# On the Hardness of the Finite Field Isomorphism Problem

Dipayan Das, Antoine Joux

► To cite this version:

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

HAL Id: hal-04294817

https://hal.science/hal-04294817v1

Submitted on 20 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On the Hardness of the Finite Field Isomorphism Problem

Dipayan Das and Antoine Joux

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany.

dipayan.das@cispa.de, joux@cispa.de

**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.

## 1 Introduction

The Finite Field Isomorphism (FFI) problem has been introduced in [DHP+18] as a new hard problem to study post-quantum cryptography. Informally, it states the following.

For a hidden element $\mathbf{x}$ (with sparse minimal polynomial) in the finite field $\mathbb{F}_{q^n}$, if small $\beta$-bounded linear combinations of powers of $\mathbf{x}$ are given, in terms of powers of a uniform generator $\mathbf{y}$, it is hard to recover $\mathbf{x}$.

The decisional version of the problem states the following.

Given the $\mathbf{y}$-basis representation of finite field elements, it is hard to decide whether they are picked from the FFI distribution or the uniform distribution, with a non-negligible advantage over random guessing.

The FFI assumption is based on the fact that the basis transformation converts “good” representations to “bad” representations of $\mathbb{F}_{q^n}$. At a high level of abstraction, the heuristics of the FFI problem is comparable to many lattice problems, which involve recovering a “good” secret basis from a “bad” public basis (example, [GGH97,HPS98]). However, despite this high-level similarity, the details are quite different and a dedicated security analysis is required.

In the papers [DHP+18,HSWZ20], the authors thoroughly analyzed the generic hardness of the FFI problem. From their analysis, the best known attack for the decisional problem has $2^{O(n)}$ time complexity, whereas the best known attack for the search problem has $O(n!)$ time complexity. Based on their analysis, they
proceed to propose a fully homomorphic encryption scheme [DHP$^{+18}$] and a
signature scheme [HSWZ20] as applications of the FFI problem.

**1.1 Our Contribution**

This paper re-examines the hardness of the FFI problem in both its decisional and
computational versions. We use basic finite field theory to study the hardness of
the FFI problem.

In Section 4, we prove the values of the trace of the hidden polynomial
x-basis are bounded in absolute value by $n$. The proof is based on combinato-
rial techniques. Thus, by a linearity argument, the trace of FFI samples can be
bounded in absolute value by $\beta n^2$. This observation provides a polynomial-time
distinguisher to solve the decisional version of the FFI problem for any field with
characteristic $q \ge 4\beta n^2$.

In Section 5, we complement the attack on the decisional FFI problem by
breaking the semantic security of the fully homomorphic encryption scheme
from [DHP$^{+18}$]. First, we give a simple semantic attack by using the bound
on the trace of the ciphertext. Then we provide an additional semantic attack
that offers a slight improvement on the lower bound on the field characteristic $q$,
using the distribution of the trace of the inverse of the finite field elements. Both
attacks apply to the proposed parameter of the scheme.

In Section 6, we exploit the notion of dual basis of a finite field basis to solve
the computational FFI problem. By definition, the trace of any basis element
with respect to its dual basis can be expressed as the Kronecker delta function.
Consequently, the traces of FFI samples with respect to the dual x-basis are
bounded by $\beta$. Using this observation, we recover the dual x-basis from the
given FFI samples $A_i$. This is done by reducing an adequate lattice built from
traces of well-chosen finite field elements. We also show that a partial recovery of
the dual x-basis can be leverage into a full cryptanalysis with good probability.

Finally, we provide some experiments on lattice reduction to find the shortest
vectors in this lattice.

**2 Preliminaries**

**2.1 Notations**

The parameter $q$ denotes a (moderately large) prime integer throughout the
paper.

The finite field with $q$ elements is denoted by $\mathbb{F}_q$. All vectors are in columns
and are denoted with bold letters. We identify polynomials and vectors as being
the same data type using the coefficient embedding. For any vector $v$, we write
$\|v\|$ for the $\ell_\infty$ norm of $v$, and $\|v\|_2$ for the $\ell_2$ norm of $v$. Representatives of the
elements of $\mathbb{F}_q$ are centered around zero, i.e. chosen in the interval $[-\frac{q-1}{2}, \frac{q-1}{2}]$.
The rationale for using this representation is that it is much better adapted to
the goal of obtaining vectors with short norms.
## 2.2 Reminders from Finite Field Theory

For every prime $q$ and every positive integer $n$, there exists a unique finite field with $q^n$ elements. It is denoted by $\mathbb{F}_{q^n}$. The prime $q$ and the integer $n$ are respectively called the characteristic and degree of the finite field.

Let $f(\boldsymbol{x})$ and $F(\boldsymbol{y})$ be two irreducible polynomials of degree $n$ over $\mathbb{F}_q$. We can construct two isomorphic representations of the finite field $\mathbb{F}_{q^n}$ as $X := \mathbb{F}_q[\boldsymbol{x}]/(f(\boldsymbol{x}))$ and $Y := \mathbb{F}_q[\boldsymbol{y}]/(F(\boldsymbol{y}))$. Every element of $\mathbb{F}_{q^n}$ can be uniquely represented by a polynomial in $\boldsymbol{x}$ with coefficients in $\mathbb{F}_q$ and degree less than $n$. Similarly, there is a representation in terms of $\boldsymbol{y}$. In other words, the set

$$ \{\mathbf{1}, \boldsymbol{x}, \dots, \boldsymbol{x}^{n-1}\} $$

is a basis of $\mathbb{F}_{q^n}$, viewed as a vector space over $\mathbb{F}_q$. This basis is called the $\boldsymbol{x}$-polynomial-basis or $\boldsymbol{x}$-basis for short. For ease of reading, we denote finite field elements known in the $\boldsymbol{x}$-basis by small letters and elements known in the $\boldsymbol{y}$-basis by capital letters.

To explicit an isomorphism between these two representations of $\mathbb{F}_{q^n}$, it suffices to know the representation in the $\boldsymbol{x}$-basis of a root of $F(\boldsymbol{y})$ or conversely the $\boldsymbol{y}$-representation of a root of $f(\boldsymbol{x})$. Note that each of the two polynomials has $n$ distinct roots, which are images of each other by the $q$-th power Frobenius map.

For every element $\boldsymbol{\alpha} \in \mathbb{F}_{q^n}$, its conjugates are obtained by repeatedly applying the Frobenius map, i.e. they are $\boldsymbol{\alpha}, \boldsymbol{\alpha}^q, \dots, \boldsymbol{\alpha}^{q^{(n-1)}}$. They are distinct if and only if the minimal polynomial of $\boldsymbol{\alpha}$ has degree $n$. The trace of an element in $\mathbb{F}_{q^n}$ is defined as the sum of all its conjugates:

$$ \mathrm{Tr}(\boldsymbol{\alpha}) := \boldsymbol{\alpha} + \boldsymbol{\alpha}^q + \dots + \boldsymbol{\alpha}^{q^{(n-1)}} \in \mathbb{F}_q $$

The trace function is linear, i.e.

$$ \mathrm{Tr}(\boldsymbol{\alpha} + c\boldsymbol{\beta}) = \mathrm{Tr}(\boldsymbol{\alpha}) + c\mathrm{Tr}(\boldsymbol{\beta}) $$

for any $\boldsymbol{\alpha}, \boldsymbol{\beta} \in \mathbb{F}_{q^n}$ and $c \in \mathbb{F}_q$.

Moreover, for every linear map $L$ from $\mathbb{F}_{q^n}$ to $\mathbb{F}_q$, there exists a unique element $\boldsymbol{\beta}$ in $\mathbb{F}_{q^n}$ such that:

$$ \forall \boldsymbol{\alpha} \in \mathbb{F}_{q^n} : L(\boldsymbol{\alpha}) = \mathrm{Tr}(\boldsymbol{\beta} \cdot \boldsymbol{\alpha}). $$

We denote this linear function by $L_\beta$.

To every basis $\omega_1, \omega_2, \dots, \omega_n$ of $\mathbb{F}_{q^n}$ we associate a dual basis $^1\hat{\omega}_1, ^1\hat{\omega}_2, \dots, ^1\hat{\omega}_n \in \mathbb{F}_{q^n}$, defined as the unique one which satisfies:

$$ \mathrm{Tr}(\omega_i \hat{\omega}_j) = \delta_i^j $$

where $\delta_i^j$ is the Kronecker delta function. From this definition, it is clear that the bidual of a basis, i.e. the dual of its dual, is the basis itself.

<footnote n="1">¹ Note that this notion of the dual basis of a finite field does not correspond to the idea of the dual basis of a lattice. This paper only uses the term dual basis to refer to the former notion.</footnote>
## 2.3 Lattice Reduction

Given a (full rank) matrix $B \in \mathbb{Z}^{d \times d}$, the lattice $\mathcal{L}$ generated by the basis $B$ is the set $\mathcal{L}(B) := \{Bz : z \in \mathbb{Z}^d\}$, $d$ is the lattice dimension. A lattice is called $q$-ary if it contains $q\mathbb{Z}^d$ as a sublattice. The volume of a lattice $\mathcal{L}(B)$ is defined as $\text{Vol}(\mathcal{L}) := |\det(B)|$. Any lattice of dimension $d \ge 2$ has infinitely many bases that generate the same lattice, and any two bases $B, B'$ are related by a unimodular matrix $U$ such that $B = B'U$. Note that the unimodular matrix stands on the right because we use the convention of having vectors in columns. The volume of a lattice is independent of the choice of lattice basis.

For a random lattice $\mathcal{L}$, the Gaussian heuristic estimates the Euclidean norm of the shortest non-zero vector in the lattice, which is approximately $\sqrt{\frac{d}{2\pi e}} \text{Vol}(\mathcal{L})^{1/d}$ [GN08].

For any basis $B$, we write $B^*$ to represent the Gram-Schmidt orthogonalization (GSO) of $B$, where the $i$-th vector of $B^*$ is given by $b_i^* := \pi_i(b_i)$. Here, the notation $\pi_i$ denotes the projection of a vector orthogonally to the vector subspace spanned by $b_1, b_2, \dots, b_{i-1}$.

A central problem in the algorithmics of lattices is to find shortest non-zero vectors (SVP) from a lattice basis $B$. This can be a handy tool in cryptanalysis. The most widely used lattice reduction algorithm is LLL [LLL82] which is polynomial-time but only yields an approximation of SVP within an exponential factor. Since this can be insufficient for cryptanalysis, it is standard practice to use slower algorithms that produce better approximations.

For our needs, we use the implementation of the blockwise Korkine-Zolotarev (BKZ) algorithm provided with the fplll software [The22].

## 2.4 Semantic Attack of an encryption scheme

An encryption scheme (KeyGen, Enc, Dec) that only encrypts bits (i.e. with message space $\{0, 1\}$) has $(t, \delta)$ attack against the semantic security if there exists an adversary $\mathcal{A}$ winning the following game against a challenger $\mathcal{C}$.

- $\mathcal{C}$ samples $m \leftarrow \{0, 1\}$, $(pk, sk) \leftarrow \text{KeyGen}(1^{\lambda})$.

- $\mathcal{C}$ gives $pk, c := \text{Enc}(pk, m)$ to $\mathcal{A}$.

- $\mathcal{A}$ outputs $m' \in \{0, 1\}$.

$\mathcal{A}$ wins the game if $\mathcal{A}$ has running time $t$ and advantage $\delta$, where the advantage is defined by

$$| \Pr[m' = m] - \Pr[m' \neq m] |$$

## 3 Finite Field Isomorphism Problem

This section formally describes the FFI problem in both its computational and decisional forms.
Let $\mathbb{X}, \mathbb{Y}$ be two representations of the finite field $\mathbb{F}_{q^n}$ as before. In the rest of the paper, we assume $n \ge 50$ to be out of range of easy exhaustive search attacks. The defining polynomial of $\mathbb{X}$ is sampled uniformly from the set of all sparse irreducible polynomials of the form $\mathbf{x}^n + \mathbf{g}(\mathbf{x})$ with $\deg \mathbf{g}(\mathbf{x}) \le \lfloor n/2 \rfloor$ and $\|\mathbf{g}(\mathbf{x})\| \le 1$, i.e. $\mathbf{g}(\mathbf{x})$ has ternary coefficients. The defining polynomial of $\mathbb{Y}$ is sampled uniformly from the set of arbitrary monic irreducible polynomials. Let $\phi(\mathbf{y})$ be an isomorphism from $\mathbb{X}$ to $\mathbb{Y}$. Note that there is an efficient algorithm to compute an isomorphism between the two representations [BCS97].<fnref n="2" /> Let $\chi_\beta$ be a distribution over $\mathbb{X}$ that samples polynomials $\mathbf{a}_i(\mathbf{x})$ with $\|\mathbf{a}_i(\mathbf{x})\| \le \beta$. Let $\mathbf{A}_i(\mathbf{y})$ be the corresponding image of $\mathbf{a}_i(\mathbf{x})$ under the isomorphism $\phi$.

**Definition 1 (Computational Finite Field Isomorphism Problem (CFFI$_{q,k,n,\beta}$)).**
Given $\mathbb{Y}$ by $\mathbf{F}(\mathbf{y})$ and $k$ samples $\mathbf{A}_1(\mathbf{y}), \dots, \mathbf{A}_k(\mathbf{y})$ recover $\mathbf{f}(\mathbf{x})$.

**Definition 2 (Decisional Finite Field Isomorphism Problem (DFFI$_{q,k,n,\beta}$)).**
Given $\mathbb{Y}$ by $\mathbf{F}(\mathbf{y})$ and $k$ samples $\mathbf{B}_1(\mathbf{y}), \mathbf{B}_2(\mathbf{y}), \dots, \mathbf{B}_k(\mathbf{y})$ that are either sampled from FFI distribution (having pre-images bounded by $\beta$) or sampled uniformly at random in $\mathbb{Y}$, DFFI$_{q,k,n,\beta}$ problem is to distinguish, with some non-negligible advantage, the correct source distribution of the samples $\mathbf{B}_i(\mathbf{y})$.

Note that the sparsity constraint on the defining polynomial of $\mathbb{X}$ is not directly included in the definition of the FFI problem given in [DHP$^{+}$18,HSWZ20]. However, the noise growth analysis of [DHP$^{+}$18, Appendix B] explicitly rewrites<fnref n="3" /> $\mathbf{f}(\mathbf{x})$ as $\mathbf{x}^n + \mathbf{f}'(\mathbf{x})$ and proceeds to bound the noise-growth during multiplication in $\mathbb{X}$ under the assumption that the degree $d$ of $\mathbf{f}'$ satisfies $d < n/2$. For clarity, we instead chose to directly include this low-degree constraint as part of the definition.

## 3.1 Previous Attacks

In this section, we briefly describe all the attacks that have been considered for both decisional and computational FFI problem in [DHP$^{+}$18,HSWZ20].

### Decisional Finite Field Isomorphism Problem

#### Lattice Attack

The decisional FFI problem could be solved by predicting if there is any good representation of the given samples, which is very unlikely for uniform samples. To achieve this, the authors of [DHP$^{+}$18,HSWZ20] suggested lattice reduction on the $q$-ary lattice

$$ \mathcal{L}_{\mathbf{A},q} := \{ \mathbf{a}_i \in \mathbb{Z}^k : \mathbf{A}\mathbf{\Psi}_i = \mathbf{a}_i \text{ mod } q \text{ for some } \mathbf{\Psi}_i \in \mathbb{Z}^n \} $$

<footnote n="2">² In practice, SAGE MATH provides the FiniteFieldHomomorphism generic (Hom( . )) function available under sage.rings.finite_rings.hom_finite_field package for this task.</footnote>

<footnote n="3">³ In the rewriting, $\mathbf{f}'(\mathbf{x})$ does not denote the derivative of $\mathbf{f}$ but an auxiliary polynomial. In our definition, we use the notation $\mathbf{g}(\mathbf{x})$ to avoid any possible confusion with the derivative.</footnote>
with each row of the matrix $\mathbf{A}$ generated from the given $\mathbf{y}$-basis representations of samples. For FFI samples, there are unusually short vectors in the lattice that corresponds to the $\mathbf{x}$-basis (or small linear combination of $\mathbf{x}$-basis) representation. For uniform samples, it is highly unlikely to have such short vectors in the lattice.

## Computational Finite Field Isomorphism Problem

### Hybrid attack

The authors of [DHP$^+$18,HSWZ20] propose to find the shortest vectors in the lattice $\mathcal{L}_{A,q}$, in the hope that they correspond to the coefficients of some powers of $\mathbf{x}$. Since the shortest vectors appear in a somewhat random-looking order, the authors suggested adding a combinatorial algorithm to resolve the ordering issue and recover the $\mathbf{x}$-basis representations of the FFI samples. This gives an attack to the computational FFI problem. They estimate the cost of the combinatorial step to be $O(n!)$, thus infeasible. One might argue that this could possibly be improved by some form of meet-in-the-middle to $O(\sqrt{n!})$. We do not examine this direction since we show in Section 6 that we can get rid of the combinatorial step altogether.

### Non-linear attack

The non-linear attack involves solving the non-linear system of equations to recover the hidden isomorphism $\phi$ using Gröbner basis computation. An adversary can solve for $2n - 2$ unknowns of $(\phi, (a_i(\mathbf{x}))$ from the equation $\phi(a_i(\mathbf{x})) = A_i(\mathbf{y})$. Solving such an equation is believed to be hard.

# 4 Proposed Attack on the Decisional FFI problem

This section proposes a new polynomial-time attack on the DFFI problem. We show that when a sample $A_i(\mathbf{y})$ comes from the FFI distribution, the underlying trace of $A_i(\mathbf{y})$ is bounded by a small multiple of $n^2$. We use this fact to mount a distinguishing attack on the DFFI problem.

**Lemma 1.** Let $f(\mathbf{x}) := \mathbf{x}^n + \sigma_1\mathbf{x}^{n-1} + \sigma_2\mathbf{x}^{n-2} + \cdots + \sigma_n$ be the defining polynomial of $\mathbb{X}$, where $\sigma_i \in \{-1, 0, 1\}$ for $\lfloor n/2 \rfloor \le i \le n, 0$ otherwise$^4$. Then

$$ \mathrm{Tr}(\mathbf{x}^i) \equiv \begin{cases} n \pmod q, & \text{if } i = 0 \\ 0 \pmod q, & \text{if } 1 \le i \le \lfloor n/2 \rfloor - 1 \\ \pm i \pmod q, & \text{if } \sigma_i \ne 0 \text{ and } \lfloor n/2 \rfloor \le i \le n-1 \\ 0 \pmod q, & \text{if } \sigma_i = 0 \text{ and } \lfloor n/2 \rfloor \le i \le n-1 \end{cases} $$

*Proof.* The definition of trace function gives $\mathrm{Tr}(\mathbf{x}^i) = n$ when $i = 0$. To prove the Lemma for $i > 0$, let us first recall the Girard-Newton identities relating the sum

<footnote>$^4$ Indeed, the smallest $i$ with $\sigma_i \ne 0$ satisfies $i + \deg g = n$. Since $\deg g = \lfloor n/2 \rfloor$ this corresponds to $i = \lfloor n/2 \rfloor$.</footnote>
of powers to symmetric polynomials. Given $n$ arbitrary numbers $w_0, \dots, w_{n-1}$ in an arbitrary ring, define their symmetric polynomials as usual by: $\sigma_1 = \sum_{i=0}^{n-1} w_i$, $\sigma_2 = \sum_{0 \le i < j < n} w_i w_j$, $\sigma_3 = \sum_{0 \le i < j < k < n} w_i w_j w_k$, ..., $\sigma_n = \prod_{i=0}^{n-1} w_i$. Then, for any $1 \le \bar{d} < n$, we have:

$$ \sum_{i=0}^{n-1} w_i^d = (-1)^d \sum_{r_1+2r_2+\dots+dr_d=d} d \cdot \frac{(r_1+r_2+\dots+r_d-1)!}{r_1!r_2!\dots r_d!} \prod_{j=1}^{d} (-\sigma_j)^{r_j} \quad (1) $$

Note that the coefficients in this equation, while written as fractions for notational purposes are, in fact, integers. As a consequence, the identity holds in every ring. In particular, when working modulo $q$ as we are. However, to avoid any potential division by 0, the coefficients should first be computed as exact integers and only reduced modulo $q$ afterwards.

The set of all the roots of $f(x)$ are given by

$$ \{\alpha_0 := x, \alpha_1 := x^q, \dots, \alpha_{n-1} := x^{q^{n-1}}\} $$

Let now the $(\sigma_j)_{1 \le j \le n}$ denote the $n$ symmetric polynomials in these roots. We know that we can write

$$ f(x) = x^n - \sigma_1 x^{n-1} + \sigma_2 x^{n-2} - \dots (-1)^n \sigma_n. $$

Thus, $\sigma_1 = \sigma_2 = \dots = \sigma_{\lceil n/2 \rceil - 1} = 0$.

Since, $\mathrm{Tr}(x^i)$ is a sum of $i$-th power of $\alpha_j$s, we can use the above identity to express it in terms of the $\sigma_j$s. Depending on the value of $i$, two cases arise:

*Case 1* ($1 \le i \le \lceil n/2 \rceil - 1$). Since all contributions include a $\sigma_j$ for $j \le i$ with value zero, there is no non-zero term in the sum of the right-hand side of Equation (1), we have

$$ \mathrm{Tr}(x^i) = 0 $$

*Case 2* ($\lceil n/2 \rceil \le i \le n - 1$). Again, since $\sigma_j = 0$ for $1 \le j \le \lceil n/2 \rceil - 1$, there is exactly one element in the set $\{(r_1, r_2, \dots, r_i) : \sum_{l=1}^i lr_l = i\}$ that contributes in the sum of the right-hand side of Equation (1), namely $(r_1 = 0, r_2 = 0, \dots, r_i = 1)$. Indeed, the sum of two contributions above $\lceil n/2 \rceil$ is always greater than $i$. This gives

$$ \mathrm{Tr}(x^i) = \begin{cases} \pm i & \text{for non-zero } \sigma_i, \\ 0 & \text{for } \sigma_i = 0 \end{cases} $$

**Lemma 2.** Let $A_i(y)$ be an $\mathrm{FFI}_{q,k,n,\beta}$ sample. Then $|\mathrm{Tr}(A_i(y))| \le 0.39\beta n^2$.

*Proof.* Let $a_i(x)$ be the representation of $A_i(y)$ in the $x$-basis. Since the trace of a finite field element is invariant to the basis representation, both $a_i(x)$ and $A_i(y)$ must have the same trace. So in order to bound the trace of $A_i(y)$, it is
sufficient to bound the trace of $a_i(x)$. By the linearity of the trace and by the previous Lemma, we have

$$ \begin{aligned} |\mathrm{Tr}(A_i(y))| & \le \beta \sum_{j=\lceil n/2 \rceil}^{n} j \\ & \le 0.39\beta n^2 \text{ for } n \ge 50. \end{aligned} $$

**Theorem 1.** Let $q \ge 1.56\beta n^2$, then there exists a polynomial-time algorithm with advantage $1 - \Omega(1/2^k)$ to distinguish the DFFI$_{q,k,n,\beta}$ problem.

*Proof.* Let $B_1(y), B_2(y), \dots, B_k(y)$ be the given $k$ samples to distinguish between FFI distribution and uniform distribution. The distinguisher finds the correct distribution of the samples by computing the trace of the samples. In a finite field, the trace function is uniformly distributed. Thus for a uniform sample $B_i(y)$, $\mathrm{Tr}(B_i(y))$ is uniformly distributed over $\mathbb{F}_q$. For an FFI sample $B_i(y)$, by the previous Lemma, $|\mathrm{Tr}(B_i(y))| \le 0.39\beta n^2$. Combining the number of samples and condition on $q$, the distinguisher outputs 1 when the samples come from FFI distribution with probability 1, and outputs 1 when the samples come from uniform distribution with probability at most $1/2^k$.

It is only left to show that the distinguisher is indeed polynomial-time. The running time of the attack is dominated by trace computation of finite field elements. Since the trace of a finite field element can be computed efficiently in time $n^{1+o(1)} \log^{2+o(1)} q$ using iterated Frobenius [KU08,Nar18], this is polynomial-time.

# 5 Proposed Semantic Attack on the fully homomorphic encryption scheme

In this section, we propose a polynomial-time attack on the semantic security of the fully homomorphic encryption scheme $\mathcal{E} := (\mathrm{KeyGen}, \mathrm{Enc}, \mathrm{Dec}, \mathrm{Eval})$ from [DHP$^{+18}$]. The working principle of the scheme is given below.

- **KeyGen**(1$^{\lambda}$) : Generate the FFI parameters $\Xi := (n, q, \beta)$ as a function of $\lambda$, and two representations of the finite field by sampling $f(x), F(y)$ with an isomorphism $\phi$ like before. Choose two integers $(S, s)$ satisfying $\binom{S}{s} \ge 2^{\lambda}$. Sample $S$ many $c_i(x)$ from the distribution $\chi_{\beta}$ and construct $C_i(y) := p\phi(c_i(x))$ for fixed constant $p := 2$. In the rest of the section, we assume $p$ is equal to 2 as in [DHP$^{+18}$].

The secret key is $sk := (\Xi, \phi, f(x))$.

The public key is $pk := (\Xi, C_1(y), C_2(y), \dots, C_S(y), F(y), s, p)$.

- **Enc**(m, pk) : The encryption of a message $m \in \{0, 1\}$ is

$$ C := \sum_{i \in [s]} C_i(y) + m $$
for uniformly random s samples $C_i(y)$.

- **Dec($C, sk$)**: The decryption recovers $m$ by computing

$$m' := p \sum_{i \in [s]} c_i(x) + m \mod p$$

using the inverse of the secret isomorphism $\phi$.

- **Eval($C, C^{(1)}, C^{(2)}, \dots, C^{(l)}$)**: The homomorphic evaluation of ciphertexts of a circuit $C$ with gates $(+, \times)$ are done using homomorphic addition and multiplication (with noise management) on $C^{(i)}$s. It is shown that for $q = 2^{n^\epsilon}$ with $\epsilon \in (0, 1)$, the above encryption scheme $\mathcal{E}$ is fully homomorphic using circular security and bootstrapping techniques (Theorem 3 of [DHP$^+$18]).

The result of Theorem 1 invalidates the semantic security of the fully homomorphic encryption scheme $\mathcal{E}$ (Theorem 1 of [DHP$^+$18]). The next Theorem gives a polynomial-time algorithm to break the semantic security of $\mathcal{E}^5$.

**Theorem 2.** Let $q > 0.44s\beta^2n^5 + 0.78\beta n^2$, then there exists a deterministic polynomial time attack against the semantic security of the fully homomorphic encryption scheme $\mathcal{E}$ defined as above.

*Proof.* Let the challenger $C$ give the public key $pk \leftarrow KeyGen(1^\lambda)$ and an encryption $C$ of a message $m \leftarrow \{0, 1\}$ to the adversary $\mathcal{A}$. Then

$$C = p \sum_{i \in [s]} \phi(c_i(x)) + m \quad (2)$$

$\mathcal{A}$ wins the semantic game by the following analysis.

We consider the following two cases for the choice of $n$.

1. When $p = 2$ is not a divisor of $n$.

Note that $\sum_{i \in [s]} \phi(c_i(x))$ is an $\text{FFI}_{q, 1, n, s\beta}$ sample. So the trace of the summation is small. By the linearity of trace and from Equation (2),

$$\text{Tr}(C) = p\text{Tr}(\sum_{i \in [s]} \phi(c_i(x))) + \text{Tr}(m)$$

Since $\text{Tr}(1) = n$ and $p$ is not a divisor of $n$, $\mathcal{A}$ breaks the semantic game for the encryption $C$ as below.

$$\text{Tr}(C) \bmod p = 0, \text{ Return } C \text{ is an encryption of } 0 \\ = n \bmod p = 1, \text{ Return } C \text{ is an encryption of } 1$$

<footnote n="5">⁵ Note that the attack does not use the homomorphic property of the encryption scheme, just regular encryptions of bits.</footnote>
2. When $p = 2$ is a divisor of $n$.

In this case, $\text{Tr}(\mathcal{C})$ mod $p$ will be 0 for both encryptions of 0 and 1. To get a semantic attack, $\mathcal{A}$ needs to do a small modification here.

$\mathcal{A}$ picks an $\text{FFI}_{q,1,n,\beta}$ sample $\mathcal{C}^*$ (with pre-image $\mathcal{c}^*$) such that $|\text{Tr}(\mathcal{C}^*)|$ is not a multiple of $p$. As any field isomorphism map elements in $\mathbb{F}_q$ to itself, this happens with probability $1/p$ for each $p^{-1}\mathcal{C}_i(\mathbf{y})$, where $\mathcal{C}_i(\mathbf{y})$ for $1 \le i \le S$ are the public key samples, so $\mathcal{A}$ almost surely knows such a sample. Multiplying both sides of Equation (2) by $\mathcal{C}^*$, we get

$$ \mathcal{C}\mathcal{C}^* = p \phi \left( \left( \sum_{i \in [s]} \mathcal{c}_i(\mathbf{x}) \right) \mathcal{c}^* \right) + m\mathcal{C}^* \quad (3) $$

By the ternary sparse choice of the minimal polynomial of $\mathbf{x}$, the noise of polynomial multiplication in $\mathbb{X}$ grows at most by a factor of $n^3$ (Equation 5 of [DHP+18]). So, the product of $\phi(\sum_{i \in [s]} \mathcal{c}_i(\mathbf{x}))$ and $\phi(\mathcal{c}^*)$ is an $\text{FFI}_{q,1,n,0.28s\beta^2n^3}$ sample, and hence, by Lemma 2, the absolute value of the trace is bounded by $0.11s\beta^2n^5$. By the linearity of trace, we have from Equation (3)

$$ \text{Tr}(\mathcal{C}\mathcal{C}^*) = p \text{Tr} \left( \phi \left( \left( \sum_{i \in [s]} \mathcal{c}_i(\mathbf{x}) \right) \mathcal{c}^* \right) \right) + m \text{Tr}(\mathcal{C}^*) $$

Since $\text{Tr}(\mathcal{C}^*)$ is not a multiple of $p$, $\mathcal{A}$ breaks the semantic game for the encryption $\mathcal{C}$ as below.

$$ \begin{aligned} \text{Tr}(\mathcal{C}\mathcal{C}^*) \bmod p = 0, \quad & \text{Return } \mathcal{C} \text{ is an encryption of } 0 \\ = 1, \quad & \text{Return } \mathcal{C} \text{ is an encryption of } 1 \end{aligned} $$

If the $q$ is chosen as in the Theorem to avoid modular reduction, $\mathcal{A}$ returns $m' \in \{0, 1\}$ with advantage $\delta = 1$. The adversary $\mathcal{A}$ runs in polynomial time by the argument given in Theorem 1.

Below we also provide an alternative approach to break the semantic security of the homomorphic encryption scheme that gives a tighter lower bound on $q$. The main ingredient of this approach is to break the semantic security of the scheme by the distribution of the trace of the inverse of $p$.

**Theorem 3.** Let $q > 0.44s\beta^2n^5 + 0.39\beta n^2$, then there exists a deterministic polynomial time attack against the semantic security of the fully homomorphic encryption scheme $\mathcal{E}$ defined as above.

*Proof.* Let the challenger $\mathcal{C}$ give the public key $\text{pk} \leftarrow \text{KeyGen}(1^\lambda)$ and an encryption $\mathcal{C}$ of a message $m \leftarrow \{0, 1\}$ to the adversary $\mathcal{A}$. $\mathcal{A}$ computes

$$ \mathcal{C}p^{-1} = \sum_{i \in [s]} \phi(\mathcal{c}_i(\mathbf{x})) + mp^{-1} \quad (4) $$

$\mathcal{A}$ wins the semantic game by the following analysis.

We consider the following two cases for the choice of $n$.
1. When $p=2$ is not a divisor of $n$.

Since any field isomorphism $\phi$ maps elements in $\mathbb{F}_q$ to itself, $\sum_{i \in [s]} \phi(c_i(x))$ is an $\text{FFI}_{q,1,n,s\beta}$ sample. As a consequence, from Equation (4), $Cp^{-1}$ is an $\text{FFI}_{q,1,n,s\beta}$ sample for an encryption of 0, thus have small trace. But for an encryption of 1, by linearity, trace of $Cp^{-1}$ is dominated by the trace of $1/p$. We now claim the absolute value of $\text{Tr}(1/p)$ is close to the boundary point $(q-1)/2$ of the $\mathbb{F}_q$ representation, thus trace of $Cp^{-1}$ is large. By the definition of trace,

$$ 
\begin{aligned}
\text{Tr}(1/p) &= n/p \mod q \\
&= n(q+1)/p \mod q \\
&= (n+q)/p \mod q \text{ since } p \text{ is not a divisor of } n
\end{aligned} 
\qquad (5) $$

To see the validity of the last line of the above equation, writing $n = pi + 1$, we have

$$ 
\begin{aligned}
n(q+1)/p \mod q &= (pi+1)(q+1)/p \mod q \\
&= i + (q+1)/p \mod q \\
&= (n+q)/p \mod q
\end{aligned} 
$$

Finally, we have $|\text{Tr}(1/p)| = (q-n)/p$ in the representation of $\mathbb{F}_q$. Thus $\mathcal{A}$ breaks the semantic game for the encryption $\mathcal{C}$ from Lemma 2 as below.

$|\text{Tr}(Cp^{-1})| \le 0.39s\beta n^2$, Return $\mathcal{C}$ is an encryption of 0
Otherwise, Return $\mathcal{C}$ is an encryption of 1

2. When $p=2$ is a divisor of $n$.

In this case, from the first line of Equation (5), the trace of $Cp^{-1}$ will be small for both encryptions of 0 and 1. To get a semantic attack, $\mathcal{A}$ needs to do a small modification here as in the previous Theorem.

$\mathcal{A}$ picks an $\text{FFI}_{q,1,n,\beta}$ sample $C^*$ such that $|\text{Tr}(C^*)|$ is not a multiple of $p$. Multiplying both sides of Equation (4) by $C^*$, we get

$$ C^*Cp^{-1} = C^* \sum_{i \in [s]} \phi(c_i(x)) + mC^*p^{-1} \qquad (6) $$

Again, by the choice of the minimal polynomial of $x$, the noise of polynomial multiplication in $\mathbb{X}$ grows at most by a factor of $n^3$ (Equation 5 of [DHP+18]). For an encryption of 0, since $C^*$ and $Cp^{-1}$ are $\text{FFI}_{q,1,n,\beta}$ and $\text{FFI}_{q,1,n,s\beta}$ samples, respectively, $C^*Cp^{-1}$ is an $\text{FFI}_{q,1,n,0.28s\beta^2n^3}$ sample. Thus the trace of the product $C^*Cp^{-1}$ is still small. But for an encryption of 1, by Equation (6), the trace of $C^*Cp^{-1}$ is dominated by the trace of second summand $C^*p^{-1}$. Since the absolute value of $\text{Tr}(C^*p^{-1})$ is close to the boundary point $(q-1)/2$, the trace of $CC^*p^{-1}$ is large in this case.

To see the above claim, let $\text{Tr}(C^*) = t$, where $|t| \le 0.39\beta n^2$ and $|t|$ is not a divisor of $p$. By the linearity of trace and from the previous analysis,

$$ 
\begin{aligned}
\text{Tr}(C^*p^{-1}) &= 1/p\text{Tr}(C^*) \\
&= (t+q)/p \mod q
\end{aligned} 
$$
Finally, we have $|\mathrm{Tr}(C^*p^{-1})| = (q-t)/p$ in the representation of $\mathbb{F}_q$.
By the Equation 5 of [DHP+18] and Lemma 2, $\mathcal{A}$ breaks the semantic game
for the encryption $C$ as below.

$$ |\mathrm{Tr}(CC^*p^{-1})| \le 0.11s\beta^2n^5, \quad \begin{array}{l} \text{Return } C \text{ is an encryption of } 0 \\ \text{Otherwise, Return } C \text{ is an encryption of } 1 \end{array} $$

The condition on $q$ in the Theorem ensures $\mathcal{A}$ returns $m' \in \{0, 1\}$ with advantage $\delta = 1$. The adversary $\mathcal{A}$ runs in polynomial time by the argument given in Theorem 1.

**Effect of the attacks on the recommended parameters:** The recommended parameters of [DHP+18] (Appendix C, Table 1) for the different level of the (somewhat) fully homomorphic encryption scheme falls within the range of our semantic attacks, except the first level (which has a small $q$ and tolerates very little noise).

# 6 Proposed Attack on the Computational FFI problem

In this section, we first express the CFFI problem as a lattice problem. The improvement over the previous attack is that here we can avoid the additional combinatorial step (see Subsection 3.1) to solve the CFFI problem. Furthermore, we show how to solve the problem from a small number of shortest lattice vectors. We rely on the dual of the $\mathbf{x}$-basis recovered from the shortest vectors of a $q$-ary lattice generated from FFI samples.

We first define a $q$-ary lattice for the given FFI samples.

**Definition 3 (Trace lattice).** Let $A_1(\mathbf{y}), A_2(\mathbf{y}), \dots, A_k(\mathbf{y})$ be the FFI$_{q,k,n,\beta}$ samples for $k > n$. We define a generating matrix $\mathcal{T}$ of order $k \times n$ with coefficients in $\mathbb{F}_q$ and $ij$-th element defined by $\mathrm{Tr}(A_i(\mathbf{y})\mathbf{y}^{j-1})$. The $q$-ary trace lattice is defined as

$$ \mathcal{L}_{\mathcal{T},q} = \{\alpha \in \mathbb{Z}^k : \mathcal{T}C = \alpha \mod q \text{ for some } C \in \mathbb{Z}^n\} $$

By linearity of trace, the lattice $\mathcal{L}_{\mathcal{T},q}$ contains traces of every finite field element (represented in $\mathbf{y}$-basis) with respect to FFI samples $A_i(\mathbf{y})$.

**Lemma 3.** The $q$-ary lattice $\mathcal{L}_{\mathcal{T},q}$ has the following properties.

1. Its dimension is $k$.

2. Its volume is $q^{k-n}$.

3. It contains $n$ linearly independent vectors $\alpha_i$ such that $\|\alpha_i\| \le \beta$ for $1 \le i \le n$.

*Proof.* The first two properties of the Lemma are true for any $q$-ary lattice of this form. We prove the third point.
For $1 \le i \le n$, let $C_{i-1}$ be the dual $x$-basis in the finite field $\mathbb{F}_{q^n}$. Then, recalling the definition of the dual basis,

$$ \mathrm{Tr}(x^{j-1}C_{i-1}) = \delta_{i-1}^{j-1} $$

It follows from the linearity of the trace function that any FFI sample $A_j$ has

$$ |\mathrm{Tr}(A_j C_{i-1})| \le \beta $$

Thus the trace lattice contains $n$ linearly independent vectors $\alpha_i$ (corresponding to each $C_{i-1}$), such that

$$ \|\alpha_i\| = \|\mathrm{Tr}(A_j C_{i-1})\| \le \beta, \quad 1 \le j \le k $$

This concludes the proof.

Since $\beta$ is reasonably smaller than $(q-1)/2$, the $n$ vectors $\alpha_i$ are very likely the shortest vectors in the lattice $\mathcal{L}_{\mathcal{T},q}$. The lattice vectors $\alpha_i$ have Euclidean norm bounded above by $\beta\sqrt{k}$, which is much smaller than that of the Gaussian heuristics.

Note that the shortest vectors of the trace lattice correspond to the dual $x$-basis, given in the $y$-basis representation. By recomputing the dual of this dual basis, we obtain the $x$-basis in the form of its $y$-basis representation, thus recovering the hidden isomorphism $\phi$. This approach eliminate the $O(n!)$ cost associated with the combinatorial step of the previously mentioned hybrid attack.

In practice, it is generally too costly to find the $n$ shortest vectors in a lattice and thus get the complete $C_i$-basis by just using lattice reduction. When applying BKZ reductions with high block size using aborting techniques [CN11], which is often seen in cryptanalysis, it is more reasonable to only expect getting a small number of shortest lattice vectors. To account for this, we give a probabilistic approach to recover $\phi$ from a subset of two or more elements of the $C_i$-basis. This is based on the observation that each lattice vector associated with the $C_i$-basis has the same expected norm and is all as likely to appear as a shortest vector while reducing the lattice $\mathcal{L}_{\mathcal{T},q}$. We can thus assume that we are getting random elements from the $C_i$-basis.

**Lemma 4.** In a set of $m > 1$ elements, sampled uniformly at random from the set of all the dual $x$-basis, there is, with probability $\Omega(m^2/n)$, at least a pair of dual $x$-basis elements $(C_i, C_j)$ whose quotient gives $\phi$.

*Proof.* For the uniform choice of the dual $x$-basis elements, there exists at least a pair of consecutive elements $(C_i, C_j)$ with probability $O(m^2/n)$, i.e a pair with $j = i + 1$.

In the good case for us, this pair with $j = i + 1$ is going to satisfy $C_i = xC_j$ which allows us to compute $x$ as $C_i/C_j$.

To see why, recall that by definition, $C_i$ is the unique element such that, for all $0 \le k < n$, $\mathrm{Tr}(x^k C_i) = \delta_i^k$. Similarly, $C_j$ satisfies $\mathrm{Tr}(x^k C_j) = \delta_j^k$.
Rewriting $\mathrm{Tr}(\boldsymbol{x}^{k-1}(\boldsymbol{x}\boldsymbol{C}_j))$ for $\mathrm{Tr}(\boldsymbol{x}^k\boldsymbol{C}_j)$, we can check that $\boldsymbol{x}\boldsymbol{C}_j$ already satisfies all necessary conditions needed for $\boldsymbol{C}_i$, except the final one with $k = n$.

However, we now prove that even this final equation is often satisfied. When, it is, we indeed have $\boldsymbol{C}_i = \boldsymbol{x}\boldsymbol{C}_j$. We can compute the missing condition as follows:

$$ \mathrm{Tr}(\boldsymbol{x}^{n-1}(\boldsymbol{x}\boldsymbol{C}_j)) = \mathrm{Tr}(\boldsymbol{x}^n\boldsymbol{C}_j) = \mathrm{Tr}(-\boldsymbol{g}(\boldsymbol{x})\boldsymbol{C}_j), $$

the last equality holds because $\boldsymbol{x}^n = -\boldsymbol{g}(\boldsymbol{x})$ (mod $\boldsymbol{f}(\boldsymbol{x})$). Since $\boldsymbol{g}$ has degree $< n$, $\mathrm{Tr}(-\boldsymbol{g}(\boldsymbol{x})\boldsymbol{C}_j)$ is simply the coefficient of $\boldsymbol{x}^j$ in $-\boldsymbol{g}$. When $\boldsymbol{g}$ is chosen as in Section 3, as a uniform ternary polynomial of degree $\le |n/2|$, this coefficient is always zero when $j > |n/2|$ and it is zero with probability at least 1/3 otherwise.

## 6.1 Lattice Reduction on Trace lattice

In this section, we discuss the experimental results of lattice reduction to find the shortest non-zero vectors in the trace lattice. The parameter $(n, q) = (256, 32771)$ appeared in the level 1 fully homomorphic encryption scheme of [DHP$^{+}$18]. We consider $(n, q)$ close to it for our experiments.

The sample size $k$, which is the lattice dimension, is the parameter that dominates the running time of lattice reduction. If $k$ is too small, for instance, too close to $n$, the lattice reduction technique could not extract any meaningful vectors. If $k$ is too large, then the running time of the lattice reduction algorithm is too slow. In our experiments, we choose $k = 2n$.

For small $n$, it is convenient to recover the shortest vectors with a small block size BKZ algorithm, as expected$^6$. But as $n$ increases, the larger block size makes the attack inadequate. To circumvent this, we reduce the lattice dimension by applying a pre-processing lattice reduction step with a smaller block size, whose cost is negligible in the context of the attack.

The choice of the parameters $(n, q)$ in our experiments allow to find “some- what” short vectors in the trace lattice during the pre-processing step. These short vectors do not correspond to the dual $\boldsymbol{x}$-basis, as expected, but have mean- ingful properties.

Let $\tilde{\boldsymbol{C}}_i$ be the recovered finite field basis corresponding to the short lattice vectors. Heuristically, the $\tilde{\boldsymbol{C}}_i$-basis act as a pseudo dual $\boldsymbol{x}$-basis in $\mathbb{F}_{q^n}$, i.e.

$$ |\mathrm{Tr}(\tilde{\boldsymbol{C}}_i\boldsymbol{x}^j)| \lesssim \beta $$

As a result, for any FFI sample $\boldsymbol{A}_j$

$$ |\mathrm{Tr}(\tilde{\boldsymbol{C}}_i\boldsymbol{A}_j)| \lesssim n\beta^2 \qquad (7) $$

The recovered $\tilde{\boldsymbol{C}}_i$-basis contains information about $\boldsymbol{x}$. To exploit this additional information of $\boldsymbol{x}$, we generate a new integer trace lattice $\mathcal{L}_{\tilde{T}} \subset \mathbb{Z}^k$ of dimension $n$ from the lattice basis $\tilde{T}$ computed using the $\tilde{\boldsymbol{C}}_i$-basis (instead of $\boldsymbol{y}$-basis in

<footnote>$^6$ For example, we recover the complete dual $\boldsymbol{x}$-basis for the parameter $(n = 100, q = 10007)$ using BKZ block size 5.</footnote>
Definition 3).<fnref n="7" /> The observation from Equation (7) ensures the basis vectors are unusually small in a (relatively) low dimensional lattice, which allows using stronger lattice reduction algorithms effectively to recover the shortest vectors. The details of our experiments are given in Table 1.

<table><caption>**Table 1.** Experimental results</caption><thead><tr><th>n</th><th>q</th><th>Pre-Processing</th><th>C<sub>i</sub>-basis</th><th>Final</th><th>Status</th></tr></thead><tbody><tr><td>200</td><td>32771</td><td>BKZ 12</td><td>✓</td><td>BKZ 60</td><td>Solved</td></tr><tr><td>240</td><td>32771</td><td>BKZ 20</td><td>✓</td><td>-</td><td>Unsolved</td></tr><tr><td>256</td><td>32771</td><td>BKZ 21</td><td>✓</td><td>-</td><td>Unsolved</td></tr></tbody></table>

In general, the running time of a BKZ lattice reduction algorithm is exponential on the blocksize. The authors of [CN11] successfully perform high blocksize BKZ reductions (with extreme pruning originated in [GNR10]) on different lattices for a small number of rounds under the heuristics that most of the progress of BKZ algorithm is made in the early rounds. In the experiments, we also use a similar approach.

We apply a high block size BKZ algorithm (with extreme pruning) on the lattice basis $\bar{T}$, aborting regularly to check if some shortest lattice vectors are achieved, continuing otherwise. For ($n = 200, q = 32771$), we could able to find five shortest vectors within 7 days of running BKZ 60 (aborting regularly) in an Intel Xeon CPU E5-2683 v4 @ 2.10GHz with 1200 MHz processor. The Gram-Schmidt norms of the reduced bases are given in Figure 1. For other parameters, we couldn't find the shortest vectors running the (high block size) aborted BKZ reduction in the fplll software for a couple of months. The application of a more sophisticated lattice reduction approach is beyond the scope of the current paper. We, therefore, invite the cryptanalytic efforts on the other set of parameters, possibly using more advanced lattice reduction tools (example, G6K [ADH$^{+}$19]).

# 7 Conclusion

In this paper, we illustrate on the FFI problem that having a lattice-reduction approach that fails to solve a problem does not necessarily imply that the problem itself is difficult. Indeed, lattice reduction might not be the optimal strategy to approach it.

<footnote n="7">⁷ It is to be noted that we can always generate arbitrary many samples by doing simple arithmetic from the given FFI samples.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Gram-Schmidt norms in log scale</figcaption></figure>

## Acknowledgements

We thank Anand Kumar Narayanan for helpful discussions on the finite field computation. This work has been supported by the European Union's H2020 Programme under grant agreement number ERC-669891.

## References

ADH$^{+}$19. Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Ea-monn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques*, Darmstadt, Germany, May 19-23, 2019, *Proceedings, Part II*, volume 11477 of *Lecture Notes in Computer Science*, pages 717-746. Springer, 2019.

BCS97. Wieb Bosma, John J. Cannon, and Allan K. Steel. Lattices of compatibly embedded finite fields. *J. Symb. Comput.*, 24(3/4):351-369, 1997.

CN11. Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better lattice security estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, *Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings*, volume 7073 of *Lecture Notes in Computer Science*, pages 1-20. Springer, 2011.
DHP<sup>+18</sup>. Yarkin Doröz, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Berk Sunar, William Whyte, and Zhenfei Zhang. Fully homomorphic encryption from the finite field isomorphism problem. In Michel Abdalla and Ricardo Dahab, editors, *Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part I*, volume 10769 of *Lecture Notes in Computer Science*, pages 125–155. Springer, 2018.

GGH97. Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In Burton S. Kaliski Jr., editor, *Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings*, volume 1294 of *Lecture Notes in Computer Science*, pages 112–131. Springer, 1997.

GN08. Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Nigel P. Smart, editor, *Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings*, volume 4965 of *Lecture Notes in Computer Science*, pages 31–51. Springer, 2008.

GNR10. Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri Gilbert, editor, *Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings*, volume 6110 of *Lecture Notes in Computer Science*, pages 257–278. Springer, 2010.

HPS98. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Joe Buhler, editor, *Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings*, volume 1423 of *Lecture Notes in Computer Science*, pages 267–288. Springer, 1998.

HSWZ20. Jeffrey Hoffstein, Joseph H. Silverman, William Whyte, and Zhenfei Zhang. A signature scheme from the finite field isomorphism problem. *J. Math. Cryptol.*, 14(1):39–54, 2020.

KU08. Kiran S. Kedlaya and Christopher Umans. Fast modular composition in any characteristic. In *49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA*, pages 146–155. IEEE Computer Society, 2008.

LLL82. Arjen K. Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. *Mathematische annalen*, 261(ARTICLE):515–534, 1982.

Nar18. Anand Kumar Narayanan. Fast computation of isomorphisms between finite fields using elliptic curves. In Lilya Budaghyan and Francisco Rodríguez-Henríquez, editors, *Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Bergen, Norway, June 14-16, 2018, Revised Selected Papers*, volume 11321 of *Lecture Notes in Computer Science*, pages 74–91. Springer, 2018.

The22. The FPLLL Development Team. fplll, a lattice reduction library, Version: 5.4.2. Available at https://github.com/fplll/fplll, 2022.