A signature scheme from the finite field isomorphism problem (Q2191202)

Let \(F_q\) be the finite field with \(q\) elements, and let \(f(x)\in F_q[x]\) and \(F(y)\in F_q[y]\) be irreducible monic polynomials of degree \(n\). We set \(X=F_q[x]/f(x)\) and \(Y = F_q[y]/f(y)\), and consider an isomorphism \(\phi : X \rightarrow Y\). Let \( 1 \leq \beta \leq q/2\) be a parameter, and denote by \( X[\beta]\) the set of \(a(x)\in X\) with \(L^{\infty}\)-norm bounded by \(\|a\| \leq \beta\). We select \(a_1(x), \ldots, a_k(x)\) uniformly and randomly from \(X[\beta]\), and let \(A_i = \phi(a_i)\) \((i=1,\ldots,k)\) be the corresponding images in \(Y\). In [\textit{Y. Doröz} et al., Lect. Notes Comput. Sci. 10769, 125--155 (2018; Zbl 1385.94032)] a new hard problem, the \textit{Finite Field Isomorphism Problem} (FFI) is presented. More precisely, we have the two following versions of this problem: The Computational FFI problem (CFFI): Given \( Y\) and the list of polynomials \(A_1(y), \ldots, A_k(y)\), recover \(f(x)\) and/or one or more of \(a_1(x), \ldots, a_k(x)\). The Decisional FFI problem (DFFI): Let \(\epsilon > 0\). Let \(b_1(x)\) be randomly chosen in \(X[\beta]\), let \(B_1(y) = \phi(b_1)\), and let \(B_2(y)\) be randomly chosen in \(Y\). Given the data \(Y, A_1(y), \ldots, A_k(y)\) and the pair \(\{B_1(y), B_2(y)\}\) in a random order, identify, with probability greater than \(1/2+ \epsilon\), which element of the pair was constructed using \(\phi\). In the aforementioned paper, a new fully homomorphic encryption scheme from the DFFI problem is given. In the paper under review, a signature scheme from the CFFI problem is constructed. For any polynomial \(h(x) \in X\), the associated NTRU lattice is defined to be the \(2n\)-dimensional lattice \(L_h\) formed by the pairs \((u(x), v(x))\in Z[x]^2\) with \(\deg u \leq n-1\), \(\deg v \leq n-1\) and \(v(x) \equiv u(x)h(x)\pmod{(q,f(x))}\) and similarly for \(L_{\phi(h)}\). The proposed signature scheme is build via the following framework: \begin{itemize} \item[1.] Generate a signature \(s\), which is a short vector within or close to a lattice \(L_h\) related to the hidden field \(X\). \item[2.] Publish its image \(S \in Y\), and prove the validity of the signature by showing a relationship between \(S\) and a lattice \(L_{\phi(h)}\) related to the public field \(Y\). \end{itemize} The assumption that the map \(\phi : X \rightarrow Y\) behaves randomly, implies that there is a negligible probability that the public lattice \(L_{\phi(h)}\) will have any exceptionally short vectors. Thus, trapdoors can be build using short vectors in \(L_h\) without the necessity of concealing the trapdoor from the attacker. It follows that one can use very efficient methods to generate \(s\). The key idea is that the attacker is not allowed to see the lattice \(X\), which contains one or more vectors that are considerably shorter than predicted by the Gaussian heuristic.