# Post Quantum Cryptographic Keys Generated with Physical Unclonable Functions
## 2 Lattice and Code-Based Post Quantum Cryptography
### Code-Based Cryptography  
Code-based algorithms such as Classic McEliece are implemented with binary Goppa codes, that is, Goppa codes with underlying computations in finite Galois fields **GF(2m)**. The parameters are an irreducible polynomial of degree \(\mathbf{t}\), field exponent \(\mathbf{m}\), and code length \(\mathbf{n}\). The resulting code has error-correction capability of \(\mathbf{t}\) errors, the information-containing part of the code word has a size of \(\mathbf{k}=\mathbf{n}-\mathbf{m}\times\mathbf{t}\) and has generator matrix \(\mathbf{G}\) with a size of \(\mathbf{k}\times\mathbf{n}\)[14,15]. The block diagram of Figure 3 is showing an example of public-private key generation for code-based cryptography, and client device i. 1. Seed \(\mathbf{a_{\text{(i)}}}\) is used to create a random invertible binary \(\mathbf{k}\times\mathbf{k}\) scrambling matrix \(\mathbf{S_{\text{(i)}}}\). 2. Seed \(\mathbf{b_{\text{(i)}}}\) is used to create a random \(\mathbf{n}\times\mathbf{n}\) permutation matrix \(\mathbf{P_{\text{(i)}}}\). 3. The public key \(\mathbf{Pk_{\text{(i)}}}=\mathbf{\hat{G}_{\text{(i)}}}\) is computed with the generator matrix \(\mathbf{G}\): \(\mathbf{\hat{G}_{\text{(i)}}}\gets\mathbf{S_{\text{(i)}}}\). \(\mathbf{G}\). \(\mathbf{P_{\text{(i)}}}\)
4. The private key \(\mathbf{S_{\text{(i)}}}\) is \(\{\mathbf{G};\mathbf{S_{\text{(i)}}}^{-1},\mathbf{P_{\text{(i)}}}^{-1}\}\). Given a generator matrix of a binary Goppa code \(\mathbf{G}\), an irreducible polynomial of degree \(\mathbf{t}\), the field exponent \(\mathbf{m}\), and the code length \(\mathbf{n}\), the encryption process involves the following steps:  
1. Create the public key, \(\mathbf{\hat{G}_{\text{(i)}}}\) as described above. 2. Multiply the message \(\mathbf{m}\) by \(\mathbf{\hat{G}_{\text{(i)}}}\), creating the ciphertext message \(\hat{m}\). 3. Add a random error vector \(\mathbf{e}\) of Hamming weight \(\mathbf{t}\) to \(\hat{m}\) to obtain the ciphertext \(\mathbf{c}\). Figure 2: Example of key generation for NTRU cryptography. The polynomials \(\mathbf{f_{\text{(i)}}}\) and \(\mathbf{g_{\text{(i)}}}\) and are generated from random number generators, from which the inverses \(\mathbf{F_{\text{(i)}}}\) and \(\mathbf{F_{\text{(i)}}}\) are computed. The public key \(\mathbf{h(\text{i})}\) is also computed from these polynomials. Given a ciphertext \(c\), a decoding algorithm, and the private key \(\{\mathbf{G};\)\(\mathbf{S_{(0)}}^{-1}\), \(\mathbf{P_{(0)}}^{-1}\}\), decryption involves the following steps:  
1. Compute \(\hat{c}=c\,\mathbf{P_{(i)}}^{-1}\). 2. Use the decoding algorithm to correct the errors to obtain \(\hat{m}\). 3. Obtain the original message by computing \(\mathbf{m}=\hat{m}.\mathbf{S_{(0)}}^{-1}\). One example of a decoding algorithm is [PERSON]'s algorithm. This algorithm calculates the error-locator polynomial which has roots corresponding with the locations of the error bits added to the encrypted message. This algorithm can be implemented as follows [25]:  
**Input:** Syndrome polynomial \(s\), Goppa polynomial g of degree \(t\)  
**Patterson (s, g):**  
1. \(\mathbf{t}=\mathbf{s}^{-1}\bmod\mathbf{g}\). 2. \(t=\sqrt{t+x}\). 3. Find polynomials \(a\), \(b\) such that \(\mathbf{b.t}\equiv\bmod\mathbf{g}\) with \(\deg(\mathbf{a})\leq\left\lvert\mathbf{t}/2\right\rvert\) and \(\deg(\mathbf{b})\leq\left\lvert\mathbf{(t}\mathbf{-}1)/2\right\rvert\) using the extended Euclidean algorithm. 4. Calculate and return the error locator polynomial, \(\mathbf{e}=\mathbf{a}^{2}+\mathbf{x.b}^{2}\). Once the error locator polynomial is found, the Berlekamp Trace Algorithm can be used to find the roots of the polynomial via factorization. These correspond to the locations of the error bits added to the message. The Berlekamp Trace Algorithm can be implemented as follows [26]:  
**Input:** Polynomial to factor \(p\), trace polynomial \(t\), basis index \(i\)  
**Berlekamp Trace (p, t, i):**  
1. if \(\deg(p)\leq 1\)
2. return the root of \(p\). 3. \(p_{0}=gcd(p,t(B_{\text{i}}.\ x))\). 4.