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
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
Privacy-Preserving Set Operations
Kissner, L., & Song, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_15 · Cited by 648
Information sharing across private databases
Agrawal, R., Evfimievski, A., & Srikant, R. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872771 · Cited by 634
Efficient oblivious transfer protocols
Naor, M., & Benny Pinkas, B. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365502 · Cited by 614
Self-citationLiu, K., Kargupta, H., & Ryan, J. (2006) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2006.14 · Cited by 554
Secure multi-party computation problems and their applications: a review and open problems
Du, W., & Atallah, M. J. (2001) · Proceedings of the 2001 workshop on New security paradigms · doi:10.1145/508171.508174 · Cited by 453
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
Keyword Search and Oblivious Pseudorandom Functions
Freedman, M. J., Ishai, Y., Pinkas, B., & Reingold, O. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_17 · Cited by 441
Self-citationCryptographic techniques for privacy-preserving data mining
Pinkas, B. (2002) · ACM SIGKDD Explorations Newsletter · doi:10.1145/772862.772865 · Cited by 430
Self-citationPriced Oblivious Transfer: How to Sell Digital Goods
Aiello, B., Ishai, Y., & Reingold, O. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_8 · Cited by 400
Single-Database Private Information Retrieval with Constant Communication Rate
Gentry, C., & Ramzan, Z. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_65 · Cited by 313
Privacy-preserving cooperative statistical analysis
Du, W., & Atallah, M. J. (2005) · Seventeenth Annual Computer Security Applications Conference · doi:10.1109/acsac.2001.991526 · Cited by 279
An Oblivious Transfer Protocol with Log-Squared Communication
Lipmaa, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11556992_23 · Cited by 271
Hazay, C., & Lindell, Y. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_10 · Cited by 267
Privacy Preserving Naïve Bayes Classifier for Vertically Partitioned Data
Vaidya, J., & Clifton, C. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.59 · Cited by 262
Deriving genomic diagnoses without revealing patient genomes
Jagadeesh, K. A., Wu, D. J., Birgmeier, J. A., Boneh, D., & Bejerano, G. (2017) · Science · doi:10.1126/science.aam9710 · Cited by 134
Efficient Federated Matrix Factorization Against Inference Attacks
Chai, D., Wang, L., Chen, K., & Yang, Q. (2022) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3501812 · Cited by 20
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.