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

arXiv:2304.13200 · Quantum

Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming

Akshay Bansal, Jamie Sikora

Published Jan 20, 2025• 1 citation
arXivHTMLPDF

Abstract

In the last two decades, there has been much effort in finding secure protocols for two-party cryptographic tasks. It has since been discovered that even with quantum mechanics, many such protocols are limited in their security promises. In this work, we use stochastic selection, an idea from stochastic programming, to circumvent such limitations. For example, we find a way to switch between bit commitment, weak coin flipping, and oblivious transfer protocols to improve their security. We also use stochastic selection to turn trash into treasure yielding the first quantum protocol for Rabin oblivious transfer.

DOI
10.22331/q-2025-01-20-1602

Related papers

Simple, Near-Optimal Quantum Protocols for Die-Rolling

Jamie Sikora

Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols that are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling that have decent (and sometimes optimal) security, which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols that are very close to Kitaev’s lower bound for any D ≥ 3 . Lastly, we briefly discuss an application of this work to the quantum state discrimination problem.

arXiv:1605.08156•Cryptography•Jul 8, 2017•8 citations

Adversarial Two-Party Quantum Interactions in Cryptography and Machine Learning

Bansal, Akshay

Two-party adversarial interactions are of fundamental importance in the study of cryptography and machine learning, as they allow us to work in dynamic environments to model and adapt to various challenges, fostering reliability and robustness. In this thesis, we first consider such interactions in the domain of information-theoretic cryptography, where we propose new protocols and security bounds involving various two-party primitives such as coin flipping, bit commitment, and variants of oblivious transfer. We begin by developing the mathematical framework of stochastic selection, which is potentially useful for devising new protocols with improved security for a combination of various tasks. We then use this idea to develop the first protocols for Rabin oblivious transfer that offer partial information-theoretic security and also provide a non-trivial lower bound on its security. We also relax some of the more commonly used assumptions to consider the security of protocols in broader compositions and independently, allowing for devices that may be potentially malicious. In the former setting, we demonstrate that the weak coin flipping task -- which enjoys almost perfect standalone security -- may not be immune to attacks when used in larger compositions. In the latter, we establish the impossibility of determining the inner workings of a shared quantum mechanical device -- a phenomenon commonly known as self-testing -- in the presence of an adversary. Finally, we consider a slightly different task in a similar setting, where we discuss the classical online learnability of various quantum objects. We prove a sublinear regret bound for learning over general subsets of positive semidefinite matrices via the regularized follow-the-leader algorithm and apply it to various settings involving the learning of quantum objects. For concrete applications, we present a sublinear regret bound for learning quantum states, effects, channels, interactive measurements, strategies, co-strategies, and collections of inner products of pure states. In proving our regret bound, we establish various matrix analysis results useful in quantum information theory, including a generalization of Pinsker's inequality for arbitrary positive semidefinite operators with possibly different traces, which may be of independent interest in the study of more general classes of divergences.

•Jun 10, 2025•0 citations

Applications of Semidefinite Programming in Quantum Cryptography

Jamie Sikora

Coin-flipping is the cryptographic task of generating a random coin-flip between two mistrustful parties. Kitaev discovered that the security of quantum coin-flipping protocols can be analyzed using semidefinite programming. This lead to his result that one party can force a desired coin-flip outcome with probability at least 1/√2. \n \nWe give sufficient background in quantum computing and semidefinite programming to understand Kitaev's semidefinite programming formulation for coin-flipping cheating strategies. These ideas are specialized to a specific class of protocols singled out by Nayak and Shor. We also use semidefinite programming to solve for the maximum cheating probability of a particular protocol which has the best known security. \n \nFurthermore, we present a family of protocols where one party has a greater probability of forcing an outcome of 0 than an outcome of 1. We also discuss a computer search to find specific protocols which minimize the maximum cheating probability.

•May 18, 2007•0 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•2 citations

Quantum Protocols for Rabin Oblivious Transfer

Erika Andersson, Bansal, Akshay, Peat, James T. +2 more

Rabin oblivious transfer is the cryptographic task where Alice wishes to receive a bit from Bob but it may get lost with probability 1/2. In this work, we provide protocol designs which yield quantum protocols with improved security. Moreover, we provide a constant lower bound on any quantum protocol for Rabin oblivious transfer. To quantify the security of this task with asymmetric cheating definitions, we introduce the notion of cheating advantage which may be of independent interest in the study of other asymmetric cryptographic primitives.

arXiv:2507.04015•Leibniz international proceedings in informatics•Jan 1, 2025•0 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•4 citations
In the last two decades, there has been much effort in finding secure protocols for two-party cryptographic tasks. It has since been discovered that even with quantum mechanics, many such protocols are limited in their security promises. In this work, we use stochastic selection, an idea from stochastic programming, to circumvent such limitations. For example, we find a way to switch between bit commitment, weak coin flipping, and oblivious transfer protocols to improve their security. We also use stochastic selection to turn trash into treasure yielding the first quantum protocol for Rabin oblivious transfer.
Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols that are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling that have decent (and sometimes optimal) security, which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols that are very close to Kitaev’s lower bound for any D ≥ 3 . Lastly, we briefly discuss an application of this work to the quantum state discrimination problem.
Two-party adversarial interactions are of fundamental importance in the study of cryptography and machine learning, as they allow us to work in dynamic environments to model and adapt to various challenges, fostering reliability and robustness. In this thesis, we first consider such interactions in the domain of information-theoretic cryptography, where we propose new protocols and security bounds involving various two-party primitives such as coin flipping, bit commitment, and variants of oblivious transfer. We begin by developing the mathematical framework of stochastic selection, which is potentially useful for devising new protocols with improved security for a combination of various tasks. We then use this idea to develop the first protocols for Rabin oblivious transfer that offer partial information-theoretic security and also provide a non-trivial lower bound on its security. We also relax some of the more commonly used assumptions to consider the security of protocols in broader compositions and independently, allowing for devices that may be potentially malicious. In the former setting, we demonstrate that the weak coin flipping task -- which enjoys almost perfect standalone security -- may not be immune to attacks when used in larger compositions. In the latter, we establish the impossibility of determining the inner workings of a shared quantum mechanical device -- a phenomenon commonly known as self-testing -- in the presence of an adversary. Finally, we consider a slightly different task in a similar setting, where we discuss the classical online learnability of various quantum objects. We prove a sublinear regret bound for learning over general subsets of positive semidefinite matrices via the regularized follow-the-leader algorithm and apply it to various settings involving the learning of quantum objects. For concrete applications, we present a sublinear regret bound for learning quantum states, effects, channels, interactive measurements, strategies, co-strategies, and collections of inner products of pure states. In proving our regret bound, we establish various matrix analysis results useful in quantum information theory, including a generalization of Pinsker's inequality for arbitrary positive semidefinite operators with possibly different traces, which may be of independent interest in the study of more general classes of divergences.
Coin-flipping is the cryptographic task of generating a random coin-flip between two mistrustful parties. Kitaev discovered that the security of quantum coin-flipping protocols can be analyzed using semidefinite programming. This lead to his result that one party can force a desired coin-flip outcome with probability at least 1/√2. \n \nWe give sufficient background in quantum computing and semidefinite programming to understand Kitaev's semidefinite programming formulation for coin-flipping cheating strategies. These ideas are specialized to a specific class of protocols singled out by Nayak and Shor. We also use semidefinite programming to solve for the maximum cheating probability of a particular protocol which has the best known security. \n \nFurthermore, we present a family of protocols where one party has a greater probability of forcing an outcome of 0 than an outcome of 1. We also discuss a computer search to find specific protocols which minimize the maximum cheating probability.
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.
Rabin oblivious transfer is the cryptographic task where Alice wishes to receive a bit from Bob but it may get lost with probability 1/2. In this work, we provide protocol designs which yield quantum protocols with improved security. Moreover, we provide a constant lower bound on any quantum protocol for Rabin oblivious transfer. To quantify the security of this task with asymmetric cheating definitions, we introduce the notion of cheating advantage which may be of independent interest in the study of other asymmetric cryptographic primitives.
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.