Private Searching on Streaming Data
Lecture notes in computer sciencePublished 1 January 2005
Rafail Ostrovsky, William E. Skeith
Citations160
SJR quartileQ2
SJR score0.35
SNIP0.55
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.
Abstract
In this paper, we consider the problem of private searching on streaming data. We show that in this model we can efficiently implement searching for documents under a secret criteria (such as presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of a Private Information Retrieval (to the more general queries and to a streaming environment as well as to public-key program obfuscation); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.
Keywords
Computer Science
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,142 Citations1983Ronald L. Rivest, Adi Shamir +1 more
Lecture notes in computer sciencePublic-Key Cryptosystems Based on Composite Degree Residuosity Classes
7,186 Citations2007Pascal Paillier
A new trapdoor mechanism is proposed and three encryption schemes are derived : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA, which are provably secure under appropriate assumptions in the standard model.
Lecture notes in computer sciencePublic Key Encryption with Keyword Search
3,103 Citations2004Dan Boneh, Giovanni Di Crescenzo +2 more
This work defines and construct a mechanism that enables Alice to provide a key to the gateway that enables the gateway to test whether the word “urgent” is a keyword in the email without learning anything else about the email.
Journal of Computer and System SciencesProbabilistic encryption
2,554 Citations1984Shafi Goldwasser, Silvio Micali
It is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources.
Lecture notes in computer scienceEvaluating 2-DNF Formulas on Ciphertexts
1,661 Citations2005Dan Boneh, Eu-Jin Goh +1 more
A homomorphic public key encryption scheme that allows the public evaluation of ψ given an encryption of the variables x1,...,xn and can evaluate quadratic multi-variate polynomials on ciphertexts provided the resulting value falls within a small set.
Journal of the ACMPrivate information retrieval
1,626 Citations1998Benny Chor, Eyal Kushilevitz +2 more
Lecture notes in computer scienceOn the (Im)possibility of Obfuscating Programs
1,263 Citations2001Boaz Barak, Oded Goldreich +5 more
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.
Lecture notes in computer scienceA Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System
1,061 Citations2001Ivan Damgård, Mads J. Jurik
A generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without loosing the homomorphic property is proposed.
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.
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.
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 scienceKeyword Search and Oblivious Pseudorandom Functions
426 Citations2005Michael J. Freedman, Yuval Ishai +2 more
This work investigates the problem of privacy-preserving access to a database, where records in the database are accessed according to their associated keywords and gives efficient solutions for various settings of KS.
Non-interactive cryptocomputing for NC/sup 1/
279 Citations2003Tomas Sander, Adam Young +1 more
This paper gives a one round, and thus round optimal, protocol for secure evaluation of circuits which is in polynomial time for NC/sup 1/ circuits and suggests applications to network and mobile computing.
Lecture notes in computer scienceAn Oblivious Transfer Protocol with Log-Squared Communication
270 Citations2005Helger Lipmaa
A one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computing and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter.
SIAM Journal on Algebraic and Discrete MethodsOn the Size of Separating Systems and Families of Perfect Hash Functions
221 Citations1984Michael L. Fredman, János Komlós
Two applications of an interesting information theoretic theorem about graphs about graphs are presented, one concerned with the derivation of good bounds for the function Y(b,k,n), and the other about the minimum size of an $(i,j)-separating system.
Lecture notes in computer scienceSingle Database Private Information Retrieval with Logarithmic Communication
163 Citations2004Yan-Cheng Chang
These schemes are based on Paillier’s cryptosystem, which along with its variants have drawn extensive studies in recent cryptographic researches and have many important applications.
Lecture notes in computer scienceSingle Database Private Information Retrieval Implies Oblivious Transfer
158 Citations2000Giovanni Di Crescenzo, Tal Malkin +1 more
It is shown that any non-trivial PIR implies Oblivious Transfer, a far better understood primitive that is complete for all two-party and multiparty secure computations and also exists a communication-efficient reduction from any PIR protocol to a 1-out-of-n Ob oblivious Transfer protocol.
Journal of ComplexityOblivious keyword search
151 Citations2004Wakaha Ogata, Kaoru Kurosawa
It is formally proved that U learns nothing more than search(w) and J gains no information on the keywords which U searched for and two efficient protocols are shown such that the size of the commitments is only O(nB) regardless of thesize of W.
Lecture notes in computer scienceA New and Efficient All-Or-Nothing Disclosure of Secrets Protocol
130 Citations1998Julien P. Stern
A new protocol which achieves the same functionality, but which is much more efficient and can easily be implemented and which is especially efficient when a large number of secrets is involved and it can be used in various applications.
Random Structures and AlgorithmsTail bounds for occupancy and the satisfiability threshold conjecture
114 Citations1995Anil Kamath, Rajeev Motwani +2 more
Lecture notes in computer scienceOne-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval
105 Citations2000Eyal Kushilevitz, Rafail Ostrovsky
This work presents a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations.
New constructions and practical applications for private stream searching
79 Citations2006John Bethencourt, Daniel S. Song +1 more
A high level outline of a new scheme for private stream searching is given and an experimental analysis of its scalability is performed, demonstrating the practical applicability of the scheme.
ACM Transactions on Information and System SecurityNew Techniques for Private Stream Searching
73 Citations2009John Bethencourt, Dawn Song +1 more
A new scheme for conducting private keyword search on streaming data which requires O(m) server to client communication complexity to return the content of the matching documents, where m is an upper bound on the size of the documents.
Lecture notes in computer scienceCryptographic Counters and Applications to Electronic Voting
61 Citations2001Jonathan Katz, Steven Myers +1 more
This work formalizes the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately and robustly, and shows a general and efficient reduction from any encryption scheme to a general cryptographic counter.