Journal of Computer Security

With the growing needs for data sharing and dissemination, privacy-preserving data publishing is becoming an important issue that still requires further investigation. In this paper, we make a step towards private data publication by proposing a solution based on the release of vertical views (fragments) over a relational table that satisfy confidentiality and visibility constraints expressing requirements for information protection and release, respectively. We translate the problem of computing a fragmentation composed of the minimum number of fragments into the problem of computing a maximum weighted clique over a fragmentation graph. The fragmentation graph models fragments, efficiently computed using Ordered Binary Decision Diagrams (OBDDs), that satisfy all the confidentiality constraints and a subset of the visibility constraints defined in the system. We then show an exact and a heuristic algorithm for computing a minimal and a locally minimal fragmentation, respectively. Finally, we provide experimental results comparing the execution time and the fragmentations returned by the exact and heuristic algorithms. The experiments show that the heuristic algorithm has low computation cost and computes a fragmentation close to optimum.

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 answers 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.

The proliferation of sensors and mobile devices and their connectedness to the network have given rise to numerous types of situation monitoring applications. Data Stream Management Systems (DSMSs) have been proposed to address the data processing needs of such applications that require collection of high-speed data, computing results on-the-fly, and taking actions in real-time. Although a lot of work appears in the area of DSMS, not much has been done in multilevel secure (MLS) DSMS making the technology unsuitable for highly sensitive applications, such as battlefield monitoring. An MLS–DSMS should ensure the absence of illegal information flow in a DSMS and more importantly provide the performance needed to handle continuous queries. We illustrate why the traditional DSMSs cannot be used for processing multilevel secure continuous queries and discuss various DSMS architectures for processing such queries. We implement one such architecture and demonstrate how it processes continuous queries. In order to provide better quality of service and memory usage in a DSMS, we show how continuous queries submitted by various users can be shared. We provide experimental evaluations to demonstrate the performance benefits achieved through query sharing.

In today's networked world, resource providers and consumers are distributed globally and locally, especially under current cloud computing environment. However, with resource constraints, optimization is necessary to ensure the best possible usage of such scarce resources. Distributed linear programming (DisLP) problems allow collaborative agents to jointly maximize profits or minimize costs with a linear objective function while conforming to several shared as well as local linear constraints. Since each agent's share of the global constraints and the local constraints generally refer to its private limitations or capacities, serious privacy problems may arise if such information is revealed. While there have been some solutions raised that allow secure computation of such problems, they typically rely on inefficient protocols with enormous computation and communication cost.

In this paper, we study the DisLP problems where constraints are arbitrarily partitioned and every agent privately holds a set of variables, and propose secure and extremely efficient approach based on mathematical transformation in two adversary models – semi-honest and malicious model. Specifically, we first present a secure column generation (SCG) protocol that securely solves the above DisLP problem amongst two or more agents without any private information disclosure, assuming semi-honest behavior (all agents properly follow the protocol but may be curious to derive private information from other agents). Furthermore, we discuss potential selfish actions and colluding issues in malicious model (distributed agents may corrupt the protocol to gain extra benefit) and propose an incentive compatible protocol to resolve such malicious behavior. To address the effectiveness of our protocols, we present security analysis for both adversary models as well as the communication/computation cost analysis. Finally, our experimental results validate the efficiency of our approach and demonstrate its scalability.