On the Hardness of the Finite Field Isomorphism Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

On the Hardness of the Finite Field Isomorphism Problem

Résumé

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 = Ω(βn 2), 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.
Fichier principal
Vignette du fichier
2022-998.pdf (448.21 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY - Paternité

Dates et versions

hal-04294817 , version 1 (20-11-2023)

Licence

Paternité

Identifiants

Citer

Dipayan Das, Antoine Joux. On the Hardness of the Finite Field Isomorphism Problem. Eurocrypt 2023 - Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2023, Lyon, France. pp.343-359, ⟨10.1007/978-3-031-30589-4_12⟩. ⟨hal-04294817⟩
36 Consultations
17 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More