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

Oblivious Transfers and Intersecting Codes.

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

Published Jan 1, 1996• 0 citations
OpenAlex

Abstract

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 ( t 1 )--OT k 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 one-bit secrets: this is known as One-out-of-two Bit Oblivious Transfer, denoted ( 2 1 )--OT 2 . We address the question of implementing ( t 1 )--OT k 2 assuming the existence of a ( 2 1 )--OT 2 . In particular, we prove that unconditionally secure ( 2 1 )--OT k 2 can be implemented from \\Theta(k) calls to ( 2 1 )--OT 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...

Related papers

Oblivious transfers and intersecting codes

Gilles Brassard A, 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•97 citations

On the Reversibility of Oblivious Transfer

UniversitP de Paris-Sud

i (:)-OT, (one-out-of-two Bit Oblivious Transfer) is a technique by which a party S owning two secret bits b,bl, can transfer one of them b, to another party R, who chooses c. This is done in a way that does not release any bias about bz to R nor any bias about c to S. How can one build a 2TO-(i) ((;)-OT2 from R to S) given a (i)-OT, (from S to a)? This question is interesting because in many scenarios, one of the two parties will be much more powerful than the other. In the current paper we answer this question and show a number of related extensions. One interesting extension of this transfer is the (:)-OTk (one-out-of-two String O.T.) in which the two secrets qo, q1 are elements of CFk(2) instead of bits. We show that $TO-(:) can be obtained at about the same cost as (3-OT:, in terms of number of cab to (i)-OTz.

•Jan 1, 1991•5 citations

Oblivious transfer and quantum non-locality

Stefan Wolf, Jürg Wullschleger

Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT

arXiv:quant-ph/0502030•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•32 citations

Interactive hashing and reductions between Oblivious Transfer variants

George Savvides

Interactive Hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks. We present a study of this important cryptographic tool in the information theoretic context. We start by presenting a security definition which is independent of any particular setting or application. We then show that a standard implementation of Interactive Hashing satisfies all the conditions of our definition. Our proof of security improves upon previous ones in several ways. Despite its generality, it is considerably simpler. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender. Specifically, we prove that if the fraction of good strings for a dishonest sender is f, then the probability that both outputs will be good is no larger than 15.6805· f. This upper bound is valid for any f and is tight up to a small constant since a sender acting honestly would get two good outputs with probability very close to f. We illustrate the potential of Interactive Hashing as a cryptographic primitive by demonstrating efficient reductions of String Oblivious Transfer with string length k to Bit Oblivious Transfer and several weaker variants. Our reductions incorporate tests based on Interactive Hashing that allow the sender to verify the receiver's adherence to the protocol without compromising the latter's privacy. This allows a much more efficient use of the available entropy without any appreciable impact on security. As a result, for Bit OT and most of its variants n = (1 + epsilon) k executions suffice, improving efficiency by a factor of two or more compared to the most efficient reductions that do not use Interactive Hashing. As it is theoretically impossible to achieve an expansion factor n/k smaller than 1, our reductions are in fact asymptotically optimal. They are also more general since they place no restrictions on the types of 2-universal hash families used for Privacy Amplification. Lastly, we present a direct reduction of String OT to Rabin OT which uses similar methods to achieve an expansion factor of 2 + epsilon which is again asymptotically optimal.

•Jan 1, 2007•23 citations

1-out-of-2 oblivious transfer using a flawed bit-string quantum protocol

Martin Plesch, Marcin Pawłowski, Matej Pivoluska

Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only $50%$ probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.

arXiv:1611.10087•Physical Review A•Apr 18, 2017•5 citations

Oblivious Transfer Based on the McEliece Assumptions

Rafael Dowsley, Jeroen van de Graaf, Jörn Müller‐Quade +1 more

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•7 citations
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 ( t 1 )--OT k 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 one-bit secrets: this is known as One-out-of-two Bit Oblivious Transfer, denoted ( 2 1 )--OT 2 . We address the question of implementing ( t 1 )--OT k 2 assuming the existence of a ( 2 1 )--OT 2 . In particular, we prove that unconditionally secure ( 2 1 )--OT k 2 can be implemented from \Theta(k) calls to ( 2 1 )--OT 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...
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.
i (:)-OT, (one-out-of-two Bit Oblivious Transfer) is a technique by which a party S owning two secret bits b,bl, can transfer one of them b, to another party R, who chooses c. This is done in a way that does not release any bias about bz to R nor any bias about c to S. How can one build a 2TO-(i) ((;)-OT2 from R to S) given a (i)-OT, (from S to a)? This question is interesting because in many scenarios, one of the two parties will be much more powerful than the other. In the current paper we answer this question and show a number of related extensions. One interesting extension of this transfer is the (:)-OTk (one-out-of-two String O.T.) in which the two secrets qo, q1 are elements of CFk(2) instead of bits. We show that $TO-(:) can be obtained at about the same cost as (3-OT:, in terms of number of cab to (i)-OTz.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT
Interactive Hashing has featured as an essential ingredient in protocols realizing a large variety of cryptographic tasks. We present a study of this important cryptographic tool in the information theoretic context. We start by presenting a security definition which is independent of any particular setting or application. We then show that a standard implementation of Interactive Hashing satisfies all the conditions of our definition. Our proof of security improves upon previous ones in several ways. Despite its generality, it is considerably simpler. Moreover, it establishes a tighter upper bound on the cheating probability of a dishonest sender. Specifically, we prove that if the fraction of good strings for a dishonest sender is f, then the probability that both outputs will be good is no larger than 15.6805· f. This upper bound is valid for any f and is tight up to a small constant since a sender acting honestly would get two good outputs with probability very close to f. We illustrate the potential of Interactive Hashing as a cryptographic primitive by demonstrating efficient reductions of String Oblivious Transfer with string length k to Bit Oblivious Transfer and several weaker variants. Our reductions incorporate tests based on Interactive Hashing that allow the sender to verify the receiver's adherence to the protocol without compromising the latter's privacy. This allows a much more efficient use of the available entropy without any appreciable impact on security. As a result, for Bit OT and most of its variants n = (1 + epsilon) k executions suffice, improving efficiency by a factor of two or more compared to the most efficient reductions that do not use Interactive Hashing. As it is theoretically impossible to achieve an expansion factor n/k smaller than 1, our reductions are in fact asymptotically optimal. They are also more general since they place no restrictions on the types of 2-universal hash families used for Privacy Amplification. Lastly, we present a direct reduction of String OT to Rabin OT which uses similar methods to achieve an expansion factor of 2 + epsilon which is again asymptotically optimal.
Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only 5050%50 probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.
We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.