On the Hardness of the Finite Field Isomorphism Problem

Summary

The finite field isomorphism problem was introduced in PKC’18, as an alternative to average-case lattice problems (like , , or ). As an application, the same paper used the problem to construct a fully homomorphic encryption scheme. In this work, we prove that the decision variant of the problem can be solved in polynomial time for any field characteristics , where parametrize the problem. Then we use our result from the 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 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.