CryptoDB
On the Hardness of the Finite Field Isomorphism Problem
NOTE: imports for ToSC and TCHES are no longer functioning.
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 }