S N O V A

Features

The SNOVA digital signature algorithm is a variant of the UOV algorithm, retaining the UOV's characteristic of short signatures while offering a shorter public key length compared to the traditional UOV algorithm, thereby providing advantages in both security and efficiency aspects of digital signatures.

Furthermore, the SNOVA algorithm provides a number of different parameter options for each security level, including various combinations of public key and signature lengths. This feature brings greater flexibility and adaptability to the application side, enabling SNOVA to be well-suited for diverse scenarios, whether it be resource-constrained devices or applications requiring high-security protection, as it allows for the selection of parameter configurations that best suit the specific use case.

Description of SNOVA

Let \( v, o \) be positive integers with \(v>o\) and \(\mathbb{F}_{q}\) be of characteristic 2. We choose \(\mathbb{F}_{q}=\rm{GF}(16)\) for our implementation. Let \(n=v+o\) and \(m=o\). The construction of a \((v,o,q,l)\) SNOVA scheme is based on the subfield \(\boldsymbol{\mathbb{F}_{q}[S]}\).

Subring \(\boldsymbol{\mathbb{F}_{q}[S]}\) and elements in \(\boldsymbol{\mathbb{F}_{q}[S]}\).

Let \(S\) be a \(l \times l\) symmetric matrix with an irreducible characteristic polynomial. The subring \(\mathbb{F}_{q}[S]\) of \(\mathcal{R}\) is defined as \[ \mathbb{F}_{q}[S]=\{a_{0}+a_{1}S+\cdots+a_{l-1}S^{l-1}\mid a_{0},a_{1},\cdots,a_{l-1} \in \mathbb{F}_{q}\}. \] As the characteristic polynomial of \(S\) is irreducible, \(\mathbb{F}_{q}[S]\) is a field. Thus, the elements in \(\mathbb{F}_{q}[S]\) are symmetric and they all commute. Let \[ \Omega=\{(j,k):1 \le j,k \le n\} \setminus \{(j,k):v+1 \le j,k \le n\}. \] This index set \(\Omega\) is defined by the Oil-Vinegar structure.

Central map of SNOVA.

For \(i \in \{1,\ldots,m\}\), we define \[ \left[ F_{i}\right]= \begin{bmatrix} F_{i,jk} \end{bmatrix} = \begin{bmatrix} F_{i}^{11} & F_{i}^{12} \\ F_{i}^{21} & 0 \end{bmatrix} \] where \(F_{i}^{11}\), \(F_{i}^{12}\) and \(F_{i}^{21}\) are matrices over \(\mathcal{R}\) randomly generated of size \(v \times v\), \(v \times o\) and \(o \times v\), respectively. We use random matrices and \(\left[F_{1}\right],\ldots,\left[F_{m}\right]\) to construct the central map. First, we randomly choose invertible elements \(A_{i,\alpha}\) and \(B_{i,\alpha}\) from \(\mathcal{R}\), and invertible elements \(Q_{i,\alpha,1}\) and \(Q_{i,\alpha,2}\) from \(\mathbb{F}_{q}[S]\). The central map of SNOVA scheme is \(\widetilde{F}=\left[\widetilde{F}_{1},\cdots,\widetilde{F}_{m}\right]:\mathcal{R}^{n} \rightarrow \mathcal{R}^{m}\), for \(i \in \{1,\cdots,m\}\), \(\widetilde{F}_{i}\) is defined to be \[ \widetilde{F}_{i}(X_{1},\ldots,X_{n})=\sum\limits_{\alpha=0}^{l^{2}+l-1}A_{i,\alpha} \cdot \left( \sum\limits_{(j,k) \in \Omega } X_{j}^{t}\left(Q_{i,\alpha,1}F_{i^{\prime},jk}Q_{i,\alpha, 2}\right)X_{k}\right) \cdot B_{i,\alpha} \] where \(i^{\prime} = (i+ \alpha) \mod m\) and \(F_{i^{\prime},jk}\) is the \((j,k)\)-th entry of \(\left[F_{i^{\prime}}\right]\). Changes to the Round 1 central map are: the sum over \(\alpha\) has been extended from \(l^2\) to \(l^{2}+l\) elements, the \(ABQ\) matrices now depend not only on \(\alpha\) but also on \(i\), and \(F_{i^\prime}\) depends on both \(i\) and \(\alpha\).

Invertible linear map.

The invertible linear map in SNOVA scheme is the map \(T: \mathcal{R}^{n} \rightarrow \mathcal{R}^{n}\) corresponding to the matrix \[ \left[T \right]= \left[T_{ij} \right]= \begin{bmatrix} I^{11} & T^{12}\\ 0 & I^{22}\\ \end{bmatrix}, \] where \(T^{12}\) is a \(v \times o\) matrix consisting of nonzero entries \(T_{ij}\) chosen randomly in \(\mathbb{F}_{q}[S]\). Note that \(T_{ij}\) is symmetric and commutes with other elements in \(\mathbb{F}_{q}[S]\). In particular, \(T_{ij}\) commutes with \(Q_{i,\alpha,1}\) and \(Q_{i,\alpha,2}\). The matrices \(I^{11}\) and \(I^{22}\) are identity matrices over \(\mathcal{R}\). Therefore, \(\left[T \right]\) is invertible and hence \(T\). Note that since \(\mathbb{F}_{q}\) is of characteristic \(2\), the matrix \(\left[T^{-1} \right]=\left[T \right]\).

Public map.

We construct the public key \(\left[ P_{1}\right],\ldots,\left[ P_{m}\right]\) via the congruence relation \[ \left[ P_{1}\right]= \begin{bmatrix} P_{1,j,k} \end{bmatrix} = \left[T \right]^{t}\left[ F_{1}\right]\left[T \right],\ldots, \left[ P_{m}\right]= \begin{bmatrix} P_{m,j,k} \end{bmatrix} = \left[T \right]^{t}\left[ F_{m}\right]\left[T \right]. \] The public map of SNOVA is \(\widetilde{P} = \widetilde{F} \circ T\). For \(i\in \{1,2,\dots,m\}\), \(\widetilde{P}_{i}=\widetilde{F}_{i} \circ T\). Then, by the relation \({\mathbf{X}}=\left[T \right] \cdot {\mathbf{U}}\) where \({\mathbf{U}}=(U_{1},\cdots,U_{n}) \in \mathcal{R}^{n}\) and the commutativity of \(\mathbb{F}_{q}[S]\), we have that \[ \widetilde{P}_{i}({\mathbf{U}})=\widetilde{F}_{i}(T({\mathbf{U}}))=\sum\limits_{\alpha=0}^{l^{2}+l-1} \sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}A_{i,\alpha} \cdot U_{j}^{t}(Q_{i,\alpha,1}P_{i^{\prime},jk}Q_{i,\alpha,2})U_{k} \cdot B_{i,\alpha} \] where \(i^{\prime}=(i +\alpha) \mod m\) and \(P_{i^{\prime},jk}\) is the \((j,k)\)-th entry of matrix \(\left[P_{i^{\prime}}\right]\). By introducing the matrices \(A_{i,\alpha},B_{i,\alpha},Q_{i,\alpha,1},Q_{i,\alpha,2}\), the public map \(\widetilde{P}\) is not a sparse UOV map when we regard it as over \(\mathbb{F}_{q}\).

Public key of SNOVA.

The public key are the matrices \(\left[P_{i} \right]\) and the matrices \(A_{i,\alpha}\), \(B_{i,\alpha}\), \(Q_{i,\alpha, 1}\) and \(Q_{i,\alpha, 2}\) for \(\alpha = 0,1,\dots,l^{2}+l-1\), or simply the seed \(\bf{s}_{public}\) which generates them.By utilizing matrices \(\left[P_{i} \right]\) and the seed \(\bf{s}_{public}\), the verifier is capable to obtain the public map \(\widetilde{P}\) and subsequently verify the received signature. We propose parameter settings aiming for NIST security levels I, III, and V. For security level I, our \(l=4\) parameter set results in a public key size of \(1016\) bytes and a signature size of \(248\) bytes. With these performances, we believe that the SNOVA scheme has strong competitiveness compared to other post-quantum signature schemes.