Quantum permutation pad for universal quantum-safe cryptography

Abstract

Classical cryptographic techniques are currently under the growing quantum computing threat. New techniques that quantum computing algorithms cannot break are urgently needed. We present such an encryption method. It builds upon quantum permutation logic gates or quantum permutation pads. It is universal in that it can be equally employed on classical computers, today’s Internet, and the upcoming quantum Internet. While the cryptographic technique is formulated in a quantum computing framework, it does not rely on physical properties uniquely present at the quantum level, such as no-cloning or entanglement of data. It achieves with today’s technology a level of security comparable to what will be possible to attain with tomorrow’s quantum technology. The mathematics behind the cryptographic technique, quantum representations of a symmetric group over a computational basis, is surprisingly simple. However, the challenge faced by an adversary wishing to break the code is intractable and uninterpretable, a property of Shannon’s perfect secrecy. We believe that the cryptographic technique presented in this article can be used in several different ways and modes. It can be integrated into numerous current Internet protocols, or the Internet of Things, making them quantum safe. In addition, it can be used to transition to the upcoming Internet quantum technology smoothly.

Appendices

Appendix A: Quantum gate interpretation of QKD

Let us consider the one-qubit computational basis $\{ |0\rangle , |1\rangle \}$. QKD can be expressed by quantum gate operations. In the computational basis $B_1=\{ |0\rangle , |1\rangle \}$, encoding can be interpreted as the application the identity gate $I = \left( \begin{matrix} 1 &{} 0 \\ 0 &{} 1 \end{matrix} \right)$ to the basis vectors $|0\rangle =[1,0]^T$ and $|1\rangle =[0,1]^T$. The encoding in the Hadamard basis $B_2 = \{ |-\rangle , |+\rangle \}$, can be interpreted as of the application of the Hadamard gate $H = \frac{1}{\sqrt{2}}\left( \begin{matrix} 1 &{} 1 \\ 1 &{} -1 \end{matrix} \right)$. Encoding of $|0\rangle$ is performed by multiplying with the Hadamard gate, that is, $H|0\rangle =|+\rangle$. Similarly, the encoding $|1\rangle$ corresponds to the product $H|1\rangle =|-\rangle$.

Quantum encoding in the Hadamard basis is equivalent to the Hadamard gate operation on a state in the computational basis. It transforms basis vectors into states with superposition, for the purposes of secure communications. The receiver also applies the Hadamard gate to restore the superposition states back to a computational basis state, before measuring. A quantum state is prepared and measured in the computational basis, but a quantum gate transforms it into a superposition state for its secure communication. The reverse gate operation brings the superposition state back to its original state for measuring in the computational basis. However, a mismatched gate selection at the receiver leads to the measurement of a superposition state. This outcome must be avoided. Note that this interpretation of QKD uses two quantum gates, namely the identity gate (I) and Hadamard gate (H).

Appendix B: Symmetric group $S_2$

In $S_2$, the permutation matrices are $P_1= \left( \begin{matrix} 1 &{} 0 \\ 0 &{} 1 \end{matrix} \right)$ and $P_2= \left( \begin{matrix} 0 &{} 1 \\ 1 &{} 0 \end{matrix} \right)$ (ref. [46]). $P_1$ is also the identity permutation gate I, and $P_2$ is the Pauli permutation gate X.

Lemma 3

The Hadamard basis is the eigenbasis of $P_2$.

Proof

Permutation gate $P_2$ is equal to the sum $|+\rangle -|1\rangle$. $\square$

Appendix C: Key generation, encryption and decryption example

In the following example, classical key material is mapped to permutation gates, using Fisher–Yates shuffling algorithm. QPP is used for encryption and decryption. Security parameters n is 2 while M is 5. For the sake of simplicity, confusion and diffusion are omitted.

1.1 C.1 Encryption

Let us consider the plaintext Hello World as a toy example. Using an ASCII character table, the plaintext has the following binary representation:

$$\begin{aligned} \begin{array}{llllll} 01001000&{}\quad 01100101&{}\quad 01101100&{}\quad 01101100&{}\quad 01101111&{}\quad 00000000\\ 00100000&{}\quad 01010111&{}\quad 01101111&{}\quad 01110010&{}\quad 01101100&{}\quad 01100100 \end{array} \end{aligned}$$

The binary representation is segmented into two-bit segments with decimal values of segments as follows:

For this example, we use a simple permutation selection algorithm. Suppose that we have randomly selected five permutation matrices/gates:

$$\begin{aligned}&P_0= \begin{pmatrix} 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \end{pmatrix}, P_1= \begin{pmatrix} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \end{pmatrix}, P_2= \begin{pmatrix} 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 \end{pmatrix},\\&P_3= \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \end{pmatrix} \text{ and } P_4= \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \end{pmatrix} \end{aligned}$$

Mapping every decimal value 0, 1, 2, and 3 of input segments to the column vectors $|0\rangle =[1 0 0 0]^T$, $|1\rangle =[0 1 0 0]^T$, $|2\rangle =[0 0 1 0]^T$ and $|3\rangle =[0 0 0 1]^T$. Let us ignore the randomization for this simple example and also take the position of a dispatching segment modulo $M=5$ to be the dispatching index of QPP. Then, we perform $P_d$ $|m\rangle$ = $|c\rangle$ with m as the decimal value of the dispatching segment, the ciphertext decimal values $|c\rangle$ of segments are as follows:

The corresponding ciphertext binary representation is:

$$\begin{aligned} \begin{array}{llllll} 10101000&{}\quad 11000111&{}\quad 11011110&{}\quad 10010110&{}\quad 01100110&{}\quad 01100100\\ 00001001&{}\quad 11111011&{}\quad 11101011&{}\quad 01000001&{}\quad 10000000&{}\quad 11000101 \end{array} \end{aligned}$$

It is clearly shown that the bit randomness is improved: the number of zero bits is 53 and the number of one bits is 43 in the plaintext Hello World, but the number of zero bits is 49 and the number of one bits is 47 in the ciphertext.

1.2 C.2 Decryption

The corresponding inverse permutation gates are:

$$\begin{aligned}&P_0^T= \begin{pmatrix} 0 &{} 0 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \end{pmatrix}, P_1^T= \begin{pmatrix} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \end{pmatrix}, P_2^T= \begin{pmatrix} 0 &{} 0 &{} 0 &{} 1 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \end{pmatrix}, \\&P_3^T= \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \end{pmatrix} \text{ and } P_4^T= \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 0 &{} 0 \end{pmatrix} \end{aligned}$$

Decryption uses the same process as the encryption, but with transposed QPP and perform $P_d^T$ $|c\rangle = |m\rangle$. The application of every corresponding inverse permutation gate yields the original plaintext, in a decimal form:

It corresponds to the the ASCII binary:

$$\begin{aligned} \begin{array}{llllll} 01001000&{}\quad 01100101&{}\quad 01101100&{}\quad 01101100&{}\quad 01101111&{}\quad 00000000\\ 00100000&{}\quad 01010111&{}\quad 01101111&{}\quad 01110010&{}\quad 01101100&{}\quad 01100100 \end{array} \end{aligned}$$

That is the decrypted plaintext: Hello World.

The pre-shared key is a bit sequence. To achieve quantum-level security, the key length can be anything greater than 256 bits. The classical key material is expanded to determine a QPP pad. For 256 bits of entropy, a two-qubit QPP pad requires at least 56 permutation matrices with a classical key of 256 to 448 bits. A three-qubit QPP pad requires 17 permutation matrices with a key of 256 to 408 bits. A four-qubit QPP pad needs six permutation matrices with a key of 256 to 384 bits.