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

Electronic colloquium on computational complexity

Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Andreas Jakoby, Maciej Liśkiewicz, Aleksander Mądry

Published Jan 1, 2006• 0 citations
Publisher

Abstract

We define $(varepsilon,delta)$-secure quantum computations between two parties that can play dishonestly to maximise advantage $delta$, however keeping small the probability $varepsilon$ that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is $(O(sqrt{varepsilon}),varepsilon)$-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.

DOI
10.4230/dagsemproc.06111.21

Related papers

Using quantum oblivious transfer to cheat sensitive quantum bit commitment

Andreas Jakoby, Maciej Liśkiewicz, Aleksander Mądry

It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independently by Aharonov et al. [STOC, 2000] and Hardy and Kent [Phys. Rev. Lett. 92 (2004)] is investigated. In this variant, the parties require some nonzero probability of detecting a cheating, i.e. if Bob, who commits a bit b to Alice, changes his mind during the revealing phase then Alice detects the cheating with a positive probability (we call this property binding); and if Alice gains information about the committed bit before the revealing phase then Bob discovers this with positive probability (sealing). In our paper we give quantum bit commitment scheme that is simultaneously binding and sealing and we show that if a cheating gives epsilon advantage to a malicious Alice then Bob can detect the cheating with a probability Omega(epsilon^2). If Bob cheats then Alice's probability of detecting the cheating is greater than some fixed constant lambda>0. This improves the probabilities of cheating detections shown by Hardy and Kent and the scheme by Aharonov et al. who presented a protocol that is either binding or sealing, but not simultaneously both. To construct a cheat sensitive quantum bit commitment scheme we use a protocol for a weak quantum one-out-of-two oblivious transfer.

arXiv:quant-ph/0605150•May 17, 2006•3 citations

Cheat Sensitive Quantum Bit Commitment

Lucién Hardy, Adrian Kent

We define cheat sensitive cryptographic protocols between mistrustful parties as protocols which guarantee that, if either cheats, the other has some nonzero probability of detecting the cheating. We describe an unconditionally secure cheat sensitive nonrelativistic bit commitment protocol which uses quantum information to implement a task which is classically impossible; we also describe a simple relativistic protocol.

arXiv:quant-ph/9911043•Physical Review Letters•Apr 16, 2004•108 citations

Lower bounds for quantum oblivious transfer

André Chailloux, Iordanis Kerenidis, Jamie Sikora

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest player's cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than $1/2$. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a bit commitment protocol and conclude by using lower bounds on quantum bit commitment. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most $3/4$. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

Quantum Information and Computation•Jan 1, 2013•37 citations

Lower bounds for Quantum Oblivious Transfer

André Chailloux, Iordanis Kerenidis, Jamie Sikora

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than $1/2$. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most $3/4$. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

Leibniz international proceedings in informatics•Jan 1, 2010•3 citations

Lower Bounds for Quantum Oblivious Transfer

André Chailloux, Iordanis Kerenidis, Jamie Sikora

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

arXiv:1007.1875•Jul 12, 2010•14 citations

A Computationally Secure Quantum Oblivious Transfer Scheme

Xin Lü, Zhi Ma, Dengguo Feng

Oblivious transfer is an important primitive in modern cryptography and is widely utilized in designing more complex protocols. In a one-out-of-two oblivious transfer, a party Alice has two messages x0, x1send to another party Bob in such a way that he can decide to obtain one of them at his choice but not both. In the literature (A. Kawachi et al., EUROCRYPT 2005, 268-284), the quantum states ppi+and ppi-are used as public keys to construct an encryption algorithm. In the paper, we further demonstrate that, for pi ne thetas, the quantum states ppiplusmnand pthetasplusmncan't been distinguished by quantum computers. Using this result, we devise a one-out-of-two oblivious transfer scheme, in which any cheating of the entities are detected at the end of the protocol. Correctness and privacy of this protocol are analyzed and results show that the proposed scheme is computationally secured

International Conference on Advanced Communication Technology•Jan 1, 2006•2 citations
We define (varepsilon,delta)(varepsilon,delta)(varepsilon,delta)-secure quantum computations between two parties that can play dishonestly to maximise advantage deltadeltadelta, however keeping small the probability varepsilonvarepsilonvarepsilon that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is (O(sqrtvarepsilon),varepsilon)(O(sqrt{varepsilon}),varepsilon)(O(sqrtvarepsilon),varepsilon)-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.
It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independently by Aharonov et al. [STOC, 2000] and Hardy and Kent [Phys. Rev. Lett. 92 (2004)] is investigated. In this variant, the parties require some nonzero probability of detecting a cheating, i.e. if Bob, who commits a bit b to Alice, changes his mind during the revealing phase then Alice detects the cheating with a positive probability (we call this property binding); and if Alice gains information about the committed bit before the revealing phase then Bob discovers this with positive probability (sealing). In our paper we give quantum bit commitment scheme that is simultaneously binding and sealing and we show that if a cheating gives epsilon advantage to a malicious Alice then Bob can detect the cheating with a probability Omega(epsilon^2). If Bob cheats then Alice's probability of detecting the cheating is greater than some fixed constant lambda>0. This improves the probabilities of cheating detections shown by Hardy and Kent and the scheme by Aharonov et al. who presented a protocol that is either binding or sealing, but not simultaneously both. To construct a cheat sensitive quantum bit commitment scheme we use a protocol for a weak quantum one-out-of-two oblivious transfer.
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest player's cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/21/21/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a bit commitment protocol and conclude by using lower bounds on quantum bit commitment. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/43/43/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/21/21/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/43/43/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.
Oblivious transfer is an important primitive in modern cryptography and is widely utilized in designing more complex protocols. In a one-out-of-two oblivious transfer, a party Alice has two messages x0, x1send to another party Bob in such a way that he can decide to obtain one of them at his choice but not both. In the literature (A. Kawachi et al., EUROCRYPT 2005, 268-284), the quantum states ppi+and ppi-are used as public keys to construct an encryption algorithm. In the paper, we further demonstrate that, for pi ne thetas, the quantum states ppiplusmnand pthetasplusmncan't been distinguished by quantum computers. Using this result, we devise a one-out-of-two oblivious transfer scheme, in which any cheating of the entities are detected at the end of the protocol. Correctness and privacy of this protocol are analyzed and results show that the proposed scheme is computationally secured