A signature scheme from the finite field isomorphism problem.

*(English)*Zbl 1450.94051Let \(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 [Y. Doröz et al., Lect. Notes Comput. Sci. 10769, 125–155 (2018; Zbl 1385.94032)] a new hard problem, the 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:

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.

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:

- 1.
- Generate a signature \(s\), which is a short vector within or close to a lattice \(L_h\) related to the hidden field \(X\).
- 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\).

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.

Reviewer: Dimitros Poulakis (Thessaloniki)

PDF
BibTeX
XML
Cite

\textit{J. Hoffstein} et al., J. Math. Cryptol. 14, 39--54 (2020; Zbl 1450.94051)

Full Text:
DOI

##### References:

[1] | Wieb Bosma, John Cannon and Catherine Playoust, The Magma algebra system. I. The user language., J. Symbolic Comput. 24 (1997), 235-265. · Zbl 0898.68039 |

[2] | Yuanmi Chen and Phong Q. Nguyen, BKZ 2.0: Better Lattice Security Estimates, in: ASIACRYPT, pp. 1-20, 2011. · Zbl 1227.94037 |

[3] | Yarkin Doröz, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Berk Sunar, William Whyte and Zhenfei Zhang, Fully Homomorphic Encryption from the Finite Field Isomorphism Problem, PKC 2018 (2018). · Zbl 1385.94032 |

[4] | Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky, Lattice Signatures and Bimodal Gaussians, CRYPTO 2013 (Ran Canetti and Juan A. Garay, eds.), LNCS 8042, Springer, 2013, pp. 40-56. · Zbl 1310.94141 |

[5] | Léo Ducas and Phong Q. Nguyen, Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures, in: Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, pp. 433-450, 2012. · Zbl 1292.94059 |

[6] | Oded Goldreich, Shafi Goldwasser and Shai Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, in: CRYPTO, pp. 112-131, 1997. · Zbl 0889.94011 |

[7] | Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman and William Whyte, NTRUSIGN: Digital Signatures Using the NTRU Lattice, in: Topics in Cryptology - CT-RSA 2003, The Cryptographers’ Track at the RSA Conference 2003, San Francisco, CA, USA, April 13-17, 2003, Proceedings, pp. 122-140, 2003. · Zbl 1039.94525 |

[8] | Jeffrey Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman and William Whyte, Transcript Secure Signatures Based on Modular Lattices, in: Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings, pp. 142-159, 2014. · Zbl 1380.94099 |

[9] | Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, in: ANTS, pp. 267-288, 1998. · Zbl 1067.94538 |

[10] | Jeffrey Hoffstein, Jill Pipher, William Whyte and Zhenfei Zhang, A signature scheme from Learning with Truncation, Cryptology ePrint Archive, Report 2017/995, 2017, http://eprint.iacr.org/2017/995. |

[11] | Nick Howgrave-Graham, A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU, in: CRYPTO, pp. 150-169, 2007. · Zbl 1215.94053 |

[12] | K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1990. · Zbl 0712.11001 |

[13] | Vadim Lyubashevsky, Fiat-shamir with aborts: Applications to lattice and factoring-based signatures, ASIACRYPT 2009, Springer, 2009, pp. 598-616. · Zbl 1267.94125 |

[14] | Vadim Lyubashevsky, Lattice Signatures without Trapdoors, EUROCRYPT2012 (David Pointcheval and Thomas Johansson, eds.), LNCS 7237, Springer, 2012, pp. 738-755. · Zbl 1295.94111 |

[15] | Gary L. Miller, Riemann’s hypothesis and tests for primality, Journal of Computer and System Sciences13 (1976), 300 - 317. · Zbl 0349.68025 |

[16] | Phong Q. Nguyen and Oded Regev, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, J. Cryptology22 (2009), 139-160. · Zbl 1159.94369 |

[17] | NIST, Post-Quantum Cryptography - Round 1 Submissions, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions. |

[18] | Michael O Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory12 (1980), 128 - 138. · Zbl 0426.10006 |

[19] | Damien Stehlé and Ron Steinfeld, Making NTRU as Secure as Worst-Case Problems over Ideal Lattices, in: Advances in Cryptology - EUROCRYPT2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, pp. 27-47, 2011. · Zbl 1281.94057 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.