Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Springer eBooks

Efficient Reduction among Oblivious Transfer Protocols based on New Self-Intersecting Codes

Claude Crépeau, Miklós Sántha

Published Jan 1, 1993• 9 citations
Publisher
DOI
10.1007/978-1-4613-9323-8_27

Related papers

New Communication-Efficient Oblivious Transfer Protocols Based on Pairings

Helger Lipmaa

Lecture notes in computer science•Sep 17, 2008•9 citations

Oblivious transfers and intersecting codes

Gilles Brassard, Claude Crépeau, Miklós Sántha

Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement one-out-of-t string oblivious transfer, denoted (/sup t//sub 1/)-OT/sup k//sub 2/. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k=1 and t=2 of two 1-bit secrets: this is known as one-out-of-two bit oblivious transfer, denoted (/sup 2//sub 1/)-OT/sub 2/. We address the question of implementing (/sup t//sub 1/)-OT/sup k//sub 2/ assuming the existence of a (/sup 2//sub 1/)-OT/sub 2/. In particular, we prove that unconditionally secure (/sup 2//sub 1/)-OT/sup k//sub 2/ can be implemented from /spl Theta/(k) calls to (/sup 2//sub 1/)-OT/sub 2/. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally secure oblivious transfer.

IEEE Transactions on Information Theory•Jan 1, 1996•94 citations

Alternative Protocols for Generalized Oblivious Transfer

Bhavani Shankar, Kannan Srinathan, Chandrasekharan Pandu Rangan

Springer eBooks•Dec 19, 2007•53 citations

Oblivious transfer and polynomial evaluation

Moni Naor, Benny Pinkas B

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.

ACM Symposium on Theory of Computing (STOC)•May 1, 1999•633 citations

Efficient 1-Out-n Oblivious Transfer Schemes

Wen-Guey Tzeng

Lecture notes in computer science•Jan 1, 2002•85 citations

Securely Computing Protocol of Set Intersection under the Malicious Model

Xin Liu, Weitong Chen, Naixue N. Xiong +3 more

Private set intersection (PSI) is a valuable technique with various practical applications, including secure matching of communication packets in the Internet of Things. However, most of the currently available two-party PSI protocols are based on the oblivious transfer (OT) protocol, which is computationally expensive and results in significant communication overhead. In this paper, we propose a new coding method to design a two-party PSI protocol under the semi-honest model. We analyze possible malicious attacks and then develop a PSI protocol under the malicious model using the Paillier cryptosystem, cut-and-choose, zero-knowledge proof, and other cryptographic tools. By adopting the real/ideal model paradigm, we prove the protocol’s security under the malicious model, which is more efficient compared to the existing related schemes.

Electronics•May 26, 2023•1 citation
Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement one-out-of-t string oblivious transfer, denoted (/sup t//sub 1/)-OT/sup k//sub 2/. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k=1 and t=2 of two 1-bit secrets: this is known as one-out-of-two bit oblivious transfer, denoted (/sup 2//sub 1/)-OT/sub 2/. We address the question of implementing (/sup t//sub 1/)-OT/sup k//sub 2/ assuming the existence of a (/sup 2//sub 1/)-OT/sub 2/. In particular, we prove that unconditionally secure (/sup 2//sub 1/)-OT/sup k//sub 2/ can be implemented from /spl Theta/(k) calls to (/sup 2//sub 1/)-OT/sub 2/. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally secure oblivious transfer.
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.
Private set intersection (PSI) is a valuable technique with various practical applications, including secure matching of communication packets in the Internet of Things. However, most of the currently available two-party PSI protocols are based on the oblivious transfer (OT) protocol, which is computationally expensive and results in significant communication overhead. In this paper, we propose a new coding method to design a two-party PSI protocol under the semi-honest model. We analyze possible malicious attacks and then develop a PSI protocol under the malicious model using the Paillier cryptosystem, cut-and-choose, zero-knowledge proof, and other cryptographic tools. By adopting the real/ideal model paradigm, we prove the protocol’s security under the malicious model, which is more efficient compared to the existing related schemes.