Information sharing across private databases
Published 9 June 2003
Rakesh Agrawal, Alexandre Evfimievski, Ramakrishnan Srikant
Citations638
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work formalizes the notion of minimal information sharing across private databases, and develops protocols for intersection, equijoin, intersection size, and Equijoin size.
Abstract
Literature on information integration across databases tacitly assumes that the data in each database can be revealed to the other databases. However, there is an increasing need for sharing information across autonomous entities in such a way that no information apart from the answer to the query is revealed. We formalize the notion of minimal information sharing across private databases, and develop protocols for intersection, equijoin, intersection size, and equijoin size. We also show how new applications can be built using the proposed protocols.
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Bell System Technical JournalCommunication Theory of Secrecy Systems*
9,330 Citations1949Claude E. Shannon
A theory of secrecy systems is developed on a theoretical level and is intended to complement the treatment found in standard works on cryptography.
IEEE Transactions on Information TheoryA public key cryptosystem and a signature scheme based on discrete logarithms
8,018 Citations1985Taher ElGamal
The invention pertains to a novel method of forming a flexible, tapered end on a thermoplastic molding strip that is flexible and virtually free of residual stress which may cause a strip to delaminate when applied to a desired substratum.
Random oracles are practical
4,689 Citations1993Mihir Bellare, Phillip Rogaway
It is argued that the random oracles model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice, and yields protocols much more efficient than standard ones while retaining many of the advantages of provable security.
Lecture notes in computer scienceHow To Prove Yourself: Practical Solutions to Identification and Signature Problems
3,870 Citations2007Amos Fiat, Adi Shamir
Simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any other user without shared or public keys are described.
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
ACM SIGMOD RecordPrivacy-preserving data mining
2,993 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
Privacy-preserving data mining
1,706 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
This work considers the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed, and proposes a novel reconstruction procedure to accurately estimate the distribution of original data values.
Private information retrieval
1,116 Citations2002Benny Chor, Oded Goldreich +2 more
Schemes that enable a user to access k replicated copies of a database and privately retrieve information stored in the database and get no information on the identity of the item retrieved by the user are described.
Privacy preserving association rule mining in vertically partitioned data
1,009 Citations2002Jaideep Vaidya, Chris Clifton
This paper presents a two-party algorithm for efficiently discovering frequent itemsets with minimum support levels, without either site revealing individual transaction values.
ACM Computing SurveysSecurity-control methods for statistical databases: a comparative study
969 Citations1989Nabil R. Adam, John C. Worthmann
It is recommended directing future research efforts toward developing new methods that prevent exact disclosure and provide statistical-disclosure control, while at the same time do not suffer from the bias problem and the 0/1 query-set-size problem.
The TSIMMIS project: Integration of heterogeneous information sources
930 Citations1994Sudarshan S. Chawathe, Héctor García-Molina +5 more
Replication is not needed: single database, computationally-private information retrieval
919 Citations2002Eyal Kushilevitz, Rafail Ostrovsky
Based on the quadratic residuosity assumption, a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl Epsiv/>0.0 is presented.
Privacy-preserving distributed mining of association rules on horizontally partitioned data
890 Citations2010Murat Kantarcıoğlu, Chris Clifton +2 more
Lecture notes in computer scienceThe Decision Diffie-Hellman problem
870 Citations1998Dan Boneh
This paper surveys the recent applications of DDH as well as known results regarding its security, and describes some open problems in this area.
Privacy preserving mining of association rules
785 Citations2002Alexandre Evfimievski, Ramakrishnan Srikant +2 more
A class of randomization operators are proposed that are much more effective than uniform randomization in limiting the breaches of privacy breaches and derived formulae for an unbiased support estimator and its variance are derived.
Privacy preserving auctions and mechanism design
764 Citations1999Moni Naor, Benny Pinkas +1 more
An architecture for executing protocols for auctions and, more generally, mechanism design is suggested to preserve the privacy of the inputs of the participants while maintaining communication and computational e(cid:14)ciency.
Journal of CryptologyPrivacy Preserving Data Mining
673 Citations2002Yehuda Lindell, Pinkas
This work considers a scenario in which two parties owning confidential databases wish to run a data mining algorithm on the union of their databases, without revealing any unnecessary information, and proposes a protocol that is considerably more efficient than generic solutions and demands both very few rounds of communication and reasonable bandwidth.
Elsevier eBooksHippocratic Databases
634 Citations2002Rakesh Agrawal, Jerry Kiernan +2 more
It is argued that future database systems must include responsibility for the privacy of data that they manage as a founding tenet, because of the explosive progress in networking, storage, and processor technologies.
Oblivious transfer and polynomial evaluation
630 Citations1999Moni Naor, Benny Pinkas
The efficiency of the new OT protocols makes them useful for a variety of applications, including oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.
Symposium on Discrete AlgorithmsEfficient oblivious transfer protocols
627 Citations2001Moni Naor, Benny Pinkas
This paper presents several significant improvements to oblivious transfer protocols of strings, and in particular providing the first two-round OT protocol whose security analysis does not invoke the random oraclemodel.
Lecture notes in computer scienceComputationally Private Information Retrieval with Polylogarithmic Communication
586 Citations1999Christian Cachin, Silvio Micali +1 more
A single-database computationally private information retrieval scheme with polylogarithmic communication complexity based on a new, but reasonable intractability assumption, which is essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization.
Lecture notes in computer scienceOne-Way Accumulators: A Decentralized Alternative to Digital Signatures
535 Citations1994Josh Benaloh, Michael de Mare
A simple candidate one-way hash function which satisfies a quasi-commutative property that allows it to be used as an accumulator is described, which allows protocols to be developed in which the need for a trusted central authority can be eliminated.
Elsevier eBooksMaintaining Data Privacy in Association Rule Mining
492 Citations2002Shariq J. Rizvi, Jayant R. Haritsa
This work presents a scheme, based on probabilistic distortion of user data, that can simultaneously provide a high degree of privacy to the user and retain a high level of accuracy in the mining results.
Protecting data privacy in private information retrieval schemes
447 Citations1998Yael Gertner, Yuval Ishai +2 more
This paper shows how to transform PIR schemes into SPIR schemes (with information-theoretic privacy), paying a constant factor in communication complexity, and introduces a new cryptographic primitive, called conditional disclosure of secrets, which it is believed may be a useful building block for the design of other cryptographic protocols.
IEEE Transactions on Software EngineeringView Definition and Generalization for Database Integration in a Multidatabase System
328 Citations1984Umeshwar Dayal, Hai-Yann Hwang
A versatile view definition facility for the functional data model is described and the use of this facility for resolving inconsistencies is illustrated and its importance to database integration is emphasized.
Cryptography: Theory and Practice,Second Edition
263 Citations2002Douglas R. Stinson
There is increased emphasis on general concepts, but the outstanding features that first made this a bestseller all remain, including its mathematical rigor, numerous examples, pseudocode descriptions of algorithms, and clear, precise explanations.
Privacy preserving association rule mining
247 Citations2003Yücel Saygın, Vassilios S. Verykios +1 more
New metrics are introduced in order to demonstrate how security issues can be taken into consideration in the general framework of association rule mining, and it is shown that the complexity of the new heuristics is similar to that of the original algorithms.
Computationally private information retrieval (extended abstract)
246 Citations1997Benny Chor, Niv Gilboa
Enhancing privacy and trust in electronic communities
222 Citations1999Bernardo A. Huberman, Matthew Franklin +1 more
This work proposes new non-third party mechanisms to overcome barriers to finding shared preferences, discovering communities with shared values, removing disincentives posed by liabilities, and negotiating on behalf of a group.
ACM Transactions on Database SystemsThe tracker
207 Citations1979Dorothy E. Denning, Peter J. Denning
It is shown that the compromise of small query sets can in fact almost always be accomplished with the help of characteristic formulas called trackers, and security is not guaranteed by the lack of a general tracker.
ACM Transactions on Database SystemsSecure databases
203 Citations1979David Dobkin, Anita K. Jones +1 more
Users may be able to compromise databases by asking a series of questions and then inferring new information from the answers, and the complexity of protecting a database against this technique is discussed here.
Transforming Heterogeneous Data with Database Middleware: Beyond Integration.
190 Citations1999Laura M. Haas, Renée J. Miller +4 more
This paper looks at database middleware systems as tranformation engines, and discusses when and how data is transformed to provide users with the information they need.
Elsevier eBooksDistributed Search over the Hidden Web
189 Citations2002Panagiotis G. Ipeirotis, Luis Gravano
This paper presents an algorithm to derive content summaries from "uncooperative" databases by using "focused query probes," which adaptively zoom in on and extract documents that are representative of the topic coverage of the databases.
IEEE Transactions on Software EngineeringAuditing and Inference Control in Statistical Databases
186 Citations1982Francis Y. L. Chin, Gültekin Özsoyoğlu
A statistical database (SDB) may be defined as an ordinary database with the capability of providing statistical information to user queries, which is to limit the use of the SDB so that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual.
Journal of the American Statistical AssociationOn the Question of Statistical Confidentiality
174 Citations1972Ivan P. Fellegi
The nature of statistical confidentiality is explored, its essential role in the collection of data by statistical offices, its relationship to privacy and the need for increased attention to potential statistical disclosures because of the increased tabulation and dissemination capabilities of statistical offices are explored.
Management of heterogeneous and autonomous database systems
169 Citations1998Ahmed K. Elmagarmid, Marek Rusinkiewicz +1 more
1.1.
Communication preserving protocols for secure function evaluation
167 Citations2001Moni Naor, Kobbi Nissim
This work proposes a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f, and exemplifies a protocol for the Millionaires problem, which is more efficient than previously known ones in either communication or computation.
IEEE Transactions on Knowledge and Data EngineeringPrivacy-preserving distributed mining of association rules on horizontally partitioned data
152 Citations2004Murat Kantarcıoğlu, Chris Clifton
This work addresses secure mining of association rules over horizontally partitioned data by incorporating cryptographic techniques to minimize the information shared, while adding little overhead to the mining task.
An XPath-based preference language for P3P
99 Citations2003Rakesh Agrawal, Jerry Kiernan +2 more
This work identifies the minimal subset of XPath that is needed, thus allowing matching programs to potentially use a smaller memory footprint and gives an APPEL to XPath translator that shows that XPath is as expressive as APPEL.
Lecture notes in computer scienceA proposed architecture for trusted third party services
84 Citations1996Nigel Jefferies, Chris J. Mitchell +1 more
A novel solution to the problem of providing trusted third party services, such as the management of cryptographic keys for end-to-end encryption, in a way that meets legal requirements for warranted interception is proposed.
Intelligent integration of information
68 Citations1993Gio Wiederhold
The computational models needed to support the mediating functions in this three-layer, mediated architecture are focused on and initial applicatiions are introduced.
Implementing P3P using database technology
64 Citations2004Rakesh Agrawal, Jerry Kiernan +2 more
This work discusses architectural alternatives for implementing P3P and presents a server-centric implementation that reuses database querying technology, as opposed to the prevailing client-centric implementations based on specialized engines.