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

IEEE Transactions on Information Theory

One-Out-of-q OT Combiners

Oriol Farràs, Jordi Ribes-González

Published Dec 7, 2023• 2 citations
Publisher

Abstract

In 1-out-of-$q$Oblivious Transfer (OT) protocols, a sender Alice is able to send one of$q\ge 2$messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take$n$instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the$n$original OT instances are secure. We present new 1-out-of-$q$OT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an$\mathbb {F}_{q}$-linear secret sharing scheme on a set of$n$participants and adversary structure$\mathcal {A}$, we can construct an$n$-server, 1-out-of-$q$OT combiner that is secure against an adversary corrupting either Alice and a set of servers in$\mathcal {A}$, or Bob and a set of servers$B$with$\bar {B}\notin \mathcal {A}$. If the normalized total share size of the scheme is$\ell $, then the resulting OT combiner requires$\ell $calls to OT protocols, and the total amount of bits exchanged during the protocol is$(q^{2}+q+1)\ell \log q$. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power$q\geq n$, there are$n$-server, 1-out-of-$q$OT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchanging$O(qn\log q)$bits in total.

DOI
10.1109/tit.2023.3340294

Related papers

Resource-Efficient OT Combiners with Active Security

Ignacio Cascudo, Ivan Damgård, Oriol Farràs +1 more

An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.

Lecture notes in computer science•Jan 1, 2017•6 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•38 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

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

Quantum m-out-of-n oblivious transfer

Zhide Chen, Hong Zhu

In the m-out-of-n oblivious transfer (OT) model, one party Alice sends n bits to another party Bob, Bob can get only m bits from the n bits. However, Alice cannot know which m bits Bob received. Y. Mu and Naor presented classical m-out-of-n oblivious transfer based on discrete logarithm. As the work of Shor, the discrete logarithm can be solved in polynomial time by quantum computers, so such OTs are unsecure to the quantum computer. In this paper, we construct a quantum m-out-of-n OT (QOT) scheme based on the transmission of polarized light and show that the scheme is robust to general attacks, i.e. the QOT scheme satisfies statistical correctness and statistical privacy.

arXiv:cs/0311039•IEEE Symposium on Computers and Communications (ISCC)•Jan 1, 2004•4 citations

Quantum Oblivious Transfer with Reusable Bell State

Shu–Yu Kuo, Kuo-Chun Tseng, Yao–Hsin Chou +1 more

In cryptography, oblivious transfer (OT) is an important multi-party cryptographic primitive and protocol, that is suitable for many upper-layer applications, such as secure computation, remote coin-flipping, electrical contract signing and exchanging secrets simultaneously. However, some no-go theorems have been established, indicating that one-out-of-two quantum oblivious transfer (QOT) protocols with unconditional security are impossible. Fortunately, some one-out-of-two QOT protocols using the concept of Crépeau’s reduction have been demonstrated not to conform to Lo’s no-go theorem, but these protocols require more quantum resources to generate classical keys using all-or-nothing QOT to construct one-out-of-two QOT. This paper proposes a novel and efficient one-out-of-two QOT which uses quantum resources directly instead of wasting unnecessary resources to generate classical keys. The proposed protocol is not covered by Lo’s no-go theorem, and it is able to check the sender’s loyalty and avoid the attack from the receiver. Moreover, the entangled state of the proposed protocol is reusable, so it can provide more services for the participants when necessary. Compared with other QOT protocols, the proposed protocol is more secure, efficient, and flexible, which not only can prevent external and internal attacks, but also reduce the required resources and resource distribution time.

Computers, materials & continua/Computers, materials & continua (Print)•Sep 22, 2022•2 citations
In 1-out-of-qqqOblivious Transfer (OT) protocols, a sender Alice is able to send one ofq≥2q\ge 2q≥2messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners takennninstances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of thennnoriginal OT instances are secure. We present new 1-out-of-qqqOT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given anFq\mathbb {F}_{q}Fq​-linear secret sharing scheme on a set ofnnnparticipants and adversary structureA\mathcal {A}A, we can construct annnn-server, 1-out-of-qqqOT combiner that is secure against an adversary corrupting either Alice and a set of servers inA\mathcal {A}A, or Bob and a set of serversBBBwithBˉ∉A\bar {B}\notin \mathcal {A}Bˉ∈/A. If the normalized total share size of the scheme isℓ\ell ℓ, then the resulting OT combiner requiresℓ\ell ℓcalls to OT protocols, and the total amount of bits exchanged during the protocol is(q2+q+1)ℓlog⁡q(q^{2}+q+1)\ell \log q(q2+q+1)ℓlogq. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime powerq≥nq\geq nq≥n, there arennn-server, 1-out-of-qqqOT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchangingO(qnlog⁡q)O(qn\log q)O(qnlogq)bits in total.
An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.
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.
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.
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.
In the m-out-of-n oblivious transfer (OT) model, one party Alice sends n bits to another party Bob, Bob can get only m bits from the n bits. However, Alice cannot know which m bits Bob received. Y. Mu and Naor presented classical m-out-of-n oblivious transfer based on discrete logarithm. As the work of Shor, the discrete logarithm can be solved in polynomial time by quantum computers, so such OTs are unsecure to the quantum computer. In this paper, we construct a quantum m-out-of-n OT (QOT) scheme based on the transmission of polarized light and show that the scheme is robust to general attacks, i.e. the QOT scheme satisfies statistical correctness and statistical privacy.
In cryptography, oblivious transfer (OT) is an important multi-party cryptographic primitive and protocol, that is suitable for many upper-layer applications, such as secure computation, remote coin-flipping, electrical contract signing and exchanging secrets simultaneously. However, some no-go theorems have been established, indicating that one-out-of-two quantum oblivious transfer (QOT) protocols with unconditional security are impossible. Fortunately, some one-out-of-two QOT protocols using the concept of Crépeau’s reduction have been demonstrated not to conform to Lo’s no-go theorem, but these protocols require more quantum resources to generate classical keys using all-or-nothing QOT to construct one-out-of-two QOT. This paper proposes a novel and efficient one-out-of-two QOT which uses quantum resources directly instead of wasting unnecessary resources to generate classical keys. The proposed protocol is not covered by Lo’s no-go theorem, and it is able to check the sender’s loyalty and avoid the attack from the receiver. Moreover, the entangled state of the proposed protocol is reusable, so it can provide more services for the participants when necessary. Compared with other QOT protocols, the proposed protocol is more secure, efficient, and flexible, which not only can prevent external and internal attacks, but also reduce the required resources and resource distribution time.