# Circuit for Batch Verification of Falcon Signatures ## 1. Notation * $n$ -- ring degree (512 or 1024) * $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$ * $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242) * $\phi=X^n+1$ ## 2. Single Signature Verification Inputs: * $r\in Z_2^{320}$ * $m$ -- bytestring * $s$ * public key $h\in Z_q[X]/\phi$ Procedure: 1. $c\in Z_q[X]/\phi\leftarrow HashToPoint(r||m)$: * Iterate SHAKE-256 on $r||m$; * Extract 16 bits as $b$. If the number $b$ is $<3q$, take $b\bmod q$ as a polynomial coefficient. 2. $s_2\in Z_q[X]/\phi\leftarrow Decompress(s)$. Reject invalid $s_2$. 3. $s_1 \in Z_q[X]/\phi\leftarrow c-s_2h$. 4. Normalize $s_1$: subtract $q$ from each coefficient that exceeds $\lfloor q/2\rfloor$. 5. Compute $A=||(s_1,s_2)||=\sum_i (s_{1,i}^2 +s_{2,i}^2)$. 6. If $A^2\leq \widehat{\beta}$ * then ACCEPT * else REJECT. Modified procedure: 3. Sample $z$ points $\alpha_1,\alpha_2,\ldots,\alpha_z$. Verify the statement $s_1 = c-s_2h$ on these $z$ points. If points are sampled via Fiat-Shamir, we need $z = \lambda /\log_2 \frac{q}{n}$ points, otherwise we need $n+1$ points. ## 3. Circuit for Batch Verification ### 3.1 Same $r$ and $m$ values for all signatures. In this case Aggregator passes $r,m$ in the cleartext and both Verifier and Aggregator can compute $c$ off-circuit. #### Parameters * $\ell$ --- number of signatures aggregated. The $i$-th signature is denoted as $(r,s[i])$; * $r$ --- the scalar field $\mathbb{F}$ size of the proof system (a number of about 254 bit size). * $w$ --- the number of points in $Z_q$ necessary to check the equality of degree $n$ polynomials with security level $\lambda$. Computed as $$z = \lambda /\log_2 \frac{q}{n}$$ #### Committed Inputs * $C$ is a commitment to $r,\{s_2[i]\}$ #### Precomputation * Compute $\alpha_1,\alpha_2,\ldots,\alpha_s \in Z_q \leftarrow Hash(C)$. #### Public Inputs * Public keys $h,h,\ldots, h[\ell]\in \mathbb{F}^n$ #### Constants * Polynomial $c(X)$. * Evaluations of $h[i]$ at points $\alpha_j$. #### Private Inputs * $\{s_2[i]\}\in \mathbb{F}^n$ #### Internal variables * $\{s_1[i]\}\in \mathbb{F}^n$ * $\{t_{i,j}\}\in \mathbb{F}$ #### Constraints * Coefficients range check: * $s_1[i]_j<q$. $14n$ constraints per signature * $s_2[i]_j<q$. $14n$ constraints per signature * Polynomial evaluation \begin{align} s_1[i](\alpha_j) &= w_{i,j};\;\quad z\text{ linear constraints per signature}\\ s_2[i](\alpha_j) &= w_{i,j}';\;\quad z\text{ linear constraints per signature}\\ h[i](\alpha_j) &= w_{i,j}'';\;\quad \text{ constant}\\ w_{i,j} &= c(\alpha_j)-w_{i,j}'\cdot w_{i,j}'' + q\cdot t_{i,j};\;\quad z\text{ multiplicative constraints per signature};\\ |t_{i,j}|&<nq+2n+1;\quad z(14+ \log n)\text{ multiplicative constraints per signature};\\ \end{align} Cost is $z(15 + \log n)$ mult constraints per signature. * Normalization: * Sign of $s_1[i]_j$ can be obtained for free from the range check (see above); * The rest is $1$ linear constraint per signature. * Bounding * Computation ($2n$ multiplicative constraints per signature) $$A^2 = \sum_j s_1[i]_j^2 + s_2[i]_j^2$$ * Bound $A^2 \leq \widehat{\beta}$ -- 25 or 26 mult constraints per signature. In total we have $30n+z(15+\log n)$ mult constraints For Falcon-512 and 128-bit security we have $z=29$ and thus totally about 16056 mult constraints. For Falcon-1024 we get $z=37$ and thus about 31645 constraints. ### 3.2 Distinct $r$ and $m$ values for all signatures. In this case still both Verifier and Aggregator can compute $c$ polynomials off-circuit but they are distinct. The circuit construction does not change much except that we replace $c(\alpha_j)$ with $c[i](\alpha_j)$ (both sets are constants). The number of constraints does not change then.