© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0509169 · Journal of Mathematical Physics

On the optimality of quantum encryption schemes

Daniel Nagaj, Iordanis Kerenidis

Published Sep 1, 2006• 16 citations

Abstract

It is well known that n bits of entropy are necessary and sufficient to perfectly encrypt n bits (one-time pad). Even if we allow the encryption to be approximate, the amount of entropy needed does not asymptotically change. However, this is not the case when we are encrypting quantum bits. For the perfect encryption of n quantum bits, 2n bits of entropy are necessary and sufficient (quantum one-time pad), but for approximate encryption one asymptotically needs only n bits of entropy. In this paper, we provide the optimal trade-off between the approximation measure ϵ and the amount of classical entropy used in the encryption of single quantum bits. Then, we consider n-qubit encryption schemes which are a composition of independent single-qubit ones and provide the optimal schemes both in the 2- and the ∞-norm. Moreover, we provide a counterexample to show that the encryption scheme of Ambainis-Smith [Proceedings of RANDOM ’04, pp. 249–260] based on small-bias sets does not work in the ∞-norm.

DOI: 10.1063/1.2339014

Related papers

Approximate quantum encryption with even shorter keys

Temel, Mehmet, Boris Škorić

Perfect encryption of a qubit state using the Quantum One-Time Pad (QOTP) requires 2 classical key bits. More generally, perfect QOTP encryption of a $2^n$-dimensional state requires $2n$ classical bits. However, almost-perfect encryption, with information-theoretic security, can be achieved with only little more than $1$ key bit per qubit. In this paper we slightly improve the key length. We show that key length $n+\frac23\log\frac1\varepsilon$ suffices to encrypt $n$ qubits in such a way that the cipherstate has trace distance $\leq\varepsilon$ from the fully mixed state. The previous best result was $n+2\log\frac1\varepsilon$. Similar to the previous literature, we expand the key to a $2n$-bit pseudorandom string which is then used as a QOTP key. In this expansion we make use of $2n$ bits of public randomness which are included as a classical part of the cipherstate. Our key expansion is slightly faster than in previous works.

•Jan 1, 2022•1 citation

Comment on “Optimal encryption of quantum bits”

Xiangfu Zou, Daowen Qiu

Boykin and Roychowdhury [Phys. Rev. A 67, 042317 (2003)] discussed the optimal encryption of quantum bits, gave a necessary and sufficient condition (NASC) for the security of quantum encryption, and suggested an optimal quantum one-time pad encryption scheme. In this Comment, we point out that the proof of the NASC for the security of quantum encryption is not correct. Moreover, we reprove the NASC for the security of quantum encryption.

Physical Review A•Aug 27, 2013•1 citation

Private Quantum Channels and the Cost of Randomizing Quantum Information

Michele Mosca, Alain Tapp, Ronald de Wolf

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme. From the point of view of the eavesdropper, this encryption process can be seen as a randomization of the original state. We thus also obtain strict bounds on the amount of entropy necessary for randomizing n qubits.

arXiv:quant-ph/0003101•Mar 22, 2000•26 citations

Optimality of private quantum channels

Jan Bouda, Mário Ziman

We addressed the question of optimality of private quantum channels. We have shown that the Shannon entropy of the classical key necessary to securely transfer the quantum information is lower bounded by the entropy exchange of the private quantum channel $\cal E$ and von Neumann entropy of the ciphertext state $\varrho^{(0)}$. Based on these bounds we have shown that decomposition of private quantum channels into orthogonal unitaries (if exists) is optimizing the entropy. For non-ancillary single qubit PQC we have derived the optimal entropy for arbitrary set of plaintexts. In particular, we have shown that except when the (closure of the) set of plaintexts contains all states, one bit key is sufficient. We characterized and analyzed all the possible single qubit private quantum channels for arbitrary set of plaintexts. For the set of plaintexts consisting of all qubit states we have characterized all possible approximate private quantum channels and we have derived the relation between the security parameter and the corresponding minimal entropy.

arXiv:0710.2004•Journal of Physics A Mathematical and Theoretical•Apr 30, 2007•10 citations

Weak approximate unitary designs and applications to quantum encryption

Cécilia Lancien, Christian Majenz

Unitary t -designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary t -designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling dtpoly(t,log⁡d,1/ϵ) unitaries from an exact t -design provides with positive probability an ϵ -approximate t -design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.

arXiv:1911.06742•Quantum•Aug 28, 2020•11 citations

Optimal encryption of quantum bits

P. Oscar Boykin, Vwani Roychowdhury

We show that $2n$ random classical bits are both necessary and sufficient for encrypting any unknown state of n quantum bits in an informationally secure manner. We also characterize the complete set of optimal protocols in terms of a set of unitary operations that comprise an orthonormal basis in a canonical inner product space. Moreover, a connection is made between quantum encryption and quantum teleportation that allows for a different proof of optimality of teleportation.

arXiv:quant-ph/0003059•Physical Review A•Apr 22, 2003•339 citations

It is well known that n bits of entropy are necessary and sufficient to perfectly encrypt n bits (one-time pad). Even if we allow the encryption to be approximate, the amount of entropy needed does not asymptotically change. However, this is not the case when we are encrypting quantum bits. For the perfect encryption of n quantum bits, 2n bits of entropy are necessary and sufficient (quantum one-time pad), but for approximate encryption one asymptotically needs only n bits of entropy. In this paper, we provide the optimal trade-off between the approximation measure ϵ and the amount of classical entropy used in the encryption of single quantum bits. Then, we consider n-qubit encryption schemes which are a composition of independent single-qubit ones and provide the optimal schemes both in the 2- and the ∞-norm. Moreover, we provide a counterexample to show that the encryption scheme of Ambainis-Smith [Proceedings of RANDOM ’04, pp. 249–260] based on small-bias sets does not work in the ∞-norm.

Perfect encryption of a qubit state using the Quantum One-Time Pad (QOTP) requires 2 classical key bits. More generally, perfect QOTP encryption of a

2^n

-dimensional state requires

2n

classical bits. However, almost-perfect encryption, with information-theoretic security, can be achieved with only little more than

1

key bit per qubit. In this paper we slightly improve the key length. We show that key length

n+\frac23\log\frac1\varepsilon

suffices to encrypt

n

qubits in such a way that the cipherstate has trace distance

\leq\varepsilon

from the fully mixed state. The previous best result was

n+2\log\frac1\varepsilon

. Similar to the previous literature, we expand the key to a

2n

-bit pseudorandom string which is then used as a QOTP key. In this expansion we make use of

2n

bits of public randomness which are included as a classical part of the cipherstate. Our key expansion is slightly faster than in previous works.

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme. From the point of view of the eavesdropper, this encryption process can be seen as a randomization of the original state. We thus also obtain strict bounds on the amount of entropy necessary for randomizing n qubits.

We addressed the question of optimality of private quantum channels. We have shown that the Shannon entropy of the classical key necessary to securely transfer the quantum information is lower bounded by the entropy exchange of the private quantum channel

\cal E

and von Neumann entropy of the ciphertext state

\varrho^{(0)}

. Based on these bounds we have shown that decomposition of private quantum channels into orthogonal unitaries (if exists) is optimizing the entropy. For non-ancillary single qubit PQC we have derived the optimal entropy for arbitrary set of plaintexts. In particular, we have shown that except when the (closure of the) set of plaintexts contains all states, one bit key is sufficient. We characterized and analyzed all the possible single qubit private quantum channels for arbitrary set of plaintexts. For the set of plaintexts consisting of all qubit states we have characterized all possible approximate private quantum channels and we have derived the relation between the security parameter and the corresponding minimal entropy.

Unitary t -designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary t -designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling dtpoly(t,log⁡d,1/ϵ) unitaries from an exact t -design provides with positive probability an ϵ -approximate t -design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.

We show that

2n

random classical bits are both necessary and sufficient for encrypting any unknown state of n quantum bits in an informationally secure manner. We also characterize the complete set of optimal protocols in terms of a set of unitary operations that comprise an orthonormal basis in a canonical inner product space. Moreover, a connection is made between quantum encryption and quantum teleportation that allows for a different proof of optimality of teleportation.