Paper 2022/998

On the Hardness of the Finite Field Isomorphism Problem

Dipayan Das, CISPA – Helmholtz Center for Information Security
Antoine Joux, CISPA – Helmholtz Center for Information Security

The finite field isomorphism (FFI) problem was introduced in PKC'18, as an alternative to average-case lattice problems (like LWE, SIS, or NTRU). As an application, the same paper used the FFI problem to construct a fully homomorphic encryption scheme. In this work, we prove that the decision variant of the FFI problem can be solved in polynomial time for any field characteristics $q= \Omega(\beta n^2)$, where $q,\beta,n$ parametrize the FFI problem. Then we use our result from the FFI distinguisher to propose polynomial-time attacks on the semantic security of the fully homomorphic encryption scheme. Furthermore, for completeness, we also study the search variant of the FFI problem and show how to state it as a $q$-ary lattice problem, which was previously unknown. As a result, we can solve the search problem for some previously intractable parameters using a simple lattice reduction approach.

Note: Minor typos have been fixed.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in EUROCRYPT 2023
LatticeFinite fieldCryptanalysis
Contact author(s)
dipayan das @ cispa de
joux @ cispa de
2023-02-20: last of 2 revisions
2022-08-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dipayan Das and Antoine Joux},
      title = {On the Hardness of the Finite Field Isomorphism Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/998},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.