# Privately Generated Key Pairs for Post Quantum Cryptography in a Distributed Network
## 3 Privately Generated Key Pairs for Post-Quantum Cryptography
### Generic Digital Signature Algorithm  
This section describes a generic mechanism that can strengthen the current PKI system and give clients the authority to generate key pairs rather than relying on the CA. Then, we describe a specific algorithm developed around the learning with errors (LWE)-based lattice cryptography and the standardized Dilithium algorithm. Figure 4 summarizes the proposed generic protocol that can work with all the classical Digital Signature Algorithms (DSAs). The CA controls the validity of client devices through a root of trust while the client generates independently the key pairs. The outline of the protocol for public key distribution and verification for DSAs is as follows:  
1. The CA picks a random number to create challenges that are sent over to client devices through a public, i.e., unsecured, network. These challenges act as the instructions for a 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, as described, for example, in Figure 3.
3. From the root of trust and the CRP mechanism, client \(i\) generates responses \(K_{e}(i)\) and sends the hashed message digest \(\mathrm{H}(K_{e}(i))\) to the CA. An example of a hash function is SHA-3.
4. The CA produces \(K_{e}(i)^{\prime}\) from the CryptoTable that is approximately identical to \(K_{e}(i)\). A search engine such as the RBC can recognize \(K_{e}(i)\) by matching the hashed message digest of \(K_{e}(i)^{\prime}\) with \(\mathrm{H}(K_{e}(i))\) and variations of \(K_{e}(i)^{\prime}\) located at short hamming distances from \(K_{e}(i)\). Clients without a valid root of trust cannot generate a recognizable response \(K_{e}(i)\); thus, the method allows the CA to authenticate client \(i\).
5. The client generates a public-private key pair (\(P_{k}(i)\), \(S_{k}(i)\)) by using its own random number generator and an agreed-upon asymmetrical algorithm.
6. Client \(i\) generates a message (M) and performs an agreed-upon concatenation operation with \(K_{e}(i)\) and hashes the result to obtain \(\mathrm{H}(M||K_{e}(i))\).
7. Client \(i\) creates the signature by signing the message digest with the secret key \(S_{k}(i)\) and using the agreed-upon DSAs: S = Sign(\(\mathrm{H}(M||K_{e}(i))\), \(S_{k}(i)\)).
8. Client \(i\) sends M, S, and \(P_{k}(i)\) to the CA.  
The CA authenticates client \(i\) and verifies the digital signature by using the corrected response \(K_{e}(i)\), and independently computing S\({}^{\prime}\)= H\((M||K_{e}(i))\). The CA uses S\({}^{\prime}\) and the public key \(P_{k}(i)\) to verify S.  
If the CA successfully verifies client \(i\), the RA publishes the public key \(P_{k}(i)\).  
As needed, the CA can transmit back S\({}^{\prime}\) to client i to complete a two-way authentication scheme, allowing the client to verify the authenticity of the CA.