# Post Quantum Cryptographic Keys Generated with Physical Unclonable Functions
## 2 Lattice and Code-Based Post Quantum Cryptography
### Learning with Error Cryptography  
The LWE of the CVP problem was first introduced by [PERSON] [16]. The knowledge of integer-based vector \(\mathbf{t}\), and matrix \(\mathbf{A}\) with \(\mathbf{t}=\mathbf{A.s_{1}}\) cannot hide the vector \(\mathbf{s_{1}}\); however, the addition of a \"small\" vector of error \(\mathbf{s_{2}}\) with \(\mathbf{t}=\mathbf{A.s_{1}}+\mathbf{s_{2}}\), makes it hard to distinguish the vectors \(\mathbf{s_{1}}\) and \(\mathbf{s_{2}}\) from \(\mathbf{t}\). The vector \(\mathbf{s_{2}}\) needs to be small enough for the encryption/decryption cycles, but large enough to prevent a third party from uncovering the private key (\(\mathbf{s_{1}}\); \(\mathbf{s_{2}}\)) from the public information (\(\mathbf{t}\); \(\mathbf{A}\)). The public-private cryptographic key pair generation for client device i can be based on polynomial computations in a lattice ring, and is described in Figure 1:  
1. The generation of a first data stream called seed \(\mathbf{a_{(i)}}\) that is used for the key generation; in the case of LWE, the seed \(\mathbf{a_{(i)}}\) is shared openly in the network. 2. The generation of a second data stream called seed \(\mathbf{b_{(i)}}\) that is used to compute a second data stream for the private key \(\mathbf{S_{(i)}}\); the seed \(\mathbf{b_{(i)}}\) is kept secret. 3. The public key \(\mathbf{P_{(i)}}\) is computed from both data streams and is openly shared. 4. The matrix \(\mathbf{A_{(i)}}\) is generated from seed \(\mathbf{a_{(i)}}\). 5. The two vectors \(\mathbf{s_{1(i)}}\) and \(\mathbf{s_{2(i)}}\) are generated from seed \(\mathbf{b_{(i)}}\). 6. The vector \(\mathbf{t_{(i)}}\) is computed: \(\mathbf{t_{(i)}}\gets\mathbf{A_{(i)}}\)\(\mathbf{s_{1(i)}}+\mathbf{s_{2(i)}}\). 7. Both seed \(\mathbf{a_{(i)}}\) and \(\mathbf{t_{(i)}}\) become the public key \(\mathbf{P_{(i)}}\). 8. Both \(\mathbf{s_{1(i)}}\) and \(\mathbf{s_{2(i)}}\) become the private key \(\mathbf{S_{(i)}}\). A digital signature algorithm (DSA) can be realized from the LWE instance by first generating a public-private key pair as in Figure 1. The secret key is then used to sign a message, and the public key is used to verify this signed message. In CRYSTALS-Dilithium [8], the authors use a Fiat-Shamir with Aborts approach [17] for their signing and verification procedure. The outline of the signing procedure is as follows:  
1. Generate a masking vector of polynomials \(\mathbf{y}\). 2. Compute vector \(\mathbf{A.y}\) and set \(\mathbf{w_{1}}\) to be the high-order bits of the coefficients in this vector. 3. Create the challenge \(\mathbf{c}\), as the hash of the message and \(\mathbf{w_{1}}\). 4. Compute intermediate signature \(\mathbf{z}=\mathbf{y}+\mathbf{c.s_{1}}\). 5. Set parameter \(\mathbf{\beta}\) to be the maximum coefficient of \(\mathbf{c.s_{1}}\). 6. If any coefficient of \(\mathbf{z}\) is larger than \(\mathbf{\gamma_{1}}-\mathbf{\beta}\), then reject and restart at step 1. Figure 1: Example of public–private key generation for LWE based cryptography. The matrix \(\mathbf{A_{(i)}}\) and vectors \(\mathbf{S_{(i)}}\) and \(\mathbf{S_{2(i)}}\) are generated from random number generators. The vector \(\mathbf{t_{(i)}}\) is computed from these elements for the generation of the key pair. If any coefficient of the low-order bits of \(A.z-c.t\) is greater than \(\gamma_{2}-\beta\), then reject and restart at step 1. Note: \(\gamma_{1}\), \(\gamma_{2}\), and \(\beta\) are set such that the expected number of repetitions is between 4 and 7. The general outline of the verification procedure is given by the following: Compute \(w_{1}\)' to be the high-order bits of \(A.z-c.t\) and accept if all coefficients of \(z\) are less than \(\gamma_{1}-\beta\) and if \(c\) is the hash of the message and \(w_{1}\)'. Encapsulation allows for two parties to securely share a symmetric key by encapsulating the key in ciphertext. When both parties have the symmetric key, they are then able to use a symmetric-key encryption algorithm to communicate (e.g., AES).