The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Oblivious transfer and polynomial evaluation
Open accessAbstract
We describe efficient constructions for two oblivious twoparty computation problems: l-out-of-N Oblivious Transfer &d 'Oblivious Poly&nial Evaluation.The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial re construction.A direct corollary of the l-out-of-N OT protccol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) prc-tow1 without increasing the number of databases.The new construction for l-out-of-N OT is highly efficient -it requires only log N executions of a l-out-of-2 OT protocol.We also present a construction for k-out-of-N OT which is more efficient than k repetitions of l-out-of-N OT.The efficiency of the new OT protocols makes them useful for a variety of applications.These include 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
The Theory of Error-Correcting Codes
(1977) · North-Holland Mathematical Library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,760
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Wiesner, S. (1983) · ACM SIGACT News · doi:10.1145/1008908.1008920 · Cited by 1,520
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
(2017) · Lexikon des gesamten Buchwesens Online · doi:10.1163/9789004337862_lgbo_com_161117 · Cited by 1,432
Encrypted key exchange: password-based protocols secure against dictionary attacks
Bellovin, S. M., & Merritt, M. (2003) · Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy · doi:10.1109/risp.1992.213269 · Cited by 1,353
Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492461 · Cited by 1,116
Replication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Advances in Cryptology – CRYPTO 2005
(2005) · Lecture notes in computer science · doi:10.1007/11535218 · Cited by 725
Decoding of Reed Solomon Codes beyond the Error-Correction Bound
Sudan, M. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0439 · Cited by 723
Advances in Cryptology — CRYPTO ’91: Proceedings
(1992) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1 · Cited by 687
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73012 · Cited by 575
Protecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276723 · Cited by 445
Advances in Cryptology — CRYPTO ’87: Proceedings
(1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2 · Cited by 430
A technique for measuring the relative size and overlap of public Web search engines
Bharat, K., & Broder, A. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00127-5 · Cited by 389
Pseudorandomness and Cryptographic Applications
Luby, M. (1996) · Princeton University Press eBooks · doi:10.1515/9780691206844 · Cited by 374
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646134 · Cited by 353
Self-citationHow to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
All-or-Nothing Disclosure of Secrets
Brassard, G., Crepeau, C., & Robert, J.-M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_17 · Cited by 297
Non-Interactive Oblivious Transfer and Applications
Bellare, M., & Micali, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_48 · Cited by 297
On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited
Naor, M., & Reingold, O. (1999) · Journal of Cryptology · doi:10.1007/pl00003817 · Cited by 285
Self-citationFoundations of Secure Interactive Computing
Beaver, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_31 · Cited by 277
Equivalence Between Two Flavours of Oblivious Transfers
Crépeau, C. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_30 · Cited by 252
Comparing information without leaking it
Fagin, R., Naor, M., & Winkler, P. (1996) · Communications of the ACM · doi:10.1145/229459.229469 · Cited by 200
Self-citationSynthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions
Naor, M., & Reingold, O. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1618 · Cited by 168
Self-citationLearning polynomials with queries: The highly noisy case
Goldreich, O., Rubinfeld, R., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492485 · Cited by 167
Micali, S. M., & Rogaway, P. (2007) · Springer eBooks · doi:10.1007/3-540-46766-1_32 · Cited by 163
Open key exchange: How to defeat dictionary attacks without encrypting public keys
Lucks, S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028161 · Cited by 114
Uses of randomness in algorithms and protocols
Kilian, J. (1991) · Choice Reviews Online · doi:10.5860/choice.28-6294 · Cited by 86
On the foundations of oblivious transfer
Cachin, C. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054139 · Cited by 50
Cited by
Public Key Encryption with Keyword Search
Boneh, D., Di Crescenzo, G., Ostrovsky, R., & Persiano, G. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_30 · Cited by 3,134
Efficient Private Matching and Set Intersection
Freedman, M. J., Nissim, K., & Pinkas, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_1 · Cited by 1,266
Self-citationPrivacy Preserving Data Mining
Lindell, Y., & Pinkas, B. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44598-6_3 · Cited by 1,077
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746
Privacy Preserving Data Mining
Lindell, & Pinkas (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0019-2 · Cited by 668
Metadata
- Authors
- Naor, M., & Pinkas, B.
- Venue
- Proceedings of the thirty-first annual ACM symposium on Theory of Computing
- Publisher
- ACM
- Published
- 1999-05
- Pages
- 245-254
- OpenAlex
- W2017464959
- Cited by
- 629
- References
- 34
- FWCI
- 12.17
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.