# Post Quantum Cryptographic Keys Generated with Physical Unclonable Functions
## 4 PUF-Based Key Distribution for PQC
### PUF-Based Key Distribution for NTRU Lattice Cryptography  
The protocol to generate key pairs from PUFs for NTRU cryptography is similar than the one presented above in Section 4.1 for LWE, see Figure 8. We are suggesting a method where the only source of randomness is the PUF, Seed **K**, to compute both the public key \(\textbf{P}\textbf{K}_{\text{(i)}}\), and the private key \(Sk_{\text{(i)}}\). In our implementation, Seed **K** feeds the hash functions SHA-3, and SHAKE, to generate a long stream of bits, then compute the two polynomials \(f_{\text{(i)}}\) and \(g_{\text{(i)}}\).  
As previously discussed in Section 2.3, the polynomials \(f_{\text{(i)}}\) and \(g_{\text{(i)}}\) are not always usable due to pre-conditions, therefore a scheme to try several possible ways of addressing the PUF has to be developed. One way is to implement a deterministic method that is known by both the client device and the CA, which can have a negative impact on the latencies. We preferred the solution driven by the client device that asks the CA to initiate new handshakes. The summary of the method used to generate the key pairs for NTRU cryptography is the following:  
1. The CA uses random numbers to point at a set of addresses in the image of the **PUF-i**.
2. From these addresses, a stream of bits called Seed \(\textbf{K}^{\prime}\) is generated by the CA.
3. The CA sends the handshake to the client (i) to find the same addresses.
4. Client (i) uses the PUF to generate Seed **K**.
5. Client (i) applies error correction to Seed **K** and generates the truncated polynomials \(f_{\text{(i)}}\) and \(g_{\text{(i)}}\).
6. Computation of \(\textbf{P}\textbf{(i)}\) and \(\textbf{F}\textbf{(i)}\) and verify that the pre-conditions are fulfilled.
7. If needed, ask for a new handshake and iterate.
8. The polynomial \(h_{\text{(i)}}\) is computed: \(h_{\text{(i)}}\leftarrow\text{p}\cdot f_{\text{(i)}}\cdot g_{\text{(i)}}\).
9. The private key \(Sk_{\text{(i)}}\) is \(\{\textbf{(i)}\}\); \(\textbf{P}\textbf{(i)}\).
10. The public key \(\textbf{P}\textbf{(i)}\) is \(h_{\text{(i)}}\).
11. Client (i) communicates to the CA, through the network, the public key \(h_{\text{(i)}}\).  
Figure 8: PUF-based key pair generation for NTRU. After each handshake, the polynomials \(g_{\text{(i)}}\) and \(f_{\text{(i)}}\) are generated from the Seed K that is extracted from the PUF. The public and private key pairs are computed from these two polynomials. The search engine of the CA can independently validate the validity of public key with the image of the PUF.  
The CA uses a search engine to verify that \(\mathbf{h_{(i)}}\) is correct.  
If the validation is positive, the public key \(\mathbf{h_{(i)}}\) is posted online by the RA.  
It is important to notice that steps six and seven of the proposed method, \"Computation of \(\mathbf{Fp}\)(i) and \(\mathbf{Fq}\)(i) and verify that the pre-conditions are fulfilled; if needed ask for a new handshake and iterate\", could be handled differently to minimize backward and forward communications cycles between the CA and the client device. One example of implementation is to have a pre-arranged way to modify the seed generated by the PUF and its image. When the CA fails to validate the public key, several pre-arranged modifications of Seed K' will be tested.