Paper 2022/998
On the Hardness of the Finite Field Isomorphism Problem
Abstract
The finite field isomorphism FFI problem, introduced in PKC'18, is an alternative to average-case lattice problems (like LWE, SIS, or NTRU). As an application, the FFI problem is used to construct a fully homomorphic encryption scheme in the same paper. 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 a polynomial-time attack 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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Lattice Finite field Cryptanalysis
- Contact author(s)
-
dipayan das @ cispa de
joux @ cispa de - History
- 2022-08-03: approved
- 2022-08-03: received
- See all versions
- Short URL
- https://ia.cr/2022/998
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/998,
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{https://eprint.iacr.org/2022/998}},
url = {https://eprint.iacr.org/2022/998}
}
