Location-Based Services (LBS) are becoming more prevalent. While there are many benefits, there are also real privacy risks. People are unwilling to give up the benefits - but can we reduce privacy risks without giving up on LBS entirely? This paper explores the possibility of introducing uncertainty into location information when using an LBS, so as to reduce privacy risk while maintaining good quality of service. This paper also explores the current uses of uncertainty information in a selection of mobile applications.

This work aims at treating the inference problem in XML documents that are assumed to represent potentially incomplete information. The inference problem consists in providing a control mechanism for enforcing inference-usability confinement of XML documents. More formally, an inference-proof view of an XML document is required to be both indistinguishable from the actual XML document to the clients under their inference capabilities, and to neither contain nor imply any confidential information. We present an algorithm for generating an inference-proof view by weakening the actual XML document, i.e., eliminating confidential information and other information that could be used to infer confidential information. In order to avoid inferences based on the schema of the XML documents, the DTD of the actual XML document is modified according to the weakening operations as well, such that the modified DTD conforms with the generated inference-proof view.

Policy-based inference control of queries submitted to a logic-oriented information system aims at confining answers to queries such that the user cannot infer the validity of any sentence specified in a confidentiality policy. Such a control requires us to consider the history of queries and answe rs to a particular user. In most previous approaches, the control system captures the history by maintaining a fictitious view the user is supposed to generate by exploiting rational reasoning. In this paper, we propose and explore an alternative option to represent the history, namely by suitably adapting the confidentiality policy after returning an answer to a query. Basically, such a policy adaptation precomputes all relevant steps of formal proofs that the fictitious view logically implies some policy element. Focusing on propositional information systems, we present a comprehensive protocol for policy adaptation, which always keeps the current version of the confidentiality policy redundancy-free and fully vulnerable. This protocol is formally proved to be effective by a reduction argument, showing that policy adaptation is able to simulate the achievements of maintaining a view. We also briefly discuss the efficiency for special cases under dedicated data structures.

Inference control aims at disabling a participant to gain a piece of information to be kept confidential. Considering a server–client architecture for information systems, we extend Controlled Query Evaluation (CQE), an inference control method to enforce confidentiality in static information syste ms under queries, to databases that are updatable by a client. More specifically, within the framework of the lying approach to CQE, we study how the server should translate a view update request issued by a client into a new database state in an inference-proof way. In order to avoid dangerous inferences, some such updates have to be denied even though the new database instance would be compatible with the set of integrity constraints declared in the schema and supposed to be known to the client. In contrast, seen from the client's point of view some other updates leading to an incompatible instance should not be denied. We design a control method to resolve this seemingly paradoxical situation and then prove that the general security definitions of CQE, suitably extended to capture both query evaluation and view update processing, and other properties linked to view updates hold. Moreover, we further enhance that control method by adding an inference-proof subprotocol for refreshing the views of the other clients. To ensure inference-proofness, from the other clients' point of view, any view update might be a transaction, i.e., a sequence of elementary updates.11This article extends, elaborates and clarifies our contribution [12] to DBSec 2009 and also comprises some results of our work [9] presented at ESORICS 2009.

No abstract available.

Controlled Query Evaluation (CQE) defines a logical framework to protect confidential information in a database. By modeling a user's a priori knowledge appropriately, a CQE system not only controls access to certain database entries but also accounts for information inferred by the user. In this a rticle, we present a static (preprocessing) CQE-approach for propositional databases with an availability policy. The resulting inference-proof and availability-preserving database ensures confidentiality of secret information while guaranteeing availability of certain database entries to a highest degree possible. We illustrate the semantics of the system by a comprehensive example and state the essential requirements for an inference-proof and availability-preserving database. We present an algorithm that accomplishes the preprocessing by combining SAT solving and “Branch and Bound”.

Recently, there has been a growing interest in web service composition and the related security issues. In this paper, we propose a framework for the decentralized execution of composite web services capable to ensure the correctness as well as the security of the execution. Our framework relies on a data structure, called container, which is passed among the web services participating in the composition. The container is encrypted and authenticated in such a way to ensure the correctness of the execution flow as well as a set of relevant security requirements.

Controlled query evaluation preserves confidentiality in information systems at runtime. A security policy defines a set of potential secrets to be hidden from a certain user. Each time the user issues a query, a censor checks whether the correct answer would enable the user to infer any of those potential secrets. Given an incomplete information system, the following problem arises: Is it safe to admit that the database cannot provide an answer to a certain query because it lacks the requested information? We show that the answer needs to be refused more often than necessary at first glance, as otherwise the user would be able to make meta level inferences that would lead to a violation of the security policy. A maximally cooperative censor, which preserves confidentiality but only refuses the answer when absolutely necessary, is presented and analyzed.

We describe a layered approach to access control for distributed and interoperable computing systems. Firstly, compound access control policies are conceptually specified, using the policy algebra proposed by Bonatti/Capitani di Vimercati/Samarati. Secondly, SPKI/SDSI is exploited to implement and to enforce a policy specification by means of credentials. Therefore, SPKI/SDSI is slightly extended, in particular in order to allow algebra expressions over local names as subjects in authorization certificates and to deal with the subtraction operator of the algebra. Besides presenting the overall approach, the paper elaborates some details for a still powerful fraction of the policy algebra, thereby examining the correctness of the credential-based implementation. Keywords: Credential, certificate chain discovery, public-key infrastructure, SPKI/SDSI, access control, policy algebra

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra. We study sparse equations, which are equations with at most polynomially many solutions. We look at their complexity and compare their expressive power with that of similar notions in the powerset algebra.

In mediated information systems clients and various autonomous sources are brought together by mediators. The mediation paradigm needs powerful and expressive security mechanisms considering the dynamics and conflicting interests of the mediation participants. Firstly, we discuss the security requi rements for mediation with an emphasis on confidentiality and authenticity. We argue for basing the enforcement of these properties on certified personal authorization attributes rather than on identification. Using a public key infrastructure such personal authorization attributes can be bound to asymmetric encryption keys by credentials. Secondly, we propose a general design of secure mediation where credentials are roughly used as follows: clients show their eligibility for receiving requested information by the contained personal authorization attributes, and sources and the mediator guarantee confidentiality by using the contained encryption keys. Thirdly, we refine the general design for a specific approach to mediation, given by our prototype of a Multimedia Mediator, MMM. Among other contributions, we define the authorization model and the specification of query access authorizations within the framework of ODL, as well as the authorization and encryption policies for mediation, and we outline the resulting security architecture of the MMM. We also analyze the achievable security properties including support for anonymity, and we discuss the inevitable tradeoffs between security and mediation functionality.

Privacy and accountability are potentially conicting organizational and legal requirements which can be approached by allowing users to act pseudonymously.The reidentication of pseudonyms should be bound to a legal purpose requiring accountability.Existing solutions entrust this function to third parties.Upon good cause shown, these parties perform reidentication on demand.The ability to perform reidentication should be technically bound to the actual existence of a legal purpose, which in some applications can be interpreted as the transgression of a threshold.We present an approach for constructing transaction-based pseudonyms as shares for a suitably adapted version of Shamir's cryptographic approach to secret sharing.Only if pseudonymous actions exceed a threshold specied by a predetermined purpose, can the actor's identity b e r e c o vered.

Deals with the problem of how to gain information from many heterogeneous data sources. As a solution, we propose a general framework for mediated information gain: it minimizes and supports the human burden, clearly identifies the algorithmically tractable subtasks and assures a well-understood level of quality. We identify a "mediation task" as an extended amalgamation of searching, querying and updating in traditional information systems, and we introduce the notion of a "formal information state" which unifies and extends the classical notions of a schema, an instance, a query with additional specifications, and a returned answer. The quality is concerned with correctness, precision and completeness. Correctness is guaranteed by maintaining internal consistency, precision is achieved by embeddings identifying only the relevant parts of the sources, and completeness is reached by user interactions with revisions and by iteration. The whole framework is characterized by 18 rules which capture the essentials and suggest a high-level architecture for implementations.

There have been many proposals on how media-on-demand servers can effectively allow clients to share resources. In this paper, given a set of clients, we show how these clients may be partitioned into "sync-classes" sets of clients who can be serviced through allocation of a single set of resources. As a set of clients may be partitioned into sync-classes in many different ways, we show that a very large class of cost functions may be used to determine which partition to choose. We provide algorithms to compute such optimal splits. Our framework is very generic in the following ways: the system may plug-in any cost function whatsoever, as long as it satisfies four common-sense axioms that evaluate costs; and the system may evaluate the future anticipated requests of a user using any user model (e.g., a Markovian model) that has a specified I/O interface. Thus, a wide variety of predictive methods (of what the user will do) and a wide variety of costing methods may be used within our framework.

A general report is presented on an approach problem of privacy-oriented information systems. The report is based on extensive research experiences in specifying the structure of such a system, including the underlying data model and the privacy policy, as well as on the insight gained from a prototype implementation of selected parts of the specification. The system is called DORIS (datenschutz-orientiertes informations system). While the model is basically object-oriented, it is possible conveniently to describe an application by non-first-normal-form tuples and relations, and the data-manipulation language is high-level and relational. An expression is evaluated in three stages: navigation in the set of surrogates of persons, asking for knowledge, and finally normalization, prime value processing and output preparation. A prototype implementation of selected parts of the model is based on a kernel concept.>

In a universal relation view queries are expressed without mentioning relation names and they are evaluated by using socalled window functions.We discuss several design rules for database schemes suited for universal relation views and formalize one of them, the One Flavor Assumption.Intuitively the One Flavor Assumption says that the real world significance of any tuple of a window does not depend on the details of its construction.For its formalization we define the essence of join paths which are used in the universal relation system DURST.We prove a deep connection between database schemes satisfying the One Flavor Assumption and y-acyclic schemes.For such database schemes we carefully compare the essence of join paths with the unique minimal Do-connection, and the result of the modified GYOreduction.For universal relation views based on such schemes the DURST window functions are essentially optimized.

The design of an appropriate conceptual database scheme is one of the most difficult tasks in usual database applications. Especially, the design of a common global database scheme for many different user groups requires a great amount of effort and skill, because the desired scheme should fit a great variety of requirements and expectations. Here, view integration is a natural method that should help to manage the complexity of such a design problem. For each user group the requirements and expectations are separately collected and specified as views, that are subsequently integrated into a global scheme supporting all those different views.

Database relations which possibly contain maybe-tuples and null values of type “value at present unknown” are studied. Maybe-tuples and null values are formally interpreted by our notion of representation , which uses classical notions of predicate logic, elaborates Codd's proposal of maybe-tuples, and adopts Reiter's concept of a closed world. Precise notions of information content and redundancy , associated with our notion of representation, are investigated. Extensions of the relational algebra to relations with maybe-tuples and null values are proposed. Our extensions are essentially Codd's, with some modifications. It is proved that these extensions have natural properties which are formally stated as being adequate and restricted . By the treatment of difference and division, our formal framework can be used even for operations that require “negative information.” Finally, extensions of update operations are discussed.

We study the following database design problem. Given a universal relation scheme 〈U, F〉 where F is a set of functional dependencies, find an in some way normalized database schema D = {〈X1, F1〉,..., 〈Xn, Fn〉} where Xi ⊂ U and Fi is inherited from F, such that D is an independent representation of the universal scheme 〈U, F〉. This means that D has both the lossless join property and the faithful closure property, (***** Fi)+ = F+, where + denotes the closure of a set of functional dependencies. We show that this goal can easily be achieved by an extension of the well-known synthetic approach of Bernstein and others to database design. We merely have to check whether the usual synthesis procedure has produced a key component 〈Xi, Fi〉 such that Xi → U ε F+; in case this is true the output of the synthesis procedure is actually an independent (and not only faithful) representation, otherwise we only have to add one further component, namely just a key. These claims are proved by a careful inspection of the Aho/Beeri/Ullman algorithm to test for losslessness. Finally, we show how to use our method to synthesize minimal independent third normal form schemas.

J. Hartmanis conjectured that the time measure of one-tape Turing machines does not have the parallel computation property. We prove this conjecture by constructing one-tape Turing machines $M_1 $ and $M_2 $ such that no one-tape Turing machine can simulate them in parallel. This is shown using a result of F. C. Hennie that nonregular sets cannot be accepted in linear time.