# Privately Generated Key Pairs for Post Quantum Cryptography in a Distributed Network
## 3 Privately Generated Key Pairs for Post-Quantum Cryptography
### PKI for Lattice-Based Digital Signature Algorithm (LWE)  
Standardized lattice-based post-quantum cryptographic algorithms with LWE such as Crystals-Dilithium are well suited to designing a variation of the scheme presented in the previous section. The public-private cryptographic key pair generation for a client device \"\(i\)\" is based on polynomial computations in a lattice ring. The knowledge of integer-based vector \(t_{i}\), and matrix \(A_{i}\) with \(t_{i}=A_{i}\Big{(}S_{(1)i}+S_{(2)i}\Big{)}\) hide the vector \(S_{(1)i}\) and the \"small\" vector of error \(S_{(2)i}\). With LWE algorithms, the private key is \(S_{k(i)}=(S_{(1)i};\ S_{(2)i})\) and the public key is \(P_{k(i)}=(t_{i};A_{i})\), as follows:  
1. A randomly picked seed \(a_{i}\) generates \(A_{i}\) with the extended function SHAKE. 2. A second randomly picked data seed \(b_{i}\) generates the vectors \(S_{(1)i}\) and \(S_{(2)i}\). 3. The vector \(t_{i}\) is computed: \(t_{i}\)\(\leftarrow\)\(A_{i}(S_{(1)i}+S_{(2)i})\). 4. Seed \(a_{i}\) and \(t_{i}\) become the public key \(P_{k(i)}\). 5. \(S_{(1)i}\) and \(S_{(2)i}\) become the private key \(S_{k(i)}\). The outline of the signing and verification procedure for Dilithium is as follows:  
1. Step 1--Signature: Generate a masking vector of polynomials \(y\). 2. Compute vector \(A.y\) and set \(w_{i}\) to be the high-order bits of the coefficients. 3. Create the challenge \(c\) as the hash of the message and \(w_{i}\). 4. Compute signature \(z=y+c.S_{(1)i}\). 5. If any coefficient of \(z\) is larger than a threshold, reject and restart at step 1. 6. If any coefficient of the low-order bits of \(A_{i}z-c.t_{i}\) is too large, reject and restart at step 1. 7. Verification: Compute \(w_{1}^{\prime}\) to be the high-order bits of \(A_{i}z-c.t_{i}\) and accept if \(c\) is the hash of the message and \(w_{1}^{\prime}\). Figure 4: Public key distribution and verification for DSA (generic). The proposed scheme leverages LWE algorithms in which the public keys consist of two connected elements, the seed \(a_{i}\) and vector \(t_{i}\). As shown in Figure 5, the root of trust only generates seed \(a_{i}\). The protocol includes the generation and sharing of the challenges Ch-CT from random number RNG#1. After recovery, both communicating parties have access to the same seed \(a_{i}\), hence, matrix \(A_{i}\). A second random number generates the secret key, i.e., vectors \(S_{(1)i}\) and \(S_{(2)i}\). The client device transmits \(t_{i}\), the message M, and the signature S, thereby allowing the CA to verify the signature while keeping the private key secret. The seed \(a_{i}\) is kept secret during the verification process to allow the CA to authenticate the client device and the full public key, which is released to a registration authority (RA). The protocol is outlined as follows:  
1. With RNG#1, the CA picks a random number to create challenges Ch-CT, which are sent over to the client devices through a public, i.e., unsecured, network. These challenges act as the instructions for the CRP mechanism in the form of bit streams. For additional security, the transmission of the challenges could be protected by encryption schemes and multi-factor authentication (MFA). 2. Client \(i\) uses these challenges and feeds this as input for the root of trust. The root of trust can be a hardware token integrated with a PUF, an image, a file containing biometric information about an individual, or a structured file. 3. From the root of trust and the CRP mechanism, client \(i\) generates responses of seed \(a_{i}\) and sends the hashed message digest H(\(a_{i}\)) to the CA. An example of a hash function is SHA-3. 4. The CA will produce \(a_{i}^{\prime}\) from the CryptoTable that is approximately identical to \(a_{i}\). A search engine such as the RBC can recognize \(a_{i}\) by matching the hashed message digest of \(a_{i}^{\prime}\) with H(\(a_{i}\)) and variations of \(a_{i}^{\prime}\) located at short hamming distances from \(a_{i}\).