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:0907.4246

Sampling in a Quantum Population, and Applications

Niek J. Bouman, Serge Fehr

Published Jul 24, 2009• 11 citations
arXivHTMLPDF

Abstract

We propose a framework for analyzing classical sampling strategies for estimating the Hamming weight of a large string, when applied to a multi-qubit quantum system instead. The framework shows how to interpret such a strategy and how to define its accuracy when applied to a quantum system. Furthermore, we show how the accuracy of any strategy relates to its accuracy in its classical usage, which is well understood for the important examples. We show the usefulness of our framework by using it to obtain new and simple security proofs for the following quantum-cryptographic schemes: quantum oblivious-transfer from bit-commitment, and BB84 quantum-key-distribution.

DOI
10.48550/arxiv.0907.4246

Related papers

Quantum Sampling for Finite Key Rates in High Dimensional Quantum Cryptography

Keegan Yao, Walter O. Krawec, Jiadong Zhu

It has been shown recently that the framework of quantum sampling, as introduced by Bouman and Fehr, can lead to new entropic uncertainty relations highly applicable to finite-key cryptographic analyses. Here we revisit these so-called sampling-based entropic uncertainty relations, deriving newer, more powerful, relations and applying them to source-independent quantum random number generators and high-dimensional quantum key distribution protocols. Along the way, we prove several interesting results in the asymptotic case for our entropic uncertainty relations. These sampling-based approaches to entropic uncertainty, and their application to quantum cryptography, hold great potential for deriving proofs of security for quantum cryptographic systems, and the approaches we use here may be applicable to an even wider range of scenarios.

arXiv:2012.04151•IEEE Transactions on Information Theory•Jan 11, 2022•22 citations

Cryptography from quantum uncertainty in the presence of quantum side information

Niek J. Bouman

The thesis starts with a high-level introduction into cryptography and quantum mechanics. Chapter 2 gives a theoretical foundation by introducing probability theory, information theory, functional analysis, quantum mechanics and quantum information theory. Chapter 3, 4 and 5 are editions of work published earlier.\n\nIn Chapter 3, we present a quantum-information-theoretic tool to analyze random sampling in a quantum setting. In particular, we present two new rigorous security proofs that make use of our new sampling tool: one for BB84 quantum key distribution, and one for a quantum reduction from oblivious transfer (OT) to bit commitment.\n\nChapter 4 studies the problem of message authentication from a weak key (which is a key that is not uniformly random, e.g., a password) in a new scenario. In this scenario, the weak key is a one-time session key that is derived from a public source of randomness with the help of a long-term key (e.g., a password). We propose a new four-round protocol for message authentication from a weak (session) key. \n\nIn Chapter 5 we present a new entropic uncertainty relation and furthermore we consider the task of password-based identification. We devise a new quantum identification protocol that is secure in two security models simultaneously.

•Oct 1, 2008•0 citations

Quantum Key Distribution and String Oblivious Transfer in Noisy Channels

Dominic R ayers

We prove the unconditional security of a quantum key distribution (QKD) protocol on a noisy channel against the most general attack allowed by quantum physics. We use the fact that in a previous paper we have reduced the proof of the unconditionally security of this QKD protocol to a proof that a corresponding Quantum String Oblivious Transfer (String-QOT) protocol would be unconditionally secure against Bob if implemented on top of an unconditionally secure bit commitment schcmc. We prove a lemma that extends a security proof given by Yao for a (one bit) QOT protocol to this String-QOT protocol. This result and the reduction mentioned above implies the unconditional security of our QKD protocol despite our previous proof that unconditionally secure bit commitment schemes are impossible.

•Jan 1, 2002•17 citations

Adaptive Versus Non-Adaptive Strategies in the Quantum Setting with Applications

Frédéric Dupuis, Serge Fehr, Philippe Lamontagne +1 more

We prove a general relation between adaptive and non-adaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its “information content”. Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to non-adaptive attacks. We demonstrate the usefulness of this methodology with two examples. The first is a quantum bit commitment scheme based on 1-bit cut-and-choose . Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for two-party computation, this implies the universality of 1-bit cut-and-choose, and thus solves the main open problem of [ 9 ]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al . It was originally suggested as an unconditionally secure scheme, back when this was thought to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model. In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a non-adaptive version, which can be done by means of known techniques, and applying our main result. 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.

arXiv:1607.08168•Lecture notes in computer science•Jan 1, 2016•11 citations

Computational advantage of quantum random sampling

Dominik Hangleiter, Jens Eisert

Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.

arXiv:2206.04079•Reviews of Modern Physics•Jul 20, 2023•208 citations

Asymptotically secure All-or-nothing Quantum Oblivious Transfer

Ramij Rahaman

We present a device independently secure quantum scheme for p-threshold all-or-nothing oblivious transfer. Novelty of the scheme is that, its security does not depend -- unlike the usual case -- on any quantum bit commitment protocol, rather it depends on Hardy's argument for two-qubit system. This scheme is shown to be unconditionally secure against any strategy allowed by quantum mechanics. By providing a secure scheme for all-or-nothing quantum oblivious transfer, we have answered a long standing open problem, other than the quantum key distribution, whether there is any two-party quantum cryptographic protocol, which is unconditionally secure.

arXiv:2111.08484•Nov 16, 2021•2 citations
We propose a framework for analyzing classical sampling strategies for estimating the Hamming weight of a large string, when applied to a multi-qubit quantum system instead. The framework shows how to interpret such a strategy and how to define its accuracy when applied to a quantum system. Furthermore, we show how the accuracy of any strategy relates to its accuracy in its classical usage, which is well understood for the important examples. We show the usefulness of our framework by using it to obtain new and simple security proofs for the following quantum-cryptographic schemes: quantum oblivious-transfer from bit-commitment, and BB84 quantum-key-distribution.
It has been shown recently that the framework of quantum sampling, as introduced by Bouman and Fehr, can lead to new entropic uncertainty relations highly applicable to finite-key cryptographic analyses. Here we revisit these so-called sampling-based entropic uncertainty relations, deriving newer, more powerful, relations and applying them to source-independent quantum random number generators and high-dimensional quantum key distribution protocols. Along the way, we prove several interesting results in the asymptotic case for our entropic uncertainty relations. These sampling-based approaches to entropic uncertainty, and their application to quantum cryptography, hold great potential for deriving proofs of security for quantum cryptographic systems, and the approaches we use here may be applicable to an even wider range of scenarios.
The thesis starts with a high-level introduction into cryptography and quantum mechanics. Chapter 2 gives a theoretical foundation by introducing probability theory, information theory, functional analysis, quantum mechanics and quantum information theory. Chapter 3, 4 and 5 are editions of work published earlier.\n\nIn Chapter 3, we present a quantum-information-theoretic tool to analyze random sampling in a quantum setting. In particular, we present two new rigorous security proofs that make use of our new sampling tool: one for BB84 quantum key distribution, and one for a quantum reduction from oblivious transfer (OT) to bit commitment.\n\nChapter 4 studies the problem of message authentication from a weak key (which is a key that is not uniformly random, e.g., a password) in a new scenario. In this scenario, the weak key is a one-time session key that is derived from a public source of randomness with the help of a long-term key (e.g., a password). We propose a new four-round protocol for message authentication from a weak (session) key. \n\nIn Chapter 5 we present a new entropic uncertainty relation and furthermore we consider the task of password-based identification. We devise a new quantum identification protocol that is secure in two security models simultaneously.
We prove the unconditional security of a quantum key distribution (QKD) protocol on a noisy channel against the most general attack allowed by quantum physics. We use the fact that in a previous paper we have reduced the proof of the unconditionally security of this QKD protocol to a proof that a corresponding Quantum String Oblivious Transfer (String-QOT) protocol would be unconditionally secure against Bob if implemented on top of an unconditionally secure bit commitment schcmc. We prove a lemma that extends a security proof given by Yao for a (one bit) QOT protocol to this String-QOT protocol. This result and the reduction mentioned above implies the unconditional security of our QKD protocol despite our previous proof that unconditionally secure bit commitment schemes are impossible.
We prove a general relation between adaptive and non-adaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its “information content”. Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to non-adaptive attacks. We demonstrate the usefulness of this methodology with two examples. The first is a quantum bit commitment scheme based on 1-bit cut-and-choose . Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for two-party computation, this implies the universality of 1-bit cut-and-choose, and thus solves the main open problem of [ 9 ]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al . It was originally suggested as an unconditionally secure scheme, back when this was thought to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model. In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a non-adaptive version, which can be done by means of known techniques, and applying our main result. 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.
Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.
We present a device independently secure quantum scheme for p-threshold all-or-nothing oblivious transfer. Novelty of the scheme is that, its security does not depend -- unlike the usual case -- on any quantum bit commitment protocol, rather it depends on Hardy's argument for two-qubit system. This scheme is shown to be unconditionally secure against any strategy allowed by quantum mechanics. By providing a secure scheme for all-or-nothing quantum oblivious transfer, we have answered a long standing open problem, other than the quantum key distribution, whether there is any two-party quantum cryptographic protocol, which is unconditionally secure.