# Signature Split Method for a PQC-DSA Compliant with V2V Communication Standards
## 2 Preliminaries
### Falcon  
The keygen process of Falcon roughly consists of the process of generating the NTRU lattice, solving the NTRU equation, and generating a Falcon tree for trapdoor sampler operations. To generate the NTRU lattice, first, Falcon generates the polynomials \(f\) and \(\mathbf{g}\) with Gaussian distributions and then check that \(f^{(-1)}\) exists in modulus \(q\) (12,289). After  
\begin{table}
\begin{tabular}{c c c c c c c} \hline  & \multicolumn{3}{c}{**Crystals-Dilithium**} & \multicolumn{3}{c}{**Falcon**} \\ \hline \hline
**Problem** & \multicolumn{3}{c}{**Module-LWE**} & \multicolumn{3}{c}{**NTRU**} \\ \hline
**NIST Security** & **Public Key [B]** & **Secret Key [B]** & **Signature [B]** & **Public Key [B]** & **Secret Key [B]** & **Signature [B]** \\ \hline
1 (AES-128) & - & - & - & 897 & 1281 & 690 \\ \hline
2 (SHA256) & 1312 & 2528 & 2420 & - & - & - \\ \hline
3 (AES-192) & 1952 & 4000 & 3293 & - & - & - \\ \hline
5 (AES-256) & 2592 & 4864 & 4595 & 1793 & 2305 & 1330 \\ \hline \end{tabular}
\end{table}
Table 1: Parameters of Crystals-Dilithium and Falcon, size of the public key, secret key, and signature measured in bytes.  
this, the keygen process computes the polynomials \(F\) and \(G\) that satisfy the NTRU equation. Falcon performs the process of moving from the lower field to the upper field using the field norm map. The process of generating a Falcon tree consists of preprocessing a polynomial \(f\), \(g\), \(F\), and \(G\) into a suitable private key form. The sign process generates a signature over a message, and secret key id generated by keygen. First, the process computes a hash value \(c\), where \(c\) in \(\mathbb{Z}_{q}[X]/(X^{n}+1)\) using the message \(M\) and random value \(r\) where \(n\) is 256 and 512 for security level 1 and 5, respectively. Then, it computes the short vector that satisfies \(\mathbf{s_{1}}+\mathbf{s_{2}}h\equiv c\bmod q\) using the private key \(sk=f\), \(g\), \(F\), and \(G\). To prevent secret information leakage, Falcon uses a trapdoor sampler (fast Fourier sampling, ffSampling) to generate \(\mathbf{s_{1}}\) and \(\mathbf{s_{2}}\) without revealing the secret key. The verify process ensures that the SVP challenge is met. This is simple to configure compared to other algorithms.  
```
1:\(\mathbf{A}\in R_{q}^{k\times\ell}:=\text{ExpandA}(\rho)\)
2:\(\mu\in\{0,1\}^{384}:=\text{CRH}(tr\parallel M)\)
3:\(\kappa:=0,\,(\mathbf{z},\mathbf{h}):=\bot\)
4:while\((\mathbf{z},\mathbf{h}):=\bot\)do
5:\(y\in S_{\gamma_{1}-1}^{\ell}:=\text{ExpandMask}(K\parallel\mu\parallel x)\)
6:\(\mathbf{w}:=\mathbf{A}y\)
7:\(\mathbf{w_{1}}:=\text{HighBits}_{q}(\mathbf{w},2\gamma_{2})\)
8:\(c\in B_{60}:=\text{H}(\mu\parallel\mathbf{w_{1}})\)
9:\(\mathbf{z}:=\mathbf{y}+c\mathbf{s_{1}}\)
10:\((\mathbf{r_{0}},\mathbf{r_{1}}):=\text{Decompose}_{q}(\mathbf{w}-c\mathbf{s_ {2}},2\gamma_{2})\)
11:if\(\left\|\mathbf{z}\right\|_{\infty}\geq\gamma_{1}-\beta\) or \(\left\|\mathbf{r_{0}}\right\|_{\infty}\geq\gamma_{2}-\beta\) or \(\mathbf{r_{1}}\
eq\mathbf{w_{1}}\)
12:then\((\mathbf{z},\mathbf{h}):=\bot\)
13:else
14:\(\mathbf{h}:=\text{MakeHint}_{q}(-ct_{0},\mathbf{w}-c\mathbf{s_{2}}-ct_{0},2 \gamma_{2})\)
15:if\(\left\|ct_{0}\right\|\geq\gamma_{2}\) or the # of 1's in \(\mathbf{h}\) is greater than \(\mathbf{w}\)then\((\mathbf{z},\mathbf{h}):=\bot\)
16:\(\kappa=\kappa+1\)
17:return\(\sigma=(\mathbf{z},\mathbf{h},c)\)
```  
**Algorithm 1**Ditibium.Sign(\(sk,M\))