-
Michael Rabin, "How to exchange secrets by oblivious transfer", Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981 [ResearchIndex]
- All-or-nothing disclosure of secrets (G. Brassard, C. Crépeau, and J.-M. Robert, Crypto 1986)
- Equivalence between two flavours of oblivious transfers (Claude Crépeau, Crypto 1987)
- Achieving Oblivious Transfer Using Weakened Security Assumptions (Claude Crépeau, Joe Kilian, 1988)
- Weakening security assumptions and oblivious transfer (C. Crépeau and J. Kilian, Crypto 1988)
- Verifiable disclosure of secrets and applications (C. Crépeau, Eurocrypt 1989)
- On the reversibility of oblivious transfer (C. Crépeau and M. Sántha, Eurocrypt 1991)
- Efficient reductions among oblivious transfer protocols based on new self-intersecting codes (C. Crépeau and M. Sántha, 1991)
- Practical quantum oblivious transfer protocols. (C.H. Bennett, G. Brassard, C. Crépeau, and M.-H. Skubiszewska, Crypto 1991)
- Practical Quantum Oblivious Transfer (Charles H. Bennett, 1992)
- Quantum Oblivious Transfer (Claude Crépeau, 1994)
- Quantum Oblivious Transfer is Secure Against Individual Measurements (Dominic Mayers, Louis Salvail, 1994)
-
1995
- On the security of the quantum oblivious transfer and key distribution protocols (Dominic Mayers, 1995)
- Committed Oblivious Transfer and Private Multi-Party Computations (C. Crépeau, J. van de Graaf, and A. Tapp, Crypto 95)
-
Non-interactive OT
- Zero-Knowledge Arguments and Public-Key Cryptography
(Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, 1995)
- Zero-Knowledge Arguments and Public-Key Cryptography
-
1996
- Oblivious Transfers and Privacy Amplification (G. Brassard and C. Crépeau, manuscript, 1996)
- Upper bound on the communication complexity of private information retrieval (Andris Ambainis, ICALP 97)
- Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments (Ivan Damgård, Ronald Cramer, TR 1996 (later published in STOC 1997))
- Oblivious Transfers and Intersecting Codes (Gilles Brassard, Claude Crepeau, Miklos Santha, 1996)
- A Secure Protocol for the Oblivious Transfer (Extended Abstract) (M.J. Fischer, S. Micali, and C. Rackoff, JoC 1996)
-
1997
- Private Information Retrieval by Keywords (Benny Chor, Niv Gilboa, Moni Naor, 1997)
- Private Simultaneous Messages Protocols with Applications (Yuval Ishai, Eyal Kushilevitz, 1997)
- Oblivious Transfers and Privacy Amplification (Gilles Brassard, Claude Crépeau, 1997)
- Efficient Distributed (n choose 1) Oblivious Transfer (Yael Gertner, Tal Malkin, 1997)
-
First sublinear 1DB CPIR
- Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval
(Kushilevitz, Ostrovsky, FOCS 97)
- Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval
-
1998
- A Random Server Model for PIR (Gertner, Goldwasser, Malkin, RANDOMM 98)
- Oblivious Transfer with a Memory-Bounded Receiver (Christian Cachin, Claude Crepeau, Julien Marcil, 1998)
- On the Foundations of Oblivious Transfer (Christian Cachin, 1998)
- Protecting Data Privacy in Private Information Retrieval Schemes (Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin, JCSS 2000)
-
More sublinears 1DB CPIRs
- A New and Efficient All or Nothing Disclosure of Secrets Protocol
(Julien P. Stern, Asiacrypt 1998) - Private Access to Distributed Information
(Eran Mann, MSc thesis, Technion, 1998)
- A New and Efficient All or Nothing Disclosure of Secrets Protocol
- On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions (Ivan B. Damgård, Joe Kilian, Louis Salvail, 1998)
-
1999
- One-way functions are essential for single-server private information retrieval (Beimel, Isahi, Malkin, Kushilevitz, STOC 99)
- Improved Upper Bounds on Information-Theoretic Private Information Retrieval ( Yuval Ishai, Eyal Kushilevitz, 1999)
- Oblivious Transfer with Adaptive Queries (Moni Naor, Benny Pinkas, 1999)
- Computationally Secure Oblivious Transfer (Moni Naor, Benny Pinkas, 1999)
- Lower Bounds for Oblivious Transfer Reductions (Yevgeniy Dodis, Silvio Micali, 1999)
- Unconditionally Secure Commitment and Oblivious Transfer Schemes Using Private Channels and a Trusted Initializer (Ronald L. Rivest, 1999)
-
First polylog CPIR
- Computationally private information retrieval with polylogarithmic communication
(Cachin, Micali, Stadler, Eurocrypt 1999)
- Computationally private information retrieval with polylogarithmic communication
-
2000
- One-way Trapdoor Permutations Are Sufficient for Non-Trivial Single-Server Private Information Retrieval (Eyal Kushilevitz, Rafail Ostrovsky, 2000)
- Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing (Beimel, Isahi, Malkin, Crypto 2000)
- Single Database Private Information Retrieval Implies Oblivious Transfer (Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky, 2000)
- Distributed Oblivious Transfer (Moni Naor, Benny Pinkas, 2000)
- Reducing String Oblivious Transfer to Universal Oblivious Transfer (Stefan Wolf, 2000)
- Concurrent Oblivious Transfer (Juan Garay, Philip MacKenzie, 2000)
- Optimistic Fair Secure Computation (Christian Cachin and Jan Camenisch, Crypto 2000)
-
2001
- Information-Theoretic Private Information Retrieval: A Unified Construction (Amos Beimel, Yuval Isahi, 2001)
- Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval (Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan, 2001)
- Practical Server Privacy Using Secure Coprocessors (S.W. Smith, D. Safford, 2001)
- Secure Games with Polynomial Expressions (Aggelos Kiayias and Moti Yung, ICALP 2001)
- Generalized Zig-zag Functions and Oblivious Transfer Reductions (Paolo Arco, Douglas Stinson, 2001)
- Efficient Oblivious Transfer Protocols (Moni Naor, Benny Pinkas, SODA 2001)
- Efficient Oblivious Transfer Schemes (Wen-Guey Tzeng, 2001)
- Oblivious Transfer in the Bounded Storage Model (Yan Zong Ding, CRYPTO 2001)
- Priced Oblivious Transfer: How to Sell Digital Goods (William Aiello, Yuval Ishai, and Omer Reingold, Eurocrypt 2001)
-
2002
-
The best known IT PIR
- [scholar]Breaking the O(n^{1/(2k-1)}) Barrier for Information-Theoretic Private Information Retrieval
(Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francois Raymond, FOCS 2002)
- [scholar]Breaking the O(n^{1/(2k-1)}) Barrier for Information-Theoretic Private Information Retrieval
- Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument (Iordanis Kerenidis, Ronald de Wolf, quant-ph/0208062)
- Oblivious Keyword Search (Wakaha Ogata, Kaoru Kurosawa, 2002)
- On Unconditionally Secure Distributed Oblivious Transfer (Ventzislav Nikov, Svetla Nikova, Bart Preneel, Joos Vandewalle, INDOCRYPT 2002)
- An Two-Server Auction Protocol (Ari Juels and Mike Szydlo, FC 2002)
- New Results on Unconditionally Secure Distributed Oblivious Transfer ( Carlo Blundo, Paolo D'Arco, Alfredo De Santis, Douglas R. Stinson, 2002)
- Practical t-out-n Oblivious Transfer and Its Applications (Qian-Hong Wu, Jian-Hong Zhang, and Yu-Min Wang, ICISC 2002)
- $m$ out of $n$ Oblivious Transfer (Yi Mu, Junqi Zhang, Vijay Varadharajan, ACISP 2002)
-
The best known IT PIR
-
2003
- Quantum Symmetrically-Private Information Retrieval (Iordanis Kerenidis, Ronald de Wolf, quant-ph/0307076)
- Quantum m-out-of-n Oblivious Transfer (Zhide Chen, Hong Zhu, cs.CR/0311039)
- A Nearly Tight Lower Bound for Private Information Retrieval Protocols ( Richard Beigel, Lance Fortnow, William Gasarch)
- Verifiable Homomorphic Oblivious Transfer and Private Equality Test (Helger Lipmaa, ASIACRYPT 2003)
![[Cool]](http://www.cs.ut.ee/~lipmaa/gifs/cool.gif)
- Extending Oblivious Transfers Efficiently (Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank, Crypto 2003)
-
2004
-
TCC 2004
- Efficient and Universally Composable Committed Oblivious Transfer and Applications
(Juan A. Garay, Philip MacKenzie, Ke Yang, TCC 2004) - Unfair Noisy Channels and Oblivious Transfer
(Ivan B. Damgård, Serge Fehr, Kirill Morozov, Louis Salvail, TCC 2004) - Computational Collapse of Quantum State with Application to Oblivious Transfer
(Claude Crépeau, Paul Dumais, Dominic Mayers, Louis Salvail, TCC 2004) - Constant round oblivious transfer in the bounded storage model
(Yan Zong Ding, Danny Harnik, Alon Rosen, Ronen Shaltiel, TCC 2004) - Implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations
(Iftach Haitner, TCC 2004)
- Efficient and Universally Composable Committed Oblivious Transfer and Applications
-
Rediscovery of Stern's CPIR with some improvements and alternative OT
- Single Database Private Information Retrieval with Logarithmic Communication
(Yan-Cheng Chang, ACISP 2004)
- Single Database Private Information Retrieval with Logarithmic Communication
- Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval (Stephanie Wehner, Ronald de Wolf, quant-ph/0403140)
- Unconditionally Secure Quantum m-out-of-n Oblivious Transfer (Zhide Chen, Tianming Bu, Hong Zhu, quant-ph/0401057)
- Keyword Search and Oblivious Pseudorandom Functions (Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold)
- Privacy Preserving Keyword Searches on Remote Encrypted Data (Yan-Cheng Chang and Michael Mitzenmacher, eprint 2004/051)
- A Synchronous Model for Multi-Party Computation and the Incompleteness of Oblivious Transfer (Dennis Hofheinz and Joern Mueller-Quade, eprint 2004/016)
- Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and Non Adaptive Queries (Cheng-Kang Chu and Wen-Guey Tzeng, eprint 2004/041 (and PKC 2005))
- Cryptographic Randomized Response Techniques (Andris Ambainis, Markus Jakobsson, Helger Lipmaa, PKC 2004)
-
Log^2 OT (best)
- An Oblivious Transfer Protocol with Log-Squared Communication
(Helger Lipmaa, eprint 2004/063)
- An Oblivious Transfer Protocol with Log-Squared Communication
- Oblivious Transfer is Symmetric (Stefan Wolf Jürg Wullschleger, eprint 2004/336)
-
TCC 2004
-
2005
- Sufficient Conditions for Collision-Resistant Hashing (Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, TCC 2005)
- A Geometric Approach to Information-Theoretic Private Information Retrieval (David Woodruff and Sergey Yekhanin, CCC 2005)
- [scholar]Smooth Projective Hashing and Two-Message Oblivious Transfer (Yael Tauman Kalai, Eurocrypt 2005)
- On Robust Combiners for Oblivious Transfer and other Primitives (Danny Harnik and Joe Kilian and Moni Naor and Omer Reingold and Alon Rosen, Eurocrypt 2005)
- Oblivious Transfer is Incomplete for Deniable Protocols (J. Müller-Quade, S. Röhrich, D. Unruh, 2005)
- (An Oblivious Transfer Protocol with Log-Squared Communication)
-
eprint version (from 2004 spring)
- An Oblivious Transfer Protocol with Log-Squared Communication
(Helger Lipmaa, eprint 2004/063)
- An Oblivious Transfer Protocol with Log-Squared Communication
- [scholar]Single-Database Private Information Retrieval with Constant Communication Rate (Craig Gentry, Zulfikar Ramzan, ICALP 2005)
- Basing Cryptographic Protocols on Tamper-Evident Seals (Tal Moran and Moni Naor, 2005)
- Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol (Ran Canetti and Ling Cheung and Dilsun Kaynar and Moses Liskov and Nancy Lynch and Olivier Pereira and Roberto Segala, eprint 2005/452)
- Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol (Felipe Saint-Jean, 2005)
-
2006
- Optimal Reductions between Oblivious Transfers using Interactive Hashing (Claude Crépeau and George Savvides, Eurocrypt 2006)
- On the Compressibility of NP Instances and Cryptographic Applications (Danny Harnik, Moni Naor, ECCC TR06-022)
- Cryptography from Anonymity (Yuval Ishai and Eyal Kushilevitz and Rafail Ostrovsky and Amit Sahai, eprint 2006/084)
- On Security of Sublinear Oblivious Transfer (Sven Laur and Helger Lipmaa, eprint 2006/088)
- An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval (Alexander Razborov, Sergey Yekhanin, ECCC TR06-050)
- Oblivious-Transfer Amplification (Juerg Wullschleger, cs.CR/0608076)
- Single-Database Private Information Retrieval Protocols: Overview, Usability and Trends (Carlos Aguilar Melchor and Philippe Gaborit, 2006)
-
2007
- On the Computational Practicality of Private Information Retrieval (Radu Sion, Bogdan Carbunar, NDSS 2007)
- Direct Reduction of String (1,2)-OT to Rabin's OT (Kaoru Kurosawa and Takeshi Koshiba, eprint 2007/046)
- A Survey of Single Database PIR: Techniques and Applications (Rafail Ostrovsky and William E. Skeith III, eprint 2007/059)
- Algebraic Lower Bounds for Computing on Encrypted Data (Rafail Ostrovsky and William E. Skeith III, eprint 2007/064)
- Public Key Encryption that Allows PIR Queries (Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III, eprint 2007/073)
- New Communication-Efficient Oblivious Transfer Protocols Based on Pairings (Helger Lipmaa, eprint 2007/133)
- Extending Oblivious Transfers Efficiently - How to get Robustness Almost for Free (Jesper Buus Nielsen, eprint 2007/215)
- Blind Identity-Based Encryption and Simulatable Oblivious Transfer (Matthew Green and Susan Hohenberger, eprint 2007/235)
- Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers (Kiran S. Kedlaya, Sergey Yekhanin, manuscript)
- [scholar]Robust information-theoretic private information retrieval (Beimel, Stahl, J of Cryptology, 2007)
- [scholar]Improving the robustness of private information retrieval (Ian Goldberg, IEEE S&P 2007)
- [scholar]Evaluating Branching Programs on Encrypted Data (Yuval Ishai, Anat Paskin, TCC 2007)
- [scholar]Adaptive Oblivious Transfer from Blind Signatures (Jan Camenisch, Gregory Neven and Abhi Shelat, Eurocrypt 2007)
- [scholar]Oblivious-Transfer Amplification (Juerg Wullschleger, Eurocrypt 2007)
- [scholar]Efficient Committed Oblivious Transfer of Bit Strings (Mehmet Kiraz, Berry Schoenmakers, José Villegas, ISC 2007)
- Oblivious-Transfer Amplification
(Juerg Wullschleger, cs.CR/0608076)
- Oblivious-Transfer Amplification
- Private Multiparty Sampling and Approximation of Vector Combinations (Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca Wright, ICALP 2007)
- [scholar]Towards 3-Query Locally Decodable Codes of Subexponential Length (Sergey Yekhanin, STOC 2007)
- New Locally Decodable Codes and Private Information Retrieval Schemes
(Sergey Yekhanin, ECCC TR06-127)
- New Locally Decodable Codes and Private Information Retrieval Schemes
- Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers (Kiran Kedlaya, Sergei Yekhanin, ECCC TR07-040)
- A New Protocol for Conditional Disclosure of Secrets And Its Applications (Sven Laur, Helger Lipmaa, ACNS 2007)
-
2008
- [scholar]Generalized Non-interactive Oblivious Transfer using Count-Limited Objects with Applications to Secure Mobile Agents (Stephen Tate, Vandana Gunupudi, FC 2008)
- [scholar]Semi-Honest to Malicious Oblivious Transfer - The Black-Box Way (Iftach Haitner, TCC 2008)
- [scholar]A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval (Iftach Haitner, Jonathan J. Hoch and Gil Segev, TCC 2008)
- [scholar]OT-Combiners via Secure Computation (Danny Harnik, Yuval Ishai, Eyal Kushilevitz and Jesper Buus Nielsen, TCC 2008)
- [scholar]A Framework for Efficient and Composable Oblivious Transfer (Chris Peikert, Vinod Vaikuntanathan, and Brent Waters, Crypto 2008)
- [Founding Cryptography on Oblivious Transfer -- Efficiently:Yuval Ishai, Manoj Prabhakaran, Amit Sahai, Crypto 2008:17.06.08] (17.06.08)
- Simulatable Adaptive Oblivious Transfer (Jan Camenisch and Gregory Neven and abhi shelat, eprint 2008/014)
- Efficient Fully-Simulatable Oblivious Transfer (Yehuda Lindell, eprint 2008/035)
- Private Branching Programs: On Communication-Efficient Cryptocomputing (Helger Lipmaa, eprint 2008/107)
- Controlling access to personal data through Accredited Symmetrically Private Information Retrieval (Mohamed Layouni, eprint 2008/129)
- Oblivious Transfer based on the McEliece Assumptions (Rafael Dowsley and Jeroen van de Graaf and J\"{o}rn M\"{u}ller-Quade and Anderson C. A. Nascimento, eprint 2008/138)
- Reducing Complexity Assumptions for Oblivious Transfer (K.Y. Cheong and Takeshi Koshiba, eprint 2008/140)
- Universally Composable Adaptive Oblivious Transfer (Matthew Green and Susan Hohenberger, eprint 2008/163)
- Restricted Adaptive Oblivious Transfer (Javier Herranz, eprint 2008/182)
- Essentially Optimal Universally Composable Oblivious Transfer (Ivan Damgård and Jesper Buus Nielsen and Claudio Orlandi, eprint 2008/220)
- Oblivious Transfer from Weak Noisy Channels (J\"urg Wullschleger, eprint 2008/420)
- [scholar]High-Speed Private Information Retrieval Computation on GPU (Melchor, C.A. Crespin, B. Gaborit, P. Jolivet, V. Rousseau, P., SECURWARE 2008)
-
2009
- How to Disassemble CPIR: First CPIR with Database-Dependent Computation (Helger Lipmaa, ICISC 2009)
-
2010
- Practical Adaptive Oblivious Transfer from a Simple Assumption (Matthew Green and Susan Hohenberger, eprint 2010/109)
-
2011
- [scholar]Efficient Fully Homomorphic Encryption from (Standard) LWE (Zvika Brakerski and Vinod Vaikuntanathan, FOCS 2011)
- Correct and Private Reductions among Oblivious Transfers (Claude Crépeau, PhD thesis, 1990)
- Private Information Retrieval Does Not Imply One-Way Permutations (Hsiao, Clement Chun-Yun, Master's thesis, 2001)
- On the Possibility of Basing Oblivious Transfer on Weakened Private Information Retrieval (Chou, Jen-Hou,Master's thesis, 1992)
- Quantum Computation and Privacy (Stephanie Werner (MSc thesis) - overview of PIRs)
- Dmitri Asonov, PhD thesis, HU-Berlin (LNCS 3128, 2004) (11.07.04)
- Symmetric Private Information Retrieval (Laura Beth Lincoln, RIT, MSC 2006)
- Design and Analysis for Log-squared and Log Private Information Retrieval (Ho Bae, MSc thesis, UCL 2008)
![[scholar]](http://www.cs.ut.ee/~lipmaa/crypto/pics/rismall.gif){kind=small}
]
- Correct and Private Reductions among Oblivious Transfers (Claude Crépeau, PhD thesis, 1990)
- Fair Computation of General Functions in Presence of Immoral Majority (Goldwasser, Levin, Crypto 1991)
- Committed Oblivious Transfer and Private Multi-Party Computation (Claude Crépeau, Jeroen van de Graaf, Alain Tapp, Crypto 1995)
- Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments (Ivan Damgård, Ronald Cramer, TR 1996 (later published in STOC 1997))
- Optimistic Fair Secure Computation (Christian Cachin and Jan Camenisch, Crypto 2000)
- An Two-Server Auction Protocol (Ari Juels and Mike Szydlo, FC 2002)
- Cryptographic Randomized Response Techniques (Andris Ambainis, Markus Jakobsson, Helger Lipmaa, PKC 2004)
- Cryptographic Randomized Response Techniques (Ambainis, Jakobsson, Lipmaa)
- Verifiable Homomorphic Oblivious Transfer and Private Equality Test (Helger Lipmaa, ASIACRYPT 2003)
]
- Privacy Preserving Auctions and Mechanism Design (Moni Naor, Benny Pinkas, Reuben Sumner, 1999)
- Distributed Oblivious Transfer (Moni Naor, Benny Pinkas, 2000)
- Efficient Oblivious Transfer Protocols (Moni Naor, Benny Pinkas, SODA 2001)
- An Two-Server Auction Protocol (Ari Juels and Mike Szydlo, FC 2002)
- Bit-Slice Auction Circuit (Kaoru Kurosawa and Wakaha Ogata, ESORICS 2002)
]
-
Papers
- Oblivious Polynomial Evaluation (Moni Nair, Benny Pinkas, 1999)
- Noisy Polynomial Interpolation and Noisy Chinese Remaindering (Daniel Bleichenbacher, Phong Q. Nguyen, 2000)
- Privacy Preserving Data Mining (Yehuda Lindell, Benny Pinkas, 2000)
- Oblivious Polynomial Evaluation and Oblivious Neural Learning (Yan-Cheng Chang, Chi-Jen Lu, 2001)
]
- Fair Games Against an All-Powerful Adversary (Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung)
- Interactive Hashing Simplies Zero-Knowledge Protocol Design (Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung)
- [scholar]Oblivious Transfer in the Bounded Storage Mode (YZ Ding, 2001)
- [scholar]Optimal reductions between oblivious transfers using interactive hashing (C Crepeau, G Savvides, Eurocrypt 2006)
- Reducing complexity assumptions for statistically-hiding commitment (Iftach Haitner, Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli, Ronen Shaltiel, Eurocrypt, 2005)
- [scholar]A new interactive hashing theorem (I Haitner, Omer Reingold, 2007)
- [scholar]One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments (Hoeteck Wee, 2007)
]
-
Papers
- Oblivious function evaluation with sub-linear complexity (Ronitt Rubinfeld, 1999)
- Oblivious transfer and polynomial evaluation (Moni Naor, Benny Pinkas, STOC 1999)
- Oblivious Polynomial Evaluation and Oblivious Neural Learning (Yan-Cheng Chang, Chi-Jen Lu)
-
Theses
- Oblivious Polynomial Evaluation and Oblivious Neural Learning (Yan-Cheng Chang, thesis, 2002)
- Oblivious Transfer (Article at wikipedia)
- Practical Private Information Retrieval Links (HU-Berlin)
- Private Information Retrieval (William Gasarch)
- A Survey of Single Database PIR: Techniques and Applications (Rafail Ostrovsky and William E. Skeith III, eprint 2007/059)
- PIR Library @ Stanford
- Private Stream Searching Toolkit (John Bethencourt, Brent Waters)
- Achieving Practical Private Information Retrieval (Panel at Securecomm 2006, 31.08.2006)
- Cryptography and Information Security Group: Private Information Retrieval (Research topic at MIT)
- Private Information Retrieval Research at BGU
- PIR Research (Dartmouth (old research))
General information
Oblivious transfer: a cryptographic two-party protocol, where either(a) the receiver gets sender's bit with probability $1/2$, without the sender getting to know whether the receiver got the bit; or (b) the receiver gets exactly one of sender's $N$ $\ell$-bit inputs, without the sender getting to know which one the receiver got; this is usually called an $1$-out-of-$N$ oblivious transfer protocol. In the $1$-out-of-$N$ PIR, receiver receives one of the inputs (and possibly more), without sender getting to know what receiver asked for.
One distinguishes between information-theoretically sender-private PIR and computationally sender-private PIR (CPIR). The first kind takes at least linear communication (in $N$) in the case of one server; there are sublinear protocols in the case of multiple servers. The second kind can be done much more communication-efficiently. In particular, [Lipmaa04] proposed a protocol with communication $O(\log^2 N+\ell\cdot\log N)$, based on the Decisional Composite Residuosity Assumption, and [GentryRamzan05] proposed a protocol with communication $O(\log N+\ell)$, based on a variant of the $\Phi$ Hiding assumption. In addition, in Lipmaa's protocol, receiver's work is polylogarithmic in $N$ while in the Gentry-Ramzan protocol, receiver's work is $O(\sqrt{N})$. For very large blocks, Lipmaa's protocol eventually achieves throughput $1$ (i.e., the CPIR communicates $\approx \ell$ bits) while the Gentry-Ramzan protocol achieves throughput $1/4$. Different flavors of PIR/OT give in general rise to very different protocols.
For a long time it was thought that one can construct an oblivious transfer protocol based on any trapdoor permutation. This is however not known to be true. [Haitner04] showed how to construct OT based on ``dense trapdoor permutations''. See [KushilevitzOstrovsky2000] for a slightly sublinear-communication OT (more precisely, PIR) based on one-way trapdoor permutations.
OT is complete for MPC by a classical result of Kilian.
A lot of work has also been done on quantum OT.
See [Rabin81] for the roots of oblivious transfer, Gasarch's link farm for a somewhat out-dated overview of (C)PIR.
gmail.com