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:quant-ph/0612014

A Tight High-Order Entropic Quantum Uncertainty Relation With Applications

Ivan Damgaard, Serge Fehr, Renato Renner, Louis Salvail, Christian Schaffner

Published Dec 2, 2006• 1 citation
arXivHTMLPDF

Abstract

We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings. Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded quantum-storage model according to new strong security definitions. As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.

DOI
10.48550/arxiv.quant-ph/0612014

Related papers

Cryptography in the Bounded-Quantum-Storage Model

Christian Schaffner

This thesis initiates the study of cryptographic protocols in the bounded-quantum-storage model. On the practical side, simple protocols for Rabin Oblivious Transfer, 1-2 Oblivious Transfer and Bit Commitment are presented. No quantum memory is required for honest players, whereas the protocols can only be broken by an adversary controlling a large amount of quantum memory. The protocols are efficient, non-interactive and can be implemented with today's technology. On the theoretical side, new entropic uncertainty relations involving min-entropy are established and used to prove the security of protocols according to new strong security definitions. For instance, in the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers, the uncertainty relation allows to prove the security of QKD protocols while tolerating considerably higher error rates compared to the standard model with unbounded adversaries.

arXiv:0709.0289•Sep 3, 2007•8 citations

The Trivial Bound of Entropic Uncertainty Relations

Minu J. Bae

Entropic uncertainty relations are underpinning to compute the quantitative security bound in quantum cryptographic applications, such as quantum random number generation (QRNG) and quantum key distribution (QKD). All security proofs derive a relation between the information accessible to the legitimate group and the maximum knowledge that an adversary may have gained, Eve, which exploits entropic uncertainty relations to lower bound Eve's uncertainty about the raw key generated by one party, Alice. The standard entropic uncertainty relations is to utilize the smooth min- and max-entropies to show these cryptographic applications' security by computing the overlap of two incompatible measurements or positive-operator valued measures (POVMs). This paper draws one case of the POVM-versioned standard entropic uncertainty relation yielding the trivial bound since the maximum overlap in POVMs always produces the trivial value, "one." So, it fails to tie the smooth min-entropy to show the security of the quantum cryptographic application.

arXiv:2208.00242•Jul 30, 2022•0 citations

Min-entropy uncertainty relation for finite-size cryptography

Nelly H. Y. Ng, Mario Berta, Stephanie Wehner

Apart from their foundational significance, entropic uncertainty relations play a central role in proving the security of quantum cryptographic protocols. Of particular interest are therefore relations in terms of the smooth min-entropy for Bennett-Brassard 1984 (BB84) and six-state encodings. The smooth min-entropy ${H}_{\mathrm{min}}^{\ensuremath{\epsilon}}(X/B)$ quantifies the negative logarithm of the probability for an attacker $B$ to guess $X$, except with a small failure probability $\ensuremath{\epsilon}$. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove an alternative uncertainty relation in terms of the smooth min-entropy that is only marginally less strong but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of R\'enyi entropies that may be of independent interest.

arXiv:1205.0842•Physical Review A•Oct 15, 2012•58 citations

Cryptography in the Bounded-Quantum-Storage Model

Ivan Damgård, Serge Fehr, Louis Salvail +1 more

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient and noninteractive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

SIAM Journal on Computing•Jan 1, 2008•127 citations

Entropic Uncertainty for Biased Measurements

Walter O. Krawec

Entropic Uncertainty relations are powerful tools, especially in quantum cryptography. They typically bound the amount of uncertainty a third-party adversary may hold on a measurement outcome as a result of the measurement overlap. However, when the two measurement bases are biased towards one another, standard entropic uncertainty relations do not always provide optimal lower bounds on the entropy. Here, we derive a new entropic uncertainty relation, for certain quantum states, which can provide a significantly higher bound even if the two measurement bases are no longer mutually unbiased. We evaluate our bound on two different quantum cryptographic protocols, including BB84 with faulty/biased measurement devices, and show that our new bound can produce substantially higher key-rates under several scenarios when compared with prior work using standard entropic uncertainty relations.

arXiv:2305.09753•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•5 citations

Cryptography in the Bounded Quantum Storage Model

Ivan Damgård, Serge Fehr, Louis Salvail +1 more

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

BRICS Report Series•Jul 11, 2005•17 citations
We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings. Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded quantum-storage model according to new strong security definitions. As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.
This thesis initiates the study of cryptographic protocols in the bounded-quantum-storage model. On the practical side, simple protocols for Rabin Oblivious Transfer, 1-2 Oblivious Transfer and Bit Commitment are presented. No quantum memory is required for honest players, whereas the protocols can only be broken by an adversary controlling a large amount of quantum memory. The protocols are efficient, non-interactive and can be implemented with today's technology. On the theoretical side, new entropic uncertainty relations involving min-entropy are established and used to prove the security of protocols according to new strong security definitions. For instance, in the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers, the uncertainty relation allows to prove the security of QKD protocols while tolerating considerably higher error rates compared to the standard model with unbounded adversaries.
Entropic uncertainty relations are underpinning to compute the quantitative security bound in quantum cryptographic applications, such as quantum random number generation (QRNG) and quantum key distribution (QKD). All security proofs derive a relation between the information accessible to the legitimate group and the maximum knowledge that an adversary may have gained, Eve, which exploits entropic uncertainty relations to lower bound Eve's uncertainty about the raw key generated by one party, Alice. The standard entropic uncertainty relations is to utilize the smooth min- and max-entropies to show these cryptographic applications' security by computing the overlap of two incompatible measurements or positive-operator valued measures (POVMs). This paper draws one case of the POVM-versioned standard entropic uncertainty relation yielding the trivial bound since the maximum overlap in POVMs always produces the trivial value, "one." So, it fails to tie the smooth min-entropy to show the security of the quantum cryptographic application.
Apart from their foundational significance, entropic uncertainty relations play a central role in proving the security of quantum cryptographic protocols. Of particular interest are therefore relations in terms of the smooth min-entropy for Bennett-Brassard 1984 (BB84) and six-state encodings. The smooth min-entropy ${H}_{\mathrm{min}}^{\ensuremath{\epsilon}}(X/B)$ quantifies the negative logarithm of the probability for an attacker BBB to guess XXX, except with a small failure probability $\ensuremath{\epsilon}$. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove an alternative uncertainty relation in terms of the smooth min-entropy that is only marginally less strong but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of R\'enyi entropies that may be of independent interest.
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2n/2n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient and noninteractive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.
Entropic Uncertainty relations are powerful tools, especially in quantum cryptography. They typically bound the amount of uncertainty a third-party adversary may hold on a measurement outcome as a result of the measurement overlap. However, when the two measurement bases are biased towards one another, standard entropic uncertainty relations do not always provide optimal lower bounds on the entropy. Here, we derive a new entropic uncertainty relation, for certain quantum states, which can provide a significantly higher bound even if the two measurement bases are no longer mutually unbiased. We evaluate our bound on two different quantum cryptographic protocols, including BB84 with faulty/biased measurement devices, and show that our new bound can produce substantially higher key-rates under several scenarios when compared with prior work using standard entropic uncertainty relations.
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.