CISPA
Browse
2022-998.pdf (448.21 kB)

On the Hardness of the Finite Field Isomorphism Problem

Download (448.21 kB)
conference contribution
posted on 2024-03-25, 13:29 authored by Dipayan Das, Antoine Joux

 

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=Ω(ßn2), where q,ß,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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptographic Techniques (EuroCrypt)

Volume

14008

Page Range

343-359

Publisher

Springer Nature

Open Access Type

  • Not Open Access

BibTeX

@inproceedings{Das:Joux:2023, title = "On the Hardness of the Finite Field Isomorphism Problem", author = "Das, Dipayan" AND "Joux, Antoine", year = 2023, month = 4, pages = "343--359", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-3-031-30589-4_12" }