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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

A practical scheme for quantum oblivious transfer and private database sampling

David A. Fattal, Marco Fiorentino B, Raymond G. Beausoleil

Published Aug 28, 2008• 1 citation
Publisher

Abstract

We present an unconditionally secure Oblivious Transfer protocol relying on two rounds of entanglement-free quantum communication. When played honestly, the protocol only requires the ability to measure a single qubit in a fixed basis, and to perform a coherent bit-flip (Pauli X) operation. We present a generalization to a "Private Data Sampling" protocol, where a player (Bob) can obtain a random sample of fixed size from a classical database of size N, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided two-party secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. Finally it could be used to implement a practical bit string commitment protocol, among other applications.

DOI
10.1117/12.793715

Related papers

Quantum private data sampling

David A. Fattal, Marco Fiorentino B, Raymond G. Beausoleil

We present a novel quantum communication protocol for "Private Data Sampling", where a player (Bob) obtains a random sample of limited size of a classical database, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided twoparty secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. After outlining the main security features of the protocol, we present our first experimental results.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 11, 2009•0 citations

Towards communication-efficient quantum oblivious key distribution

M. V. Panduranga Rao, Markus Jakobi

Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database $D$ of $N$ bits held by Bob is queried by a user Alice who is interested in the bit ${D}_{b}$ in such a way that (1) Alice learns ${D}_{b}$ and only ${D}_{b}$ and (2) Bob does not learn anything about Alice's choice $b$. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of $O(N\mathrm{log}N)$. Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to $O(N)$. A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.

arXiv:1208.2501•Physical Review A•Jan 28, 2013•63 citations

Communication channels analogous to one out of two oblivious transfers based on quantum uncertainty

Kaoru Shimizu, Nobuyuki Imoto

This paper proposes a cryptographic quantum communication scheme analogous to one out of two oblivious transfers based on quantum conjugate coding defined in a four-dimensional Hilbert space. The quantum uncertainty principle ensures that our scheme can satisfy the following two conditions: (i) a sender, Bob, can encode two bits of information $X\ensuremath{\in}{0,1}$ and $Y\ensuremath{\in}{0,1},$ but a receiver, Alice, can only obtain either X or Y dependent on her choice; and (ii) honest Bob, who attempts to encode $(X,Y),$ cannot reveal Alice's choice. By contrast, when malicious Bob tries to reveal her choice, honest Alice can detect malicious Bob with a finite probability. Moreover, by using our proposed scheme many times, we can construct a protocol for quantum bit commitment (QBC) from Alice to Bob. Contrary to common belief, the security of our QBC protocol may not be violated by the well-known no-go theorem of QBC. This is because our QBC protocol does not meet the assumptions in which the no-go theorem holds.

Physical Review A•Nov 22, 2002•10 citations

Practical Quantum Bit Commitment Protocol Based on Quantum Oblivious Transfer

Yaqi Song, Li Yang

Oblivious transfer (OT) and bit commitment (BC) are two-party cryptographic protocols which play crucial roles in the construction of various cryptographic protocols. We propose three practical quantum cryptographic protocols in this paper. We first construct a practical quantum random oblivious transfer (R-OT) protocol based on the fact that non-orthogonal states cannot be reliably distinguished. Then, we construct a fault-tolerant one-out-of-two oblivious transfer ( O T 1 2 ) protocol based on the quantum R-OT protocol. Afterwards, we propose a quantum bit commitment (QBC) protocol which executes the fault-tolerant O T 1 2 several times. Mayers, Lo and Chau (MLC) no-go theorem proves that QBC protocol cannot be unconditionally secure. However, we find that computing the unitary transformation of no-go theorem attack needs so many resources that it is not realistically implementable. We give a definition of physical security for QBC protocols and prove that the practical QBC we proposed is physically secure and can be implemented in the real world.

Applied Sciences•Oct 19, 2018•8 citations

Probabilistic versions of Quantum Private Queries

Silvia Onofri, Vittorio Giovannetti

The no-go theorem regarding unconditionally secure Quantum Bit Commitment protocols is a relevant result in quantum cryptography. Such result has been used to prove the impossibility of unconditional security for other protocols such as Quantum Oblivious Transfer or One-Sided Two Party Computation. In this paper, we formally define two non-deterministic versions of Quantum Private Queries, a protocol addressing the Symmetric-Private Information Retrieval problem. We show that the strongest variant of such scheme is formally equivalent to Quantum Bit Commitment, Quantum Oblivious Transfer and One-Sided Two-Party Computation protocols. This equivalence serves as conclusive evidence of the impracticality of achieving unconditionally secure Strong Probabilistic Quantum Private Queries.

arXiv:2401.05754•International Journal of Quantum Information•Feb 23, 2024•0 citations

Quantum Oblivious Transfer Based on POVM Measurements.

Wei Yang, Liusheng Huang, Yonglong Luo +1 more

Abstract- Oblivious transfer (OT) is an important primitive in cryptography. In chosen one-out-of-two OT, Alice offers two bits, one of which Bob can choose to read, not learning any information about the other bit. Alice on the other hand does not obtain any information about Bob’s choice. We present a new technique for the same task in quantum environment, based on POVM measurements. It is shown that our method has two important advantages over the previous approaches. First, it is unconditionally secure without invoking a commitment scheme, and second, it is more efficient in terms of communication complexity. Key words: Oblivious transfer, POVM measurements, Unconditional security

FCS•Jan 1, 2006•0 citations
We present an unconditionally secure Oblivious Transfer protocol relying on two rounds of entanglement-free quantum communication. When played honestly, the protocol only requires the ability to measure a single qubit in a fixed basis, and to perform a coherent bit-flip (Pauli X) operation. We present a generalization to a "Private Data Sampling" protocol, where a player (Bob) can obtain a random sample of fixed size from a classical database of size N, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided two-party secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. Finally it could be used to implement a practical bit string commitment protocol, among other applications.
We present a novel quantum communication protocol for "Private Data Sampling", where a player (Bob) obtains a random sample of limited size of a classical database, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided twoparty secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. After outlining the main security features of the protocol, we present our first experimental results.
Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database DDD of NNN bits held by Bob is queried by a user Alice who is interested in the bit Db{D}_{b}Db​ in such a way that (1) Alice learns Db{D}_{b}Db​ and only Db{D}_{b}Db​ and (2) Bob does not learn anything about Alice's choice bbb. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of O(NlogN)O(N\mathrm{log}N)O(NlogN). Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to O(N)O(N)O(N). A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.
This paper proposes a cryptographic quantum communication scheme analogous to one out of two oblivious transfers based on quantum conjugate coding defined in a four-dimensional Hilbert space. The quantum uncertainty principle ensures that our scheme can satisfy the following two conditions: (i) a sender, Bob, can encode two bits of information $X\ensuremath{\in}{0,1}$ and $Y\ensuremath{\in}{0,1},$ but a receiver, Alice, can only obtain either X or Y dependent on her choice; and (ii) honest Bob, who attempts to encode (X,Y),(X,Y),(X,Y), cannot reveal Alice's choice. By contrast, when malicious Bob tries to reveal her choice, honest Alice can detect malicious Bob with a finite probability. Moreover, by using our proposed scheme many times, we can construct a protocol for quantum bit commitment (QBC) from Alice to Bob. Contrary to common belief, the security of our QBC protocol may not be violated by the well-known no-go theorem of QBC. This is because our QBC protocol does not meet the assumptions in which the no-go theorem holds.
Oblivious transfer (OT) and bit commitment (BC) are two-party cryptographic protocols which play crucial roles in the construction of various cryptographic protocols. We propose three practical quantum cryptographic protocols in this paper. We first construct a practical quantum random oblivious transfer (R-OT) protocol based on the fact that non-orthogonal states cannot be reliably distinguished. Then, we construct a fault-tolerant one-out-of-two oblivious transfer ( O T 1 2 ) protocol based on the quantum R-OT protocol. Afterwards, we propose a quantum bit commitment (QBC) protocol which executes the fault-tolerant O T 1 2 several times. Mayers, Lo and Chau (MLC) no-go theorem proves that QBC protocol cannot be unconditionally secure. However, we find that computing the unitary transformation of no-go theorem attack needs so many resources that it is not realistically implementable. We give a definition of physical security for QBC protocols and prove that the practical QBC we proposed is physically secure and can be implemented in the real world.
The no-go theorem regarding unconditionally secure Quantum Bit Commitment protocols is a relevant result in quantum cryptography. Such result has been used to prove the impossibility of unconditional security for other protocols such as Quantum Oblivious Transfer or One-Sided Two Party Computation. In this paper, we formally define two non-deterministic versions of Quantum Private Queries, a protocol addressing the Symmetric-Private Information Retrieval problem. We show that the strongest variant of such scheme is formally equivalent to Quantum Bit Commitment, Quantum Oblivious Transfer and One-Sided Two-Party Computation protocols. This equivalence serves as conclusive evidence of the impracticality of achieving unconditionally secure Strong Probabilistic Quantum Private Queries.
Abstract- Oblivious transfer (OT) is an important primitive in cryptography. In chosen one-out-of-two OT, Alice offers two bits, one of which Bob can choose to read, not learning any information about the other bit. Alice on the other hand does not obtain any information about Bob’s choice. We present a new technique for the same task in quantum environment, based on POVM measurements. It is shown that our method has two important advantages over the previous approaches. First, it is unconditionally secure without invoking a commitment scheme, and second, it is more efficient in terms of communication complexity. Key words: Oblivious transfer, POVM measurements, Unconditional security