3 Preliminaries
3.1 Notation; entropic quantities
Random variables are written in uppercase and their realizations in lowercase. The statistical distance between random variables \(X,Y\in {{\mathcal {X}}}\) is given by \(\Delta (X,Y)={\textstyle \frac{1}{2}}\sum _{a\in {{\mathcal {X}}}}|\textrm{Pr}[X=a]-\textrm{Pr}[Y=a]|\). Expectation over a random variable X is written as \({{\mathbb {E}}}_x f(x)=\sum _{x\in {{\mathcal {X}}}} \textrm{Pr}[X=x]f(x)\). The collision probability of X is \(\sum _{x\in {{\mathcal {X}}}}\textrm{Pr}[X=x]^2\). The Rényi entropy of order \(\alpha \) (with \(\alpha \ne 1\)) is defined as \({\textsf{H}}_\alpha (X)= (1-\alpha )^{-1}\log (\sum _{x}\textrm{Pr}[X=x]^\alpha )\). Special cases are the collision entropy \({\textsf{H}}_2(X)=-\log (\sum _{x}\textrm{Pr}[X=x]^2)\) and the min-entropy \({\textsf{H}}_{\textrm{min}}(X)={\textsf{H}}_\infty (X)=-\log (\max _x \textrm{Pr}[X=x])\).
We denote the space of density matrices on Hilbert space \({{\mathcal {H}}}\) as \({{\mathcal {D}}}({{\mathcal {H}}})\). The single-qubit Hilbert space is denoted as \({{\mathcal {H}}}_2\). A bipartite state comprising subsystems ‘A’ and ‘B’ is written as \(\rho ^{\textrm{AB}}\in {{\mathcal {D}}}({{\mathcal {H}}}_{\textrm{A}}\otimes {{\mathcal {H}}}_{\textrm{B}})\). The state of a subsystem is obtained by taking the partial trace over the other subsystem, e.g. \(\rho ^{\textrm{A}}={\textrm{Tr}}\,_{\textrm{B}}\,\rho ^{\textrm{AB}}\). The identity operator on \({{\mathcal {H}}}\) is denoted by \(\mathbbm {1}^{{\mathcal {H}}}\); we will simply write \(\mathbbm {1}\) when the Hilbert space is clear from the context. Similarly, we write \(\tau ^{{\mathcal {H}}}\) for the maximally mixed state \(\mathbbm {1}^{{\mathcal {H}}}/\textrm{dim}({{\mathcal {H}}})\), often omitting the superscript. Let M be an operator with eigenvalues \(\lambda _i\). The Schatten 1-norm of M is given by \( \Vert M \Vert _1 ={\textrm{Tr}}\,\sqrt{M^{\dag }M}=\sum _i |\lambda _i|\). The trace distance between states \(\rho ,\sigma \) is \( \Vert \rho -\sigma \Vert _{\textrm{tr}}= {\textstyle \frac{1}{2}}\Vert \rho -\sigma \Vert _1\). We say that states are orthogonal, \(\rho \perp \sigma \), if their Frobenius inner product vanishes, \({\textrm{Tr}}\,\rho ^{\dag }\sigma =0\).
In the literature, there are multiple definitions of quantum conditional Rényi entropy. We will work with the definition of [
19,
20], which is based on sandwiched relative entropy, and which has been shown in [
21] to possess the most favorable properties. Let
\(\rho ,\sigma \ge 0\) with
\(\rho \ne 0\), and
\(\alpha \in (0,1)\cup (1,\infty )\). The sandwiched quantum Rényi relative entropy is given by
$$\begin{aligned} D_{\alpha }(\rho ||\sigma ) {\mathop {=}\limits ^{{\textrm{def}}}}\frac{1}{\alpha -1}\log {\textrm{Tr}}\,\Big [\Big ( \sigma ^{{\textstyle \frac{1-\alpha }{2\alpha }}} \rho \, \sigma ^{{\textstyle \frac{1-\alpha }{2\alpha }}} \Big )^{\alpha } \Big ] \end{aligned}$$
(1)
if
\(\sigma \gg \rho \,\vee \, (\alpha <1 \wedge \rho \not \perp \sigma )\), and otherwise
\(D_{\alpha }(\rho ||\sigma )=\infty \). Here
\(\sigma \gg \rho \) denotes that
\(\sigma \) dominates
\(\rho \), i.e. that the kernel of
\(\sigma \) is contained in the kernel of
\(\rho \). For
\(\alpha \in (0,1)\cup (1,\infty )\) and
\(\rho ^{\textrm{AE}}\in {{\mathcal {D}}}({{\mathcal {H}}}_A\otimes {{\mathcal {H}}}_E)\), the conditional quantum Rényi entropy is given by
$$\begin{aligned} {\textsf{H}}_{\alpha }(A|E)_\rho {\mathop {=}\limits ^{{\textrm{def}}}}-\inf _{\sigma \in {{\mathcal {D}}}({{\mathcal {H}}}_E)} D_\alpha (\rho ^{\textrm{AE}}|| \mathbbm {1}^{A}\otimes \sigma ). \end{aligned}$$
(2)
In the limit
\(\alpha \rightarrow \infty \) this reproduces the conditional Rényi entropy as introduced by Renner [
10],
$$\begin{aligned} {\textsf{H}}_{\textrm{min}}(A|E)_\rho =\sup _{\sigma \in {{\mathcal {D}}}({{\mathcal {H}}}_E)} -\log \min \{\lambda \,|\, \lambda \mathbbm {1}^{A}\otimes \sigma -\rho ^{\textrm{AE}}\ge 0\}. \end{aligned}$$
(3)
3.2 Security definitions and useful lemmas
Entropic security of an encryption scheme is formulated as the property that the encryption
Enc hides all functions of the plaintext
X. ‘Hiding’ means that an adversary
\({{\mathcal {A}}}\) who sees the ciphertext has no advantage in guessing function values
f(
X) over an adversary
\({{\mathcal {A}}}'\) who does not observe the ciphertext. Here the function
f is fixed
before \({{\mathcal {A}}}\) observes the ciphertext. This is phrased in [
6] as: ‘The probabilistic map leaks no
a priori information about
X’.
An encryption scheme is
\((t,\varepsilon )\)-entropically secure if
\(Y(\cdot )={\textsf{Enc}}(K,\cdot )\) satisfies Def.
3.3. The definition is similar to semantic security, but it works with unbounded adversaries and is restricted to high-entropy plaintext.
It has been shown that entropic security implies statistical indistinguishability and vice versa, with small modifications in the t and \(\varepsilon \) parameters. Indistinguishability is defined by the existence of a variable G such that a ciphertext resulting from random X (from some distribution) and random K is \(\varepsilon \)-close to G in terms of statistical distance.
Note that Def.
3.7 allows the cipherstate space to be larger than the plaintext space,
\(\dim {{\mathcal {H}}}' > \dim {{\mathcal {H}}}\). We will be working with the special case where the cipherstate consists of a quantum state of the same dimension as the input, accompanied by classical information.
The effect of the encryption, with the key unknown to the adversary, can be described as a completely positive trace-preserving (CPTP) map
\(R:{{\mathcal {D}}}({{\mathcal {H}}})\rightarrow {{\mathcal {D}}}({{\mathcal {H}}}')\) as follows,
$$\begin{aligned} R(\varphi ) = \sum _{k\in {{\mathcal {K}}}} \frac{1}{|{{\mathcal {K}}}|} {\textsf{Enc}}(k,\varphi ). \end{aligned}$$
(7)
If the plaintext state is entangled with Eve (E), e.g. the state is
\(\varphi ^{\textrm{AE}}\), then the encryption and decryption act only on the A subspace; we write
\(R(\rho ^{\textrm{AE}})\) for
\((R\otimes \mathbbm {1}^E)(\rho ^{\textrm{AE}})\). The definition of entropic security is more involved than in the classical case.
Here ‘interpretation’ means
\(\varphi ^{\textrm{AE}}=\sum _i p_i \sigma ^{\textrm{AE}}_i\). Def.
3.8 implies another definition of entropic security given in [
8] that contains an adversary
\({{\mathcal {A}}}'\) who gets access only to the own subsystem
\(\sigma _i^{\textrm{E}}\). Similar to the classical case, the equivalence has been shown between entropic security and entropic indistinguishability in the quantum setting.
3.3 The quantum one time pad
Let \({{\mathcal {H}}}_2\) denote the Hilbert space of a qubit. Let Z and X be single-qubit Pauli operators, in the standard basis given by \(Z={1\; 0\atopwithdelims ()0\;-1}\) and \(X={0\; 1\atopwithdelims ()1\;0}\). For QOTP encryption of one qubit, the key consists of two bits \(s,q\in \{0,1\} \). The encryption of a state \(\varphi \in {{\mathcal {D}}}({{\mathcal {H}}}_2)\) is given by \(X^s Z^q \varphi Z^q X^s\). Decryption is the same operation as encryption, but with the order of applying the \(Z^q\) and \(X^s\) interchanged.
The simplest way to encrypt an
n-qubit state
\(\varphi \in {{\mathcal {D}}}({{\mathcal {H}}}_2^{\otimes n})\) is to encrypt each qubit independently. The QOTP key
\(\beta \) has length 2
n and can be expressed as
\(\beta =s\Vert q\), with
\(s,q\in \{0,1\} ^n\). In the rest of the paper we will use the following shorthand notation for the QOTP cipherstate,
$$\begin{aligned} F_\beta (\varphi )= U_\beta \varphi U_\beta ^{\dag }\quad \text{ where } U_\beta =\bigotimes _{i=1}^n X^{s_i}Z^{q_i}. \end{aligned}$$
(11)
Let
\({{\mathcal {H}}}_{A'}={{\mathcal {H}}}_A={{\mathcal {H}}}_2^{\otimes n}\) and let
\(\varphi ^{\textrm{AE}}\in {{\mathcal {D}}}({{\mathcal {H}}}_A \otimes {{\mathcal {H}}}_E)\) be a bipartite state. Encryption of the A subsystem is written as
\(F_\beta (\varphi ^{AE})= (U_\beta \otimes \mathbbm {1}^E) \varphi ^{\textrm{AE}} (U_\beta ^{\dag }\otimes \mathbbm {1}^E)\). For any
\(\varphi ^{\textrm{AE}}\) it holds that
$$\begin{aligned} \frac{1}{2^{2n}}\sum _{\beta \in \{0,1\} ^{2n}} F_\beta (\varphi ^{AE}) = \tau ^{\mathrm{A'}}\otimes \varphi ^{\textrm{E}}, \end{aligned}$$
(12)
i.e. Def.
3.9 is achieved with
\(t=-n\) and
\(\varepsilon =0\): no matter how entangled E is with A, from the adversary’s point of view the
\(A'\) subsystem is maximally mixed and entirely decoupled from E.
6 Complexity of the key expansion
We comment on the complexity of our key expansion compared to previous works. Complexity is typically quantified as the number of bit-AND operations; bit-XOR operations are considered to be much cheaper. Multiplication in GF
\((2^\nu )\) has time complexity
\({{\mathcal {O}}}(\nu \log \nu )\) [
23,
24] whereas GF
\((2^\nu )\) addition (subtraction) consists of
\(\nu \) bit-XOR operations. Mateer [
25] introduced an improved version of Schönhage’s multiplication algorithm [
26]. If
m is of the form
\(3^\kappa \) and
\(\kappa \) is a power of two, then multiplication of two elements in GF(
\(2^{2m}\)) requires
\( {\textstyle \frac{17}{3}}m\log _3 m\) bit-AND operations and at least
\({\textstyle \frac{52}{5}}m\log m \log (\log m) + {\textstyle \frac{3}{2}}m\log m - {\textstyle \frac{3}{2}}m+{\textstyle \frac{11}{2}}\sqrt{m}\) bit-XORs. If
\(\kappa \) is not a power of two, then the number of ANDs slightly increases to
\(6m\log _3 m\) while the bound on the XORs stays the same.
Entropically secure encryption.
Dodis and Smith’s key expansion for classical entropically-secure encryption [
6] makes use of a xor-universal hash function that is implemented by GF(
\(2^n\))-multiplying the key
\(k\in \{0,1\} ^\ell \) times a random string
\(i\in \{0,1\} ^n\). In contrast, our classical scheme has multiplication in GF
\((2^{\lambda })\), with
\(\lambda =\max (\ell ,n-\ell )\), and the concatenation with
k is for free. For short keys the speedup is modest; only when the key length
\(\ell \) is a sizeable part of
n does the speedup become interesting.
The situation is similar in the general quantum case with entanglement. The scheme of Desrosiers and Dupuis [
8] has a key expansion that is the same as in [
6] but for string length 2
n instead of
n. Again, our speedup from GF(
\(2^{2n}\))-multiplication to GF(
\(2^{2n-\ell }\)) is modest when the key is short.
Approximate randomization.
The case of approximate randomization corresponds to entropically secure encryption with \(t=0\), i.e. without entanglement between Eve and the plaintext state, but with no further guarantees about Eve’s (lack of) knowledge. The key size \(\ell \) is slightly larger than one-half of the extended length 2n, namely \(\ell =n+2\log {\textstyle \frac{1}{\varepsilon }}\). We consider \(n\gg 2\log {\textstyle \frac{1}{\varepsilon }}\) and neglect the term \(2\log {\textstyle \frac{1}{\varepsilon }}\). Our key expansion consists of one multiplication in GF(\(2^\ell \)) and one addition in GF(\(2^{2n-\ell }\)) or, since \(\ell \) asymptotically almost equals n, roughly speaking one multiplication and one addition in GF(\(2^n\)). With Mateer’s multiplication for general \(\kappa \), this yields a total cost of \(3 n\log _3 n - 3 n\log _3 2\) ANDs and \(\ge n\log n \{\frac{26}{5}\log \log \frac{n}{2} +\frac{3}{4}\}-n\{ \frac{26}{5}\log \log \frac{n}{2}+\frac{1}{2} \}\) \(+{{{\mathcal {O}}}}(\sqrt{n})\) XORs for our key expansion.
Next we consider the key expansion of [
13]. In [
13] the
\(\ell \)-bit key
k is multiplied by a string
\(\alpha \in \{0,1\}^{2n}\), and the multiplication is in GF(
\(2^{2n}\)). If we write
\(\alpha =L||R\) and take
\(\ell \approx n\) then this can be reorganized into the following steps: (i) a polynomial multiplication
\(k\cdot R\) without modular reduction; (ii) a polynomial multiplication
\(k\cdot L\) shifted by
n positions, resulting in a polynomial of degree at most 3
n, followed by GF(
\(2^{2n}\)) modular reduction; (iii) addition of the two above contributions. As we count two XORs per monomial that needs to be reduced
7, we see that the addition in step (iii) precisely compensates the missing reduction in step (i). Furthermore, the number of monomials that needs reducing in step (ii) is
n, which is the same as in GF(
\(2^n\)) multiplication. Hence the cost of computing
\(k\cdot \alpha \) equals the cost of two GF(
\(2^n\)) multiplications.
Since in GF(
\(2^n\)), multiplication is much more expensive than addition, we see that our key expansion is a factor 2 cheaper than [
13].
7 Implementation
Entropically secure encryption involves two main processes: key expansion and encryption. The encryption is a straightforward XOR operation in the classical case, and qubitwise Pauli operations in the classical case. The key expansion requires more work, namely the Galois field multiplication of the short key and the public string. This multiplication can be implemented in two steps. The first step is binary polynomial multiplication. The second step is modular reduction with an irreducible polynomial.
We have done some preliminary implementation work, without extensive optimization. Note that existing finite field implementations are optimized for much smaller inputs than what are dealing with. For the binary polynomial multiplication we have used the
gf2x
library (version 1.3.0) [
28]. It is suitable for flexible sizes and is faster than similar libraries. For the reduction, lists are available of irreducible polynomials for specific degrees but they go up to only around GF(
\(2^{18}\)) [
29]. We have used a class of irreducible polynomials and reduction algorithm proposed by Banegas et al. [
27]. It works for any length and requires fewer XORs than previous reduction algorithms.
Our preliminary experiments were done on an Intel Core i7-9750 H 2.60GHZ processor with 16GB RAM. For message length \(2^{26}\) bits and key length \(2^{14}\) bits, the polynomial multiplication takes 0.29 s, and reduction 0.47 s. When message is longer, \(2^{32}\) bits, and key has the same length, \(2^{14}\), the polynomial multiplication takes 44.29 s, and reduction 33.0 s. Optimization is left for future work.
8 Discussion
Our scheme achieves the same shortest key length
\(\ell =n-t+2\log \frac{1}{\varepsilon }\) reported in other studies, but with a more efficient key expansion. In the classical case, we achieve a reduction of the ciphertext size compared to the best-known [
6] scheme that has
fast key expansion.
It is interesting to note that the security proof in [
13] uses Fourier analysis and
\(\delta \)-biased families, and invokes Cayley graphs for intuition, whereas our proof is more straightforward. Furthermore, the security proof in [
8] uses an expansion in the Pauli basis, which we do not need.
All the definitions of entropic indistinguishability and entropic security put a condition on the min-entropy of the plaintext, whereas all the security proofs yield expressions that contain the collision entropy. It may be advantageous to work with modified definitions that put a condition on the collision entropy, since that is more easily met.
We briefly discuss the application of entropically secure encryption as a building block in various larger schemes. Consider for instance Quantum Key Distribution. QKD produces information-theoretically secure key material at a rate that depends on the quality of the quantum channel and the details of the QKD scheme. Depending on the amount of plaintext that needs to be encrypted, a QKD key may be employed as a one-time-pad or as a symmetric key in blockcipher/streamcipher encryption. The latter case would necessarily occur, e.g. when a plaintext data stream arrives at a higer rate (bit per second) than the QKD key generation rate. Then the encryption is computationally secure; this is perfectly legitimate but a bit disappointing given that the key exchange was information-theoretically secure. It is interesting to note that (classical) ESE can re-instate information-theoretic security when the \(\frac{n-t}{t}\) value of the plaintext stream is lower than the QKD key rate, e.g. in case of well compressed data. Our key expansion scheme yields a significant computational improvement over existing ESE schemes when the required key length for ESE is of the same order of magnitude as the plaintext length, e.g. \(n-t > n/2 \). Computational efficiency is important when one deals with gigabits-per-second data streams that need to be encrypted in realtime.
Furthermore, there are various quantum-cryptographic schemes that require encryption of quantum states, e.g. zero knowledge protocols, commitments, signing/authentication of quantum states [
30].
It is an interesting topic for future work to see how much they can gain from approximate randomization, and how relevant a factor 2 speedup would be.
Note that ESE should be used carefully, because it does not have composability [
6]. When ESE is used as a component in a larger scheme, security may be lost if the other components somehow cause a violation of ESE’s entropy condition. For this reason it is prudent to apply ESE in tandem with a computationally secure encryption scheme.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.