CryptoDB
On the Hardness of the Finite Field Isomorphism Problem
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| Abstract: | 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. |
BibTeX
@inproceedings{eurocrypt-2023-32828,
title={On the Hardness of the Finite Field Isomorphism Problem},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30589-4_12},
author={Dipayan Das and Antoine Joux},
year=2023
}