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

ACM Asia Conference on Computer and Communications Security (ASIA CCS)

Efficient computational oblivious transfer using interactive hashing

Kirill Morozov, George Savvides

Published Mar 22, 2011• 1 citation
Publisher

Abstract

We present two protocols for reducing oblivious transfer (OT) to the security of trapdoor permutations and to the hardness of some coding problems, respectively. The first protocol is the most efficient known to date, while the second one is a theoretical proof-of-concept. Our constructions leverage the power of Interactive Hashing (IH). The first protocol can be viewed as a simple modification of the well-known OT construction by Even, Goldreich and Lem-pel (1985), in which a receiver must send a random domain element to a sender through IH. Alternatively, our protocol can be viewed as a simple modification of the construction by Ostrovsky, Venkatesan and Yung (1993), in which the players substitute the one-way permutation with a trapdoor permutation. We use a similar approach to derive a second OT protocol based on coding assumptions related to security of the McEliece cryptosystem. In our second construction, the receiver inputs a public key into IH while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.

DOI
10.1145/1966913.1966977

Related papers

Computational Oblivious Transfer and Interactive Hashing

Kirill Morozov, George Savvides

We use interactive hashing to achieve the most efficient OT protocol to date based solely on the assumption that trapdoor permutations (TDP) exist. Our protocol can be seen as the following (simple) modification of either of the two famous OT constructions: 1) In the one by Even et al (1985), a receiver must send a random domain element to a sender through IH; 2) In the one by Ostrovsky et al (1993), the players should use TDP instead of one-way permutation. A similar approach is employed to achieve oblivious transfer based on the security of the McEliece cryptosystem. In this second protocol, the receiver inputs a public key into IH, while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.

•Jan 1, 2009•1 citation

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

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•21 citations

Efficient k-out-of-n Oblivious Transfer Schemes

Cheng Kang Chu, Wen-Guey Tzeng

Abstract: Oblivious transfer is an important cryptographic protocol in various security applications. For example, in on-line transactions, a k-out-of-n oblivious transfer scheme allows a buyer to privately choose k out of n digital goods from a merchant without learning information about other n−k goods. In this paper, we propose several efficient two-round k-out-of-n oblivious transfer schemes, in which the receiver R sends O(k) messages to the sender S, andS sends O(n) messages back to R. The schemes provide unconditional security for either sender or receiver. The computational security for the other side is based on the Decisional Diffie-Hellman (DDH) or Chosen-Target Computational Diffie-Hellman (CT-CDH) problems. Our schemes have the nice property of universal parameters, that is, each pair of R and S need not hold any secret before performing the protocol. The system parameters can be used by all senders and receivers without any trapdoor specification. In some cases, our OT k n schemes are the most efficient ones in terms of the communication cost, either in rounds or the number of messages. Moreover, one of our schemes is extended to an adaptive oblivious transfer scheme. In that scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, onlyO(1) messages are exchanged and O(1) operations are performed. The preliminary version of this paper was published at PKC ’05 [Chu and Tzeng 2005].

•Jan 1, 2007•24 citations

Non-interactive Oblivious Transfer Protocols

Jing Qin, Zhao Huawei, Mingqiang Wang

Two novel constructions of one out of n oblivious transfer protocols from bilinear maps between groups are proposed. The protocols satisfy the category of non-interactive, mean that any sender S can obliviously transfer some secret(s) to a receiver R, but R does not send any messages back to S. The choice of a receiver is unconditionally secure. A sender's secrecy is guaranteed if the receiver is semi-honest in a standard model since the decision bilinear Diffie-Hellman problem is hard and the sender's secrecy is achieved when the receiver is a malicious party in a random oracle model since the bilinear Diffie-Hellman problem assumption holds. When a sender is a cheating party, the receiver will detect him/her and halt the protocol. A precise proof of the security of the protocols is presented.

International Forum on Information Technology and Applications•May 1, 2009•3 citations

A Survey of Oblivious Transfer Protocol

Vijay Kumar Yadav, Nitish Andola, Shekhar Verma +1 more

Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.

ACM Computing Surveys•Jan 5, 2022•41 citations
We present two protocols for reducing oblivious transfer (OT) to the security of trapdoor permutations and to the hardness of some coding problems, respectively. The first protocol is the most efficient known to date, while the second one is a theoretical proof-of-concept. Our constructions leverage the power of Interactive Hashing (IH). The first protocol can be viewed as a simple modification of the well-known OT construction by Even, Goldreich and Lem-pel (1985), in which a receiver must send a random domain element to a sender through IH. Alternatively, our protocol can be viewed as a simple modification of the construction by Ostrovsky, Venkatesan and Yung (1993), in which the players substitute the one-way permutation with a trapdoor permutation. We use a similar approach to derive a second OT protocol based on coding assumptions related to security of the McEliece cryptosystem. In our second construction, the receiver inputs a public key into IH while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.
We use interactive hashing to achieve the most efficient OT protocol to date based solely on the assumption that trapdoor permutations (TDP) exist. Our protocol can be seen as the following (simple) modification of either of the two famous OT constructions: 1) In the one by Even et al (1985), a receiver must send a random domain element to a sender through IH; 2) In the one by Ostrovsky et al (1993), the players should use TDP instead of one-way permutation. A similar approach is employed to achieve oblivious transfer based on the security of the McEliece cryptosystem. In this second protocol, the receiver inputs a public key into IH, while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.
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.
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.
Abstract: Oblivious transfer is an important cryptographic protocol in various security applications. For example, in on-line transactions, a k-out-of-n oblivious transfer scheme allows a buyer to privately choose k out of n digital goods from a merchant without learning information about other n−k goods. In this paper, we propose several efficient two-round k-out-of-n oblivious transfer schemes, in which the receiver R sends O(k) messages to the sender S, andS sends O(n) messages back to R. The schemes provide unconditional security for either sender or receiver. The computational security for the other side is based on the Decisional Diffie-Hellman (DDH) or Chosen-Target Computational Diffie-Hellman (CT-CDH) problems. Our schemes have the nice property of universal parameters, that is, each pair of R and S need not hold any secret before performing the protocol. The system parameters can be used by all senders and receivers without any trapdoor specification. In some cases, our OT k n schemes are the most efficient ones in terms of the communication cost, either in rounds or the number of messages. Moreover, one of our schemes is extended to an adaptive oblivious transfer scheme. In that scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, onlyO(1) messages are exchanged and O(1) operations are performed. The preliminary version of this paper was published at PKC ’05 [Chu and Tzeng 2005].
Two novel constructions of one out of n oblivious transfer protocols from bilinear maps between groups are proposed. The protocols satisfy the category of non-interactive, mean that any sender S can obliviously transfer some secret(s) to a receiver R, but R does not send any messages back to S. The choice of a receiver is unconditionally secure. A sender's secrecy is guaranteed if the receiver is semi-honest in a standard model since the decision bilinear Diffie-Hellman problem is hard and the sender's secrecy is achieved when the receiver is a malicious party in a random oracle model since the bilinear Diffie-Hellman problem assumption holds. When a sender is a cheating party, the receiver will detect him/her and halt the protocol. A precise proof of the security of the protocols is presented.
Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.