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

Journal of Software

k out of n Oblivious Transfer Protocols from Bilinear Pairings

Jing Qin, Huawei Zhao

Published Dec 14, 2009• 3 citations
Publisher

Abstract

Abstract—Two non-interactive three parties k out of n oblivious transfer protocols knOT (where 0<k<n) from bilinear pairings are proposed in this paper. In these protocols, a sender can obliviously transfer n messages to a receiver without communication with him/her. The public keys that a sender used to encrypt his/her messages are made by a third party. The receiver can extract k out of n messages at his/her choices by using the corresponding secret keys. The choices of the receiver are unconditionally secure. The sender's secrecy is guaranteed if the receiver is semi-honest in the standard model since the decision bilinear Diffie-Hellman problem (DBDH) is hard and the sender's secrecy is achieved when the receiver is a malicious party in the random oracle model since the bilinear Diffie-Hellman problem assumption (BDHA) 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. Index Terms—oblivious transfer, malicious oblivious transfer, bilinear pairing, bilinear Diffie-Hellman problems

DOI
10.4304/jsw.5.1.65-72

Related papers

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

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

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

A Verifiable 1-out-of-n Distributed Oblivious Transfer Protocol.

Christian L. F. Corniaux, Hossein Ghodosi

In the various 1-out-of-n distributed oblivious transfer protocols (DOT) designed in an unconditionally secure environment, a receiver contacts k out of m servers to obtain one of the n secrets held by a sender. After a protocol has been executed, the sender has no information on the choice of the receiver and the receiver has no information on the secrets she did not obtain. Likewise, a coalition of k − 1 servers is unable to infer any information, neither on the sender’s secrets, nor on the receiver’s choice. These protocols are based on a semi-honest model: no mechanism prevents a group of malicious servers from disrupting the protocol such that the secret obtained by the receiver does not correspond to the chosen secret. Actually, to verify the information transmitted by the servers seems to require some properties difficult to reconcile: on one hand the receiver has to collect more information from the servers to discard the incorrect data generated by the malicious servers; on the other hand, if the receiver is allowed to gather more information from the servers, the sender’s security may be compromised. We study the first unconditionally secure DOT protocol in the presence of an active adversary who may corrupt up to k − 1 servers. In addition to the active adversary, we also assume that the sender may (passively) corrupt up to k − 1 servers to learn the choice of the receiver. Similarly, the receiver may (passively) corrupt up to k − 1 servers to learn more than the chosen secret. However, we assume that the sender, receiver, and active adversary do not collaborate with each other. Our DOT protocol allows the receiver to contact 4k − 3 servers to obtain one secret, while the required security is maintained.

•Jan 1, 2013•2 citations

Efficient Fully-Simulatable Oblivious Transfer.

Yehuda Lindell

Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryp-tographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists. 1

Chicago Journal of Theoretical Computer Science•Jan 1, 2008•2 citations

Security Analysis of Three Oblivious Transfer Protocols

Gang Yao, Feng Bao, Robert Huijie Deng

An m out of n oblivious transfer (OT) protocol is a cryptographic protocol for a sender to transfer m out of n messages to a receiver such that the sender has no idea which m messages are obtained by the receiver (receiver security ) and at the same time the receiver cannot obtain more than m messages ( sender security ). Three such protocols are proposed in [1], which have the advantage that the communication overhead of the protocols is much smaller than that of m implementations of a 1 out of n OT protocol. In this paper we give a security analysis of the three protocols. First we show that the first protocol cannot guarantee both the sender security and the receiver security simultaneously. Next, we point out an obvious security flaw in the second protocol which allows the receiver to obtain all the n messages. The third protocol is nicely designed to be non-interactive. However, we show that the security of the protocol is based on a sort of parallel discrete logarithm problem, instead of the discrete logarithm problem as claimed in the paper. Using the technique of “generalized birthday attack”, the former problem can be solved with a computation complexity much smaller than that required to solve the discrete logarithm problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Birkhäuser Basel eBooks•Jan 1, 2004•4 citations
Abstract—Two non-interactive three parties k out of n oblivious transfer protocols knOT (where 0<k<n) from bilinear pairings are proposed in this paper. In these protocols, a sender can obliviously transfer n messages to a receiver without communication with him/her. The public keys that a sender used to encrypt his/her messages are made by a third party. The receiver can extract k out of n messages at his/her choices by using the corresponding secret keys. The choices of the receiver are unconditionally secure. The sender's secrecy is guaranteed if the receiver is semi-honest in the standard model since the decision bilinear Diffie-Hellman problem (DBDH) is hard and the sender's secrecy is achieved when the receiver is a malicious party in the random oracle model since the bilinear Diffie-Hellman problem assumption (BDHA) 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. Index Terms—oblivious transfer, malicious oblivious transfer, bilinear pairing, bilinear Diffie-Hellman problems
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.
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].
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.
In the various 1-out-of-n distributed oblivious transfer protocols (DOT) designed in an unconditionally secure environment, a receiver contacts k out of m servers to obtain one of the n secrets held by a sender. After a protocol has been executed, the sender has no information on the choice of the receiver and the receiver has no information on the secrets she did not obtain. Likewise, a coalition of k − 1 servers is unable to infer any information, neither on the sender’s secrets, nor on the receiver’s choice. These protocols are based on a semi-honest model: no mechanism prevents a group of malicious servers from disrupting the protocol such that the secret obtained by the receiver does not correspond to the chosen secret. Actually, to verify the information transmitted by the servers seems to require some properties difficult to reconcile: on one hand the receiver has to collect more information from the servers to discard the incorrect data generated by the malicious servers; on the other hand, if the receiver is allowed to gather more information from the servers, the sender’s security may be compromised. We study the first unconditionally secure DOT protocol in the presence of an active adversary who may corrupt up to k − 1 servers. In addition to the active adversary, we also assume that the sender may (passively) corrupt up to k − 1 servers to learn the choice of the receiver. Similarly, the receiver may (passively) corrupt up to k − 1 servers to learn more than the chosen secret. However, we assume that the sender, receiver, and active adversary do not collaborate with each other. Our DOT protocol allows the receiver to contact 4k − 3 servers to obtain one secret, while the required security is maintained.
Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryp-tographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists. 1
An m out of n oblivious transfer (OT) protocol is a cryptographic protocol for a sender to transfer m out of n messages to a receiver such that the sender has no idea which m messages are obtained by the receiver (receiver security ) and at the same time the receiver cannot obtain more than m messages ( sender security ). Three such protocols are proposed in [1], which have the advantage that the communication overhead of the protocols is much smaller than that of m implementations of a 1 out of n OT protocol. In this paper we give a security analysis of the three protocols. First we show that the first protocol cannot guarantee both the sender security and the receiver security simultaneously. Next, we point out an obvious security flaw in the second protocol which allows the receiver to obtain all the n messages. The third protocol is nicely designed to be non-interactive. However, we show that the security of the protocol is based on a sort of parallel discrete logarithm problem, instead of the discrete logarithm problem as claimed in the paper. Using the technique of “generalized birthday attack”, the former problem can be solved with a computation complexity much smaller than that required to solve the discrete logarithm problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.