# Post Quantum Cryptographic Keys Generated with Physical Unclonable Functions
## 4 PUF-Based Key Distribution for PQC  
### PUF-Based Key Distribution for LWE Lattice Cryptography  
The proposed generic protocol to generate public-private key pairs with PUFs for LWE lattice cryptography is shown in Figure 6. The random number generator (a) is used for the generation of seed \(\mathbf{a_{\text{(i)}}}\), which is public information. However, Seed k that is needed for the generation of the private key \(\mathbf{S_{\text{(i)}}}\) is generated from the PUF. The outline of a protocol generating a key pair for LWE cryptography is the following:  
1. The CA uses a random numbers generator and hash function to be able to point at a set of addresses in the image of the PUF-i.
2. From these addresses, a stream of bits called Seed K' is generated by the CA.
3. The CA communicates to the Client (i), through a handshake, the instructions needed to find the same set of addresses in the PUF.
4. Client (i) uses the PUF to generate the stream of bits called Seed K. The two data streams Seed K and Seed K' are similar, however slightly differ from each other due to natural physical variations and drifts occurring in the PUFs.
5. [If needed, Client (i) applies error correcting codes to reduce the difference between Seed K and Seed K'; the corrected, or partially corrected, data stream is used to generate the vectors \(\mathbf{s_{\text{(i)}}}\) and \(\mathbf{s_{\text{(i)}}}\)]
6. Client (i) independently uses a random numbers generator (a) to generate a second data stream Seed \(\mathbf{a_{\text{(i)}}}\), which is used for the computation of the matrix \(\mathbf{A_{\text{(i)}}}\).
7. The vector \(\text{t}_{\text{(i)}}\) is computed: \(\mathbf{t_{\text{(i)}}}\gets\mathbf{A_{\text{(i)}}}\ \mathbf{s_{\text{(i)}}}+\mathbf{s_{\text{(i)}}}\).
8. The private key \(\mathbf{S_{\text{(i)}}}\) is \(\{\mathbf{s_{\text{(i)}}};\mathbf{s_{\text{(i)}}}\}\).
9. The public key \(\mathbf{P_{\text{(i)}}}\) is \(\{\mathbf{a_{\text{(i)}}};\mathbf{t_{\text{(i)}}}\}\).
10. Client (i) communicates to the CA, through the network, the public key \(\mathbf{P_{\text{(i)}}}\);
11. The CA uses a search engine to verify that \(\mathbf{P_{\text{(i)}}}\) is correct. The search engine initiates the validation by generating a public key from Seed \(\mathbf{a_{\text{(i)}}}\) and Seed K' with lattice cryptography codes. If the resulting public key is not \(\mathbf{P_{\text{(i)}}}\), an iteration process gradually injects errors into Seed K' and computes the corresponding public keys. The search converges when a match in the resulting public key is found, or when the CA concludes that the public key should be bad.
12. If the validation is positive, the public key \(\mathbf{P_{\text{(i)}}}\) is posted online by the RA.  
Figure 6: PUF-based key pair generation for learning with error (LWE). The private keys, i.e., vectors \(\mathbf{S_{\text{(i)}}}\) and \(\mathbf{s_{\text{(i)}}}\), are generated from the seed K that is extracted from the PUF. The matrix \(\mathbf{A_{\text{(i)}}}\) continues to be generated from a random number. The search engine of the CA has access to an image of the PUF, and can independently validate the validity of public key, which is posted by the RA for cloud-based transactions. A new key pair can be generated, and validated by the CA, at each handshake cycle.  
This protocol is applicable for single use key pairs that are generated for each transaction. The random number generators of the first step of the protocol can generate new data streams, which point at different portions of the PUFs, thereby triggering the generation of new key pairs. The search engine described above can benefit from noise injection and high-performance computing. The injection of noise in Seed K will make the search too difficult for CA, unless equipped with HPCs, or GPUs. This can preclude hostile CAs from participating.