## 2 Literature Review
### Falcon
**Key generation:** Algorithm 7 outlines the process of generating FALCON key pairs, which involves computing polynomials \(f\), \(g\), \(F\), \(G\), and \(h\) based on specific equations. These equations define relationships between the polynomials, ensuring the integrity of the generated keys. To calculate these polynomials, a random number is generated which serves as a seed for initializing shake256. By using shake256 random numbers, the algorithm generates random polynomials \(f\) and \(g\) with a Gaussian distribution. If the squared norm of these polynomials exceeds predefined bounds or if the orthogonalized vector norms deviate from expected values, new polynomials are generated. The orthogonalized vector norm computation employs the fast Fourier transform (FFT) for efficiency. The equations guiding the polynomial computation are as follows:  
\[fG-gF=q\mod\phi \tag{2}\]  
\[h=gf^{-1}\mod(\phi,q) \tag{3}\]  
Having obtained the \(f\) and \(g\) polynomials, the algorithm proceeds to compute the public key polynomial \(h\), fulfilling the requirements of the first equation. Additionally, it solves the second equation (NTRU equation) to derive polynomials \(F\) and \(G\). For the \(sk\), the algorithm sequentially encodes the \(f\), \(g\), \(F\), and \(G\) polynomials. Meanwhile, \(pk\) is encoded by representing the polynomial \(h\). Ultimately, the algorithm generates both the \(sk\) and \(pk\), ensuring the cryptographic integrity of the Falcon scheme. **Signature generation:** Algorithm 8 outlines the steps for generating signatures in the FALCON scheme. It begins by generating a random seed for the hash function, followed by initializing the shake256 function with this seed. Subsequently, the algorithm computes a hash digest \(c\) from the salt \(r\) and the input message \(m\). Next, \(sk\), previously encoded during key generation, is decoded to retrieve the polynomials \(f\), \(g\), \(F\), and \(G\). If \(G\) is not extracted from \(sk\), the algorithm calculates it. Leveraging these polynomials, the algorithm computes two short vectors \(s_{1}\) and \(s_{2}\) satisfying \(s_{1}\equiv s_{2}h\mod q\), all while keeping \(sk\) hidden. The short vector \(s_{2}\) is then encoded and concatenated with the signature length, salt, message, and encoded \(s_{2}\). These concatenated data are stored in the signature (\(sig\)). This process ensures the secure generation of FALCON signatures while maintaining the confidentiality of \(sk\). ```
A message m, a secret key sk, a bound \(\left\lfloor\beta^{2}\right\rfloor\) A signature sig of m \(\tau\leftarrow\{0,1\}^{320}\) uniformly \(c\leftarrow\text{HashToPoint}(\text{r}\|\text{m})\) \(\text{t}\leftarrow\left(-\frac{1}{q}\text{FFT}(c)\odot\text{FFT}(F),\frac{1}{ q}\text{FFT}(c)\odot\text{FFT}(f)\right)\) do \(\text{z}\leftarrow\text{ffSampling}(\text{t},\text{T})\) \(\text{S}=\left(\text{t}-\text{z}\right)\left[\frac{FFT(g)-FFT(f)}{FFT(G)-FFT( f)}\right]\) while\(\|\text{S}\|^{2}>\beta^{2}\) \((s_{1},s_{2})\leftarrow\text{invFFT}(\text{s})\) \(s\leftarrow\text{Compress}(s_{2},8\cdot\text{sbytelen}-328)\) while\((s=\bot)\) returnsig\(=(r,s)\)
```  
**Algorithm 8** Falcon signature generation [46]. **Signature verification:** The verification algorithm, described in Algorithm 9, initiates by computing the combination of the initial component of the signature and the message using the HashToPoint function, resulting in a point on a modulo \(q\). This step lays the groundwork for further validation. Following this, the algorithm proceeds to decompressthe second component of the signature. If the decomposition fails, indicating potential tampering or invalidity, the algorithm promptly rejects the signature, ensuring the integrity of the verification process. Subsequently, the algorithm computes \(s_{1}\) by subtracting the hash digest \(c\) from the decompressed \(s_{1}\) multiplied by \(pk\), all under modulo \(q\). This computation is crucial in validating the authenticity of the signature against the provided \(pk\).