# Indifferentiable Hashing to Elliptic Curves

## 5.1 Introduction

In this chapter, we turn to the problem, alluded to in §3.6.1, of constructing hash functions to elliptic curves that are provably well-behaved, in the sense that they can replace an elliptic curve-valued random oracle in a large, explicit class of protocols while preserve proofs of security in the random oracle model. This work was presented at CRYPTO 2010 [BCI+10a].

### 5.1.1 The random oracle model

Many cryptosystems based on elliptic curves—and all of those that involve the use of a hash function—have been proved secure in the random oracle model (ROM): examples include [BZ04, Bol03, BF01, BGLS03, BLS01, Boy03, BMP00, CC03, GS02, HL02, Jab96, LQ04, ZK02]. In the random oracle model [BR93], a hash function is modeled by a publicly accessible random function (the random oracle); the adversary cannot compute the hash function by himself but must instead query the random oracle.

A proof in the random oracle model is not fully satisfactory, since it does not imply that the scheme will remain secure when the random oracle is replaced by a concrete cryptographic hash function. It is possible to construct ad hoc schemes that are provably secure in the ROM but completely insecure when the random oracle is instantiated with any function family (see [CGH04]). Despite these separation results, a proof in the ROM is believed to indicate that there are no structural flaws in the design of the system, and that no flaw will suddenly appear when a “well-designed” hash function is used instead.

Owing to a large amount of research in the area, we have a good idea of what a well-designed bit string-valued hash function looks like, and it is relatively easy to construct from them “well-behaved” hash functions with values in such algebraic objects as finite fields $F_q$, finite rings $\mathbb{Z}_n$, and their groups of invertible elements. However, as we mentioned in Chapter 3, it is more difficult to obtain well-behaved hash functions
to elliptic curves even from a bit string-valued random oracle, especially if we want constructions with constant running time.

### 5.1.2 Constructing good hash functions from elliptic curve encodings

Given a “well-behaved” hash function $\mathfrak{h}: \{0, 1\}^* \to \mathbb{F}_q$ and an elliptic curve encoding $f: \mathbb{F}_q \to E(\mathbb{F}_q)$, the simplest way to construct a hash function $\mathfrak{H}: \{0, 1\}^* \to E(\mathbb{F}_q)$ is to set:

$$ \mathfrak{H}(m) = f(\mathfrak{h}(m)). $$

However, even if $\mathfrak{h}$ is modeled as a random oracle, this construction does not usually behave like a random oracle to $E(\mathbb{F}_q)$. Indeed, except for a very limited number of special curves, known encoding functions $f$ have an image $f(\mathbb{F}_q)$ consisting of a constant fraction < 1 of all points in $E(\mathbb{F}_q)$ (this fraction is $\approx 5/8$ for Icart’s encoding, for example, as seen in Chapter 4). This implies that, unlike a random oracle, $\mathfrak{H}$ isn’t surjective at all, and this property, together with the fact that encodings are efficiently samplable, is enough to construct an efficient distinguisher between $\mathfrak{H}$ and a random oracle (see §3.6.1).

As a result, current proofs in the random oracle model for $\mathfrak{H}$ do not guarantee the security of the resulting scheme when $\mathfrak{H}$ is instantiated as $\mathfrak{H}(m) = f(\mathfrak{h}(m))$, even if $\mathfrak{h}$ itself assumed to be ideal. In other words, even if a proof in the random oracle for $\mathfrak{H}$ can indicate that there are no structural flaws in the design of the cryptosystem, instantiating $\mathfrak{H}$ in that way could introduce a flaw that would make the resulting cryptosystem completely insecure. We give an example of such a cryptosystem in §5.4.2.

### 5.1.3 Our goal

Our main goal is to give a generic construction of an elliptic curve-valued hash function $\mathfrak{H}: \{0, 1\}^* \to E(\mathbb{F}_q)$, based on an elliptic curve encoding $f$ and random oracles $\mathfrak{h}$ for which well-behaved instantiations are known, and that does preserve random oracle proofs of security. To that end, we use the indifferentiability framework of Maurer et al. [MRH04], and try to obtain a hash function construction which is *indifferentiable* from a random oracle. General composition results then ensure that the construction can be used as a plug-in replacement for a random oracle in a large class of cryptographic protocols (namely protocols with single-stage security games, as clarified recently by Ristenpart et al. [RSS11]) while preserving security proofs.

### 5.1.4 Our results

We first introduce and formalize the notion of *admissible encoding* in §5.2 (which generalizes a similar definition from Boneh and Franklin [BF01]). Being an admissible encoding is a sufficient condition on a family of deterministic algorithms $F$ for the construction:

$$ \mathfrak{H}(m) = F(\mathfrak{h}(m)) $$

to be indifferentiable from a random oracle when $\mathfrak{h}$ is modeled as a random oracle.
As pointed out earlier, most of the known encoding functions $f$ to elliptic curves cannot give rise to a secure hash function using a construction of that form, so they cannot be admissible encodings themselves. However, we introduce two constructions using them that are indeed indifferentiable.

In §5.3, we prove that if $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ is Icart's encoding (both in odd and even characteristic), then the following defines an admissible encoding:

$$F(u, v) = f(u) + f(v)$$

where $+$ denotes the elliptic curve group law. As a result, we obtain a hash function construction which is indifferentiable from a random oracle to $E(\mathbb{F}_q)$:

$$\mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m))$$

when $\mathfrak{h}_1, \mathfrak{h}_2$ are modeled as random oracle to $\mathbb{F}_q$.

The proof relies on a rather careful inspection of the geometric properties of Icart's encoding, but the intuition behind it is in fact quite simple. The main step is to prove that all points $\mathbf{P}$ on the elliptic curve up to a bounded number of exceptions has roughly the same number of preimages under $F$. But this is true because, since $f$ is an algebraic function, the solutions $(u, v)$ of $f(u) + f(v) = \mathbf{P}$ generically form an irreducible curve of bounded genus in the affine plane over $\mathbb{F}_q$, which consists of $q + O(q^{1/2})$ points by the Hasse-Weil bound.

However, there are some difficulties to overcome to make this idea work, which involve somewhat technical tools from algebraic geometry. This makes the proof difficult to adapt to other encodings with a more complicated geometric description, such as the SWU encoding, and especially encodings to the Jacobians of higher genus curves. Chapter 6 describes a less intuitive but technically much simpler and versatile proof strategy, using arithmetic tools like character sums instead of geometry.

In §5.4, we also describe a different hash function construction for which indifferen-
tiability is very easy to establish. For a very large class of encodings $f: \mathbb{F}_q \to E(\mathbb{F}_q)$
which we call weak encodings (essentially those whose image size is at least a positive
constant fraction of all curve points, which includes all the known elliptic curve encodings
described in Chapter 3), the following construction is indifferentiable from a random
oracle:

$$\mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G}.$$

Here, $E(\mathbb{F}_q)$ is assumed to be a cyclic group with generator $\mathbf{G}$, $\mathfrak{h}_1$ is modeled as a random oracle to $\mathbb{F}_q$, and $\mathfrak{h}_2$ as a random oracle to $\mathbb{Z}/N\mathbb{Z}$ with $N = \#E(\mathbb{F}_q)$. This construction is very general and has a very simple security proof, but it is less efficient than the previous one due to the full size scalar multiplication in the elliptic curve group.

Further contributions include a number of composition lemmas for admissible encod-
ings, which we use in §5.5 to construct indifferentiable hash functions to subgroups of
elliptic curve groups, or to obtain indifferentiable hashing from bit string-valued random
oracles rather than $\mathbb{F}_q$-valued ones.
<figure><img src="image_10.png" /><figcaption>Figure 5.1: The indifferentiability notion, illustrated with construction $C^h = F \circ h$ for some function $F$, and random oracles $h$ and $\mathcal{H}$.</figcaption></figure>

# 5.2 Admissible Encodings and Indifferentiability

## 5.2.1 Preliminaries

*Indifferentiability.* We recall the notion of indifferentiability introduced by Maurer et al. in [MRH04]. We define an *ideal primitive* as an algorithmic entity which receives inputs from one of the parties and delivers its output immediately to the querying party. A *random oracle* [BR93] to a finite set $S$ is an example of ideal primitive, which provides a random output in $S$ for each new query while identical input queries are given the same answer.

**Definition 5.1 (Indifferentiability [MRH04])**. A Turing machine $C$ with oracle access to an ideal primitive $h$ is said to be $(t_{\mathcal{D}}, t_{\mathcal{S}}, q_{\mathcal{D}}, \varepsilon)$-*indifferentiable* from an ideal primitive $H$ if there exists a simulator $\mathcal{S}$ with oracle access to $H$ and running in time at most $t_{\mathcal{S}}$, such that for any distinguisher $\mathcal{D}$ running in time at most $t_{\mathcal{D}}$ and making at most $q_{\mathcal{D}}$ queries, it holds that:

$$ \left| \Pr[\mathcal{D}^{C^h,h} = 1] - \Pr[\mathcal{D}^{H,H}, \mathcal{S}^H = 1] \right| < \varepsilon $$

$C^h$ is said to be *indifferentiable* from $H$ if $\varepsilon$ is a negligible function of the security parameter $k$, for polynomially bounded $q_{\mathcal{D}}$, $t_{\mathcal{D}}$ and $t_{\mathcal{S}}$.

It is shown in [MRH04] that the indifferentiability notion is a “good” notion for substituting one ideal primitive by a construction based on another ideal primitive. That is, if the construction $C^h$ is *indifferentiable* from an ideal primitive $H$, then $C^h$ can replace $H$ in “most” cryptosystems (at least those with single-stage security games), and the resulting cryptosystem is at least as secure in the $h$ model as in the $H$ model; see [MRH04] and [RSS11] for a precise discussion.

*Statistical indistinguishability.* We also recall the definition of statistically indistinguishable distributions.
**Definition 5.2.** Let $X$ and $Y$ be two random variables over a set $S$. The distributions of $X$ and $Y$ are $\varepsilon$-statistically indistinguishable if:

$$ \sum_{s \in S} |\Pr[X = s] - \Pr[Y = s]| \le \varepsilon. $$

The two distributions are statistically indistinguishable if $\varepsilon$ is a negligible function of the security parameter.

### 5.2.2 Admissible encodings

Our goal is to construct a hash function into elliptic curves that is indifferentiable from a random oracle. First, we introduce our new notion of *admissible encoding*. It can be seen as a generalization of the definition used by Boneh and Franklin in [BF01].

**Definition 5.3 (Admissible Encoding).** A function $F: S \to R$ between finite sets is an $\varepsilon$-admissible encoding if it satisfies the following properties:

**Computable:** $F$ is computable in deterministic polynomial time.

**Regular:** for $s$ uniformly distributed in $S$, the distribution of $F(s)$ is $\varepsilon$-statistically indistinguishable from the uniform distribution in $R$.

**Samplable:** there is an efficient randomized algorithm $\mathcal{I}: R \to S \cup \{\perp\}$ such that for any $r \in R$, $\mathcal{I}(r)$ induces a distribution that is $\varepsilon$-statistically indistinguishable from the uniform distribution in $F^{-1}(r)$.

$F$ is an admissible encoding if $\varepsilon$ is a negligible function of the security parameter.

The following theorem shows that if $F: S \to R$ is an admissible encoding, then the hash function $\mathfrak{H}: \{0, 1\}^* \to R$ with:

$$ \mathfrak{H}(m) = F(\mathfrak{h}(m)) $$

is indifferentiable from a random oracle into $R$ when $\mathfrak{h}: \{0, 1\}^* \to S$ is seen as a random oracle. This shows that the construction $\mathfrak{H}$ can replace a random oracle into $R$, and the resulting scheme remains secure in the random oracle model for $\mathfrak{h}$.

**Theorem 5.1.** Let $F: S \to R$ be an $\varepsilon$-admissible encoding. The construction $\mathfrak{H}(m) = F(\mathfrak{h}(m))$ is $(t_{\mathcal{D}}, t_{\mathcal{F}}, q_{\mathcal{D}}, \varepsilon')$-indifferentiable from a random oracle, in the random oracle model for $\mathfrak{h}: \{0, 1\}^* \to S$, with $\varepsilon' = 4q_{\mathcal{D}} \cdot \varepsilon$ and $t_{\mathcal{F}} = 2q_{\mathcal{D}} \cdot t_{\mathcal{F}}$, where $t_{\mathcal{F}}$ is the maximum running time of the sampling algorithm $\mathcal{I}$ for $F$.

*Proof.* We first describe our simulator in Algorithm 5.1. As illustrated in Figure 5.1, the simulator $\mathcal{S}$ has oracle access to $\mathfrak{H}$, and must answer the random oracle queries to $\mathfrak{h}$ made by the distinguisher $\mathcal{D}$. To answer the same queries with the same values, $\mathcal{S}$ is stateful: it maintains a list $L$ of previously answered queries. It uses the sampling algorithm $\mathcal{I}$ of $F$ to answer new queries.
**Algorithm 5.1** Simulator $\mathcal{S}$ such that $(\mathfrak{H}, \mathcal{S}^{\mathfrak{H}})$ is indistinguishable from $(F \circ \mathfrak{h}, \mathfrak{h})$.

1: **procedure** $\mathcal{S}(m)$ ▷ hash $m \in \{0, 1\}^*$ to $S$
2: **if** $L$ contains a pair of the form $(m, s)$ **then** ▷ $m$ was queried previously
3: **return** $s$
4: **end if**
5: $r \leftarrow \mathfrak{H}(m)$ ▷ $m$ is new: query $\mathfrak{H}$ on it
6: $s \leftarrow \mathcal{I}(r)$
7: Append $(m, s)$ to $L$
8: **return** $r$
9: **end procedure**

We must show that the systems $(F \circ \mathfrak{h}, \mathfrak{h})$ and $(\mathfrak{H}, \mathcal{S}^{\mathfrak{H}})$ are indistinguishable. We consider a distinguisher $\mathcal{D}$ making at most $q_{\mathcal{D}}$ queries to one of the systems $(F \circ \mathfrak{h}, \mathfrak{h})$ or $(\mathfrak{H}, \mathcal{S}^{\mathfrak{H}})$ and trying to guess which of the two systems it is.

Without loss of generality, we can assume that the distinguisher makes all queries to $\mathfrak{h}(m)$ (or $\mathcal{S}^{\mathfrak{H}}$) for which there was a query to $(F \circ \mathfrak{h})(m)$ (or $\mathfrak{H}(m)$), and conversely; this gives a total of at most $2q_{\mathcal{D}}$ queries. We can then describe the full interaction between the distinguisher and the system as a sequence of triples:

$$ \text{View} = (m_i, s_i, r_i)_{1 \le i \le 2q_{\mathcal{D}}} $$

where $s_i = \mathfrak{h}(m_i)$ or $\mathcal{S}^{\mathfrak{H}}(m_i)$, and $r_i = (F \circ \mathfrak{h})(m_i)$ or $\mathfrak{H}(m_i)$. Without loss of generality we can assume that the $m_i$'s are distinct.

If the system is $(F \circ \mathfrak{h}, \mathfrak{h})$ we have $s_i = \mathfrak{h}(m_i)$ for all $i$. Therefore the $s_i$'s are uniformly and independently distributed in $S$. Moreover we have $r_i = (F \circ \mathfrak{h})(m_i) = F(s_i)$ for all $i$: hence, the distribution of each $r_i$'s is $\varepsilon$-statistically indistinguishable from the uniform distribution in $R$.

On the other hand, if the system is $(\mathfrak{H}, \mathcal{S}^{\mathfrak{H}})$ we have $r_i = \mathfrak{H}(m_i)$ for all $i$. Therefore the $r_i$'s are uniformly and independently distributed in $R$. Moreover we have $s_i = \mathcal{I}(r_i)$ for all $i$. Hence, by Lemma 5.1 below, the distribution of each $s_i$ is $2\varepsilon$-statistically indistinguishable from the uniform distribution in $S$. Moreover, from the definition of $\mathcal{I}$, they always satisfy $F(s_i) = r_i$, unless $s_i = \perp$, which happens with probability at most $\varepsilon$.

Overall, the statistical distance between View in system $(F \circ \mathfrak{h}, \mathfrak{h})$ and View in system $(\mathfrak{H}, \mathcal{S}^{\mathfrak{H}})$ is thus at most $q_{\mathcal{D}} \cdot (\varepsilon + 2\varepsilon + \varepsilon) = 4q_{\mathcal{D}} \cdot \varepsilon$. Considering the running time of the simulator, this concludes the proof. $\square$

**Lemma 5.1.** For $r$ uniformly distributed in $R$, the distribution of $s = \mathcal{I}(r)$ is $2\varepsilon$-statistically indistinguishable from the uniform distribution in $S$.

*Proof.* We let $\omega$ be the sequence of random coins used by $\mathcal{I}$. We have to show that $\delta \le 2\varepsilon$, where the statistical distance $\delta$ is given by:

$$ \delta = \sum_{s \in S} \left| \Pr_{\omega, r}[\mathcal{I}(r) = s] - \frac{1}{\#S} \right| $$
Given $s \in S$, we have $\mathcal{I}(r) = s$ only if $r = F(s)$. Therefore, $\mathrm{Pr}_{\omega,r}[\mathcal{I}(r) = s] = (1/\#R) \cdot \mathrm{Pr}_{\omega}[\mathcal{I}(F(s)) = s]$. This gives:

$$ \delta = \sum_{r \in R} \sum_{s \in F^{-1}(r)} \frac{1}{\#R} \left| \mathrm{Pr}_{\omega}[\mathcal{I}(r) = s] - \frac{\#R}{\#S} \right| \quad (5.1) $$

Now, since $F$ is an $\varepsilon$-admissible encoding, the statistical distance $\delta_1$ between the uniform distribution in $R$ and the distribution of $F(s)$ for a $s \in S$ uniformly random is at most $\varepsilon$, and we can write $\delta_1$ as:

$$ \begin{aligned} \delta_1 &= \sum_{r \in R} \left| \mathrm{Pr}_s[F(s) = r] - \frac{1}{\#R} \right| \\ &= \sum_{r \in R} \left| \frac{\#F^{-1}(r)}{\#S} - \frac{1}{\#R} \right| \\ &= \sum_{r \in R} \sum_{s \in F^{-1}(r)} \frac{1}{\#R} \left| \frac{\#R}{\#S} - \frac{1}{\#F^{-1}(r)} \right| \end{aligned} \quad (5.2) $$

Moreover, by definition of admissibility again, for each $r \in R$ the distribution of $\mathcal{I}(r)$ is $\varepsilon$-statistically indistinguishable from the uniform distribution in $F^{-1}(r)$ for all $r \in R$. This gives, for all $r \in R$:

$$ \sum_{s \in F^{-1}(r)} \left| \mathrm{Pr}_{\omega}[\mathcal{I}(r) = s] - \frac{1}{\#F^{-1}(r)} \right| \le \varepsilon. $$

Hence, summing over $r \in R$, we get:

$$ \delta_2 = \sum_{r \in R} \sum_{s \in F^{-1}(r)} \frac{1}{\#R} \left| \mathrm{Pr}_{\omega}[\mathcal{I}(r) = s] - \frac{1}{\#F^{-1}(r)} \right| \le \varepsilon \quad (5.3) $$

From (5.1), (5.2) and (5.3), we obtain $\delta \le \delta_1 + \delta_2 \le \varepsilon + \varepsilon = 2\varepsilon$ as required. $\square$

## 5.3 Our Main Construction

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ with $q \equiv 2 \pmod 3$. Let $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ denote Icart's encoding [Ica09], whose definition is recalled in §3.5.2. As we have noted already, it is easy to see that $f$ itself is not an admissible encoding to $E(\mathbb{F}_q)$ the image of $f$ consists of only a fraction of the elliptic curve points. Therefore we cannot use the construction $\mathfrak{H}(m) = f(\mathfrak{h}(m))$ for indifferentiable hashing.

In this section, we describe a different construction with the same level of efficiency that does achieve indifferentiability. We consider the following map $F: (\mathbb{F}_q)^2 \to E(\mathbb{F}_q)$:

$$ F(u_1, u_2) = f(u_1) + f(u_2) \quad (5.4) $$

which had already been considered by Icart for the construction of surjective hashing (see §4.6). We prove that $F$ is an $\varepsilon$-admissible encoding with $\varepsilon = 2^8 \cdot q^{-1/2}$, and deduce the following theorem.
**Theorem 5.2.** If $q > 2^{13}$ is any 2k-bit prime power congruent to 2 mod 3 (even or odd), and if the j-invariant of E is not in $\{0; 2592\}$, then the hash function

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) $$

is $(t_D, t_S, q_D, \varepsilon')$-indifferentiable from a random oracle, where $\varepsilon' = 2^{10} \cdot q_D \cdot 2^{-k}$, in the random oracle model for $\mathfrak{h}_1, \mathfrak{h}_2 : \{0, 1\}^* \to \mathbb{F}_q$.

In order to prove that $F$ is an admissible encoding, we write, for any $\mathbf{P} \in E(\mathbb{F}_q)$:

$$ N(\mathbf{P}) = \#\{(u, v) \in (\mathbb{F}_q)^2 \mid f(u) + f(v) = \mathbf{P}\} = \#F^{-1}(\mathbf{P}). $$

Then the following holds.

**Proposition 5.1.** If $q$ is an odd prime power congruent to 2 mod 3, and if the j-invariant of $E$ is not in $\{0; 2592\}$, then for every point $\mathbf{P} \in E(\mathbb{F}_q)$ except at most 144, we have

$$ |q - N(\mathbf{P})| \le 2^7 \cdot \sqrt{q} $$

and all the remaining points $\mathbf{P}$ satisfy $N(\mathbf{P}) \le 2^5 \cdot q$.

Sections §5.3.2 and §5.3.3 are devoted to the proof of this proposition. Intuitively, the idea of the proof is to show that, for all points $\mathbf{P} \in E(\mathbb{F}_q)$ except a few exceptional ones, $F^{-1}(\mathbf{P})$ is an irreducible algebraic curve of bounded genus in the affine plane $\mathbb{A}^2$ over $\mathbb{F}_q$. The estimate for the number of points then follows from the Hasse-Weil bound. We also show in §5.3.4 that the result extends to Icart's function $f$ in characteristic 2.

Let us now see how Proposition 5.1 implies the regularity of $F$, and how we can easily deduce that this encoding is admissible, and hence Theorem 5.2.

### 5.3.1 Admissibility of $F(u, v) = f(u) + f(v)$

To prove that $F$ is $\varepsilon$-admissible, note first that $F$ is clearly computable in deterministic polynomial time. Thus, it suffices to show that it is $\varepsilon$-regular and $\varepsilon$-samplable. Now, for any $\mathbf{P}$ not among the exceptional points, we have

$$ \left| \frac{\#F^{-1}(\mathbf{P})}{\#(\mathbb{F}_q)^2} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \left| \frac{\#F^{-1}(\mathbf{P})}{\#(\mathbb{F}_q)^2} - \frac{1}{q} \right| + \left| \frac{1}{q} - \frac{1}{\#E(\mathbb{F}_q)} \right| \\ \le \frac{2^7}{q^{3/2}} + \frac{5}{q^{3/2}} \le \frac{2^7 + 5}{q^{3/2}} $$

And on the other hand, for exceptional points $\mathbf{P}$:

$$ \left| \frac{\#F^{-1}(\mathbf{P})}{\#(\mathbb{F}_q)^2} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \frac{2^5}{q} $$

Thus, the statistical distance between the distribution of $F(u, v)$ for uniform $(u, v)$ and the uniform distribution on the curve can be bounded as

$$ \sum_{\mathbf{P} \in E(\mathbb{F}_q)} \left| \frac{N(\mathbf{P})}{q^2} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le (q + 2\sqrt{q} + 1) \cdot \frac{2^7 + 5}{q^{3/2}} + 144 \cdot \frac{2^5}{q} \le \frac{2^8}{q^{1/2}} $$
for $q > 2^{13}$, as required. This proves $\varepsilon$-regularity, with $\varepsilon = 2^8 \cdot q^{-1/2}$.

To see that $F$ is $\varepsilon$-samplable, one can consider the following randomized sampling algorithm, where $c$ is some constant to be determined later. Note that computing the set $S$ in step 3 amounts to solving univariate polynomial equations over $\mathbb{F}_q$, which is easily done in polynomial time using an algorithm such as Berlekamp's [Ber68].

<caption>**Algorithm 5.2** Sampling algorithm for $F$.</caption>

1: **repeat** $[c \cdot \lg q]$ **times**
2: &nbsp;&nbsp;&nbsp;&nbsp;pick $v \in \mathbb{F}_q$ uniformly at random
3: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow f^{-1}(\mathbf{P} - f(v))$
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $S = \emptyset$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next iteration
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pick $i$ uniformly at random in $\{1, 2, 3, 4\}$
8: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i \le \#S$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$u \leftarrow i$-th element of $S$
10: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(u, v)$
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next iteration
13: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
14: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
15: **end repeat**
16: **return** $\perp$

Since the image of $f$ contains roughly $(5/8) \cdot \#E(\mathbb{F}_q)$ points (as proved in Chapter 4), a pigeonhole argument shows that $S \ne \emptyset$ with probability at least $2 \cdot 5/8 - 1 = 1/4$. Furthermore, we always have $\#S \le 4$. Thus, each **repeat** iteration succeeds with probability at least $1/16$. Therefore, if we set $c = \frac{1}{2\lg(16/15)}$, we find that Algorithm 5.2 succeeds with probability greater than $1 - \varepsilon/2$, and steps 7–13 ensure that it yields the uniform distribution on $F^{-1}(\mathbf{P})$. This concludes the proof that $F$ is an admissible encoding.

### 5.3.2 Geometric interpretation of Icart's encoding

Icart's function $f$ admits a natural extension to the projective line over $\mathbb{F}_q$ by setting $f(\infty) = \mathbf{O}$, the neutral element of the elliptic curve. Then, consider the graph of $f$:

$$C = \{(u, \mathbf{P}) \in \mathbb{P}^1 \times E \mid f(u) = \mathbf{P}\}$$

As shown in [Ica09, Lemma 3], $C$ is the closed subscheme of $\mathbb{P}^1 \times E$ defined by

$$u^4 - 6xu^2 + 6yu - 3a = 0 \qquad (5.5)$$

In other words, Icart's function is the algebraic correspondence between $\mathbb{P}^1$ and $E$ given by (5.5).
Let $j$ be the $j$-invariant of $E$:

$$j = 1728 \cdot \frac{4a^3}{4a^3 + 27b^2} \in \mathbb{F}_q.$$

Save for a few exceptional values of $j$, we can precisely describe the geometry of $C$.

**Lemma 5.2.** If $j \notin \{0; 2592\}$, the subscheme $C$ is a geometrically integral curve on $\mathbb{P}^1 \times E$ with one triple point at infinity and no other singularity. Its normalization $\tilde{C}$ is a smooth, geometrically integral curve of genus 7. The natural map $h: \tilde{C} \to E$ is a morphism of degree 4 ramified at 12 distinct finite points of $E(\mathbb{F}_q)$, with ramification index 2.

*Proof.* As usual with Icart's function, we assume that $E$ is not supersingular, i.e. $a$ and $j$ are non-zero. The subscheme $C$ is then clearly reduced, and was shown in Chapter 4 to be geometrically connected (this is Lemma 4.3). It is thus a geometrically integral curve on the surface $\mathbb{P}^1 \times E$.

Let us determine its singular locus. First consider the affine patch of $C$ given by $u \neq \infty$ and $\mathbf{P} \neq \mathbf{O}$. It can be represented as the algebraic set of points $(u, x, y)$ in affine 3-space satisfying $y^2 = x^3 + ax + b$ as well as equation (5.5). It is smooth at all points where the map

$$(u, x, y) \mapsto (y^2 - (x^3 + ax + b), u^4 - 6xu^2 + 6yu - 3a)$$

is of rank 2. The gradient of this map is

$$(u, x, y) \mapsto \begin{pmatrix} 0 & -3x^2 - a & 2y \\ 4u^3 - 12xu + 6y & -6u^2 & 6u \end{pmatrix}.$$

Since $E$ is smooth, this is of rank 2 at a point of the curve unless:

$$\left\{ \begin{array}{l} y^2 = x^3 + ax + b \\ u^4 - 6xu^2 + 6yu - 3a = 0 \\ 4u^3 - 12xu + 6y = 0 \\ \left| \begin{array}{cc} -3x^2 - a & 2y \\ -6u^2 & 6u \end{array} \right| = 6u(2uy - 3x^2 - a) = 0. \end{array} \right.$$

Eliminating $u, x, y$ between those four equations, we find $-24a^4 - 162ab^3 = -6a(4a^3 + 27b^2) = 0$, which is impossible. Therefore, there is no singular point in this affine patch.

Turning now to points at infinity, we denote by $v$ the local coordinate $1/u$ on $\mathbb{P}^1$ in a neighborhood of $\infty$, and let $(z, w) = (1/y, x/y)$ be local coordinates on $E$ in a neighborhood of $\mathbf{O}$. First note that there is no point $(\infty, \mathbf{P}) \in C$ with $\mathbf{P} \neq \mathbf{O}$. Indeed, writing equation (5.5) in terms of $(v, x, y)$:

$$3av^4 - 6yv^3 + 6xv^2 - 1 = 0$$
we see that $v = 0$ is never a root.

Similarly, let us find points of the form $(u, \mathbf{O})$ with $u \neq \infty$. In terms of $(u, z, w)$, equation (5.5) becomes

$$zu^4 - 6wu^2 + 6u - 3az = 0.$$

For $z = w = 0$, we get only one root $u = 0$. Thus, the only point on $C$ of the form $(u, \mathbf{O})$ with $u \neq \infty$ is $(0, \mathbf{O})$, and it is easily seen to be regular: the elliptic curve equation becomes $z = bz^3 + awz^2 + w^3$, and hence the map $\mathbb{A}^3 \to \mathbb{A}^2$ defining $C$ in this patch has the following Jacobian matrix:

$$\begin{pmatrix} 0 & -3bz^2 - 2aw + 1 & -a - 3w^2 \\ 4zu^3 - 12wu + 6 & u^4 - 3a & -6u^2 \end{pmatrix}$$

which is of rank 2 for $u = z = w = 0$ (recall that the characteristic does not divide 6).

Finally, the point $(\infty, \mathbf{O})$ lies on $C$ and is a triple point. Indeed, consider the local ring $\mathcal{O} = \mathbb{F}_q[v, z, w]/(bz^3 + awz^2 - z + w^3)_{(v,z,w)}$ of $\mathbb{P}^1 \times E$ at $(\infty, \mathbf{O})$, and write the local equation of $C$ at this point:

$$3azv^4 - 6v^3 + 6wv^2 - z \in \mathcal{O}.$$

Let $\mathfrak{m} = (v, z, w)$ be the maximal ideal of $\mathcal{O}$. Since $z = bz^3 + awz^2 + w^3 \in \mathfrak{m}^3$, we see that the curve equation belongs to $\mathfrak{m}^3$. It isn't in $\mathfrak{m}^4$, however, so the multiplicity of $(\infty, \mathbf{O})$ is exactly 3 (see [Har77, Exercise V.3.4]).

Thus, the normalization $\tilde{C}$ of $C$ is a smooth geometrically integral curve, and $\tilde{C} \to C$ is an isomorphism outside $(\infty, \mathbf{O})$, whereas the fiber over $(\infty, \mathbf{O})$ consists of three points.

Consider now the map $h: \tilde{C} \to E$ deduced from the second projection $C \to E$. Since equation (5.5) is of degree 4, $h$ is a morphism of degree 4 as well. The fiber at the origin $\mathbf{O}$ of $E$ contains 4 points, namely $(0, \infty)$ and the 3 points of $\tilde{C}$ over the singular point of $C$. In particular, $h$ is unramified at infinity. The ramification points are thus the finite points $(x, y)$ of $E$ where (5.5) has a multiple root, i.e. where the discriminant $\Delta$ vanishes.

Recall that $\Delta$ is a polynomial of degree 6 in $x$. It has 6 simple roots over the algebraic closure of $\mathbb{F}_q$ provided that its own discriminant:

$$\mathrm{disc}(\Delta) = 2^{58} \cdot 3^{42} \cdot (4a^3 + 27b^2)^2 \cdot (-4a^3 + 81b^2)^3$$

is nonzero, i.e. $4a^3 \neq 81b^2$, or $j \neq 2592$. We will assume this in what follows.

None of these roots $x$ corresponds to a point $(x, y)$ on $E$ such that $y = 0$. Indeed, eliminating $x$ between $\Delta = 0$ and $x^3 + ax + b = 0$, we find $a(4a^3 + 27b^2) = 0$, which is impossible. Thus, each root of $\Delta$ corresponds to exactly two points of $E$ where $h$ is ramified. Hence the 12 distinct ramification points on $E(\mathbb{F}_q)$.

Eliminating $u, x, y$ between equation (5.5) and its first and second derivatives as well as $y^2 = x^3 + ax + b$, we find $12(-4a^3 + 81b^2) = 0$, which contradicts our assumption that $j \neq 2592$. It follows that equation (5.5) cannot have a triple root. Thus, all 12 ramification points of $h$ have ramification index 2. This allows us to compute the genus $g_{\tilde{C}}$ of $\tilde{C}$ using the Riemann-Hurwitz formula:

$$2g_{\tilde{C}} - 2 = 4(2 \cdot 1 - 2) + 12 \quad \text{and hence} \quad g_{\tilde{C}} = 7$$

as required.

□
5.3.3 The square correspondence

In this context, the function $(u,v) \mapsto f(u) + f(v)$ occurring in our hash function construction admits the following description. A point $(u,v)$ in the affine plane $\mathbb{A}^2$, or more generally in $\mathbb{P}^1 \times \mathbb{P}^1$, corresponds to $\mathbf{P}$ on the elliptic curve $E$ if and only if there is some point $(\alpha, \beta) \in \tilde{C} \times \tilde{C}$ over $(u,v)$ such that $h(\alpha) + h(\beta) = \mathbf{P}$.

Consider the surface $S = \tilde{C} \times \tilde{C}$, and define the following two morphisms. The map $p: S \to \mathbb{P}^1 \times \mathbb{P}^1$ is the square of the first projection, and $s: S \to E$ is obtained by composing $h \times h: S \to E \times E$ with the group law $E \times E \to E$. Then the set of points $(u,v) \in \mathbb{P}^1 \times \mathbb{P}^1$ corresponding to a given $\mathbf{P} \in E$ is exactly $p(s^{-1}(\mathbf{P}))$ (and we can take the intersection with $\mathbb{A}^2$ if we are only interested in affine points). This allows us to give a geometric proof of Proposition 5.1.

Let us first describe the geometry of the fibers $s^{-1}(\mathbf{P})$. Denote by $\mathbf{R}_1, \dots, \mathbf{R}_{12}$ the 12 geometric points of $E$ over which $h$ is ramified, and let $R = \{\mathbf{R}_i + \mathbf{R}_j\}_{1 \le i,j \le 12} \subset E$. The map $s$ is of rank 1 at $(\alpha, \beta)$ if and only if $h$ is of rank 1 at at least one of $\alpha$ or $\beta$, which is certainly the case when $h(\alpha)$ or $h(\beta)$ is not one the $\mathbf{R}_i$. Therefore, $s$ is smooth of relative dimension 1 over the open subscheme $E_0 = E - R$, and all points in $E_0$ have smooth curves on $S$ as fibers. The following lemma makes this more precise.

**Lemma 5.3.** The fibers of $s$ at all geometric points of $E_0$ are smooth connected curves on $S_{\tilde{\mathbb{F}}_q}$ of genus 49.

*Proof.* The morphism $s: S \to E$ is projective, and thus proper, so it admits a Stein factorization $S \to E_1 \to E$, where $s_1: S \to E_1$ has connected geometric fibers, and $E_1 \to E$ is finite [EGA III.1, 4.3.3]. We will show that, in fact, $E_1 = E$.

Consider $\alpha_i \in \tilde{C}$, $i = 0, \dots, 3$, the four points such that $h(\alpha_i) = \mathbf{O}$. Then $h$ factors as $\tilde{C} \to S \to E_1 \to E$ where the first arrow is given by $\beta \mapsto (\alpha_i, \beta)$ for some fixed $i \in \{0, \dots, 3\}$. In particular, we have surjective morphisms of curves $\tilde{C} \to E_1 \to E$. The function field $K(E_1)$ of $E_1$ is thus an intermediate field of the quartic extension $K(\tilde{C})/K(E)$. But we know by Proposition 4.1 in Chapter 4 that this quartic extension has a normal closure of Galois group $S_4$. Thus, it doesn't have any non trivial subextension: we must either have $E_1 = \tilde{C}$ or $E_1 = E$. In the latter case, we are done. Otherwise, $\tilde{C} \to E_1$ is the identity map, since $K(\tilde{C})$ doesn't have any non trivial automorphism over $K(E)$. This implies $s_1(\alpha_i, \alpha_j) = \alpha_j$ for all $i, j$. But by symmetry, we also have $s_1(\alpha_i, \alpha_j) = \alpha_i$, a contradiction.

Hence, $E_1 = E$ and $s$ has connected geometric fibers. In particular, the fiber $Z = s^{-1}(\mathbf{P})$ at any geometric point $\mathbf{P}$ of $E_0$ is a smooth connected curve. Let us compute its genus $g_Z$. To do so, observe that the image of $Z$ under $h \times h: S_{\tilde{\mathbb{F}}_q} \to (E \times E)_{\tilde{\mathbb{F}}_q}$ is the curve $E'$ of points $(\zeta, \tau)$ such that $\zeta + \tau = \mathbf{P}$. $E'$ is clearly isomorphic to $E_{\tilde{\mathbb{F}}_q}$, and is thus of genus 1. Since $h: \tilde{C} \to E$ is of degree 4, any given point $(\zeta, \tau)$ on $E'$ has $4^2 = 16$ preimages by $Z \to E'$, except when either $\zeta$ or $\tau$ is one of the 12 ramification points $\mathbf{R}_1, \dots, \mathbf{R}_{12}$ of $h$ (note that $\zeta$ and $\tau$ cannot be both ramification points since $\mathbf{P}$ is outside $R$). In this latter case, $(\zeta, \tau)$ has $3 \cdot 4 = 12$ preimages. Thus, $Z \to E'$ is a morphism of degree 16 with $2 \cdot 12 = 24$ ramification points in $E'$, each of ramification
type (2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1). Applying the Riemann-Hurwitz formula, we get

$$2g_Z - 2 = 16(2 \cdot 1 - 2) + 24 \cdot 4 \quad \text{and hence} \quad g_Z = 49$$

as stated.

□

Consider now a fiber $Z$ of $s$ at some $\mathbb{F}_q$-point $\mathbf{P}$ of $E$ not in $R$. The previous description says that $Z$ is a smooth geometrically integral curve of genus 49 on $S$. This gives a precise estimate of the number of $\mathbb{F}_q$-points on $Z$ in view of the Hasse-Weil bound:

$$|q + 1 - \#Z(\mathbb{F}_q)| \le 98\sqrt{q}.$$

What we are interested in, however, is the number of points in $p(Z)$, or more precisely even, in $p(Z) \cap \mathbb{A}^2$. But those numbers are related in a simple way when Icart's function is well-defined, i.e. $q \equiv 2 \pmod 3$.

**Lemma 5.4.** Suppose that $q \equiv 2 \pmod 3$, and let $N$ be the number of $\mathbb{F}_q$-points in $p(Z) \cap \mathbb{A}^2$. Then we have

$$q - 98\sqrt{q} - 23 \le N \le q + 98\sqrt{q} + 1.$$

*Proof.* Let $D$ be the closed subscheme of points $(\alpha, \beta)$ on $S$ such that $p(\alpha, \beta)$ has at least one component at infinity in $\mathbb{P}^1 \times \mathbb{P}^1$. Denote further by $U$ be the complementary open subscheme: $U = p^{-1}(\mathbb{A}^2)$. Then $p$ induces a bijection $U(\mathbb{F}_q) \to \mathbb{A}^2(\mathbb{F}_q) \subset (\mathbb{P}^1 \times \mathbb{P}^1)(\mathbb{F}_q)$. This is a direct consequence of the fact that $t \mapsto t^3$ is a bijection in $\mathbb{F}_q$, as explained in the proof of [Ica09, Lemma 3].

In particular, the $\mathbb{F}_q$-points of $p(Z) \cap \mathbb{A}^2$ are in bijection with $(Z \cap U)(\mathbb{F}_q)$. This immediately yields the upper bound:

$$N \le \#Z(\mathbb{F}_q) \le q + 1 + 98\sqrt{q}.$$

To obtain the lower bound, it suffices to estimate the number of $\mathbb{F}_q$-points on $Z$ outside of $U$, i.e. on $Z \cap D$. This is certainly bounded above by the number of geometric points on $Z \cap D$, which is itself not greater than the intersection number $Z \cdot D$ when $Z$ and $D$ are regarded as 1-cycles on $S$.

Let $l$ and $m$ denote the divisor classes on $S = \tilde{C} \times \tilde{C}$ of $\tilde{C} \times \{\alpha\}$ and $\{\alpha\} \times \tilde{C}$ for an arbitrary $\alpha$. Then $D \equiv n_{\infty}(l+m)$, where $\equiv$ denotes numerical equivalence and $n_{\infty}$ is the number of points on $\tilde{C}$ mapping to $\infty$ in $\mathbb{P}^1$. As seen in the proof of Lemma 5.2, we have $n_{\infty} = 3$ (the three points of $\tilde{C}$ lying over the singular point of $C$). Hence

$$Z \cdot D = 3Z \cdot (l + m).$$

On the other hand, the canonical divisor $K$ of $S$ satisfies $K \equiv (2g_{\tilde{C}} - 2)(l + m) = 12(l + m)$ (see e.g. [Har77, Exercises V.1.5(b) and V.1.9(b)]). Now $K$ appears in the adjunction formula of the intersection theory of surfaces [Har77, Proposition V.1.5]:

$$2g_Z - 2 = Z \cdot K + Z^2 = 4Z \cdot D + Z^2.$$
Since Z is a fiber of $s_0$, its self-intersection number is zero: any two fibers of $s_0$ are algebraically equivalent and disjoint. Thus $Z^2 = 0$ and we get

$$Z \cdot D = \frac{1}{4} \cdot (2g_Z - 2) = 24.$$

In particular, $\#(Z \cap D)(\mathbb{F}_q) \le 24$ and hence

$$N \ge \#Z(\mathbb{F}_q) - 24 \ge q - 98\sqrt{q} - 23$$

which concludes the proof.

□

The first part of Proposition 5.1 now follows from the previous propositions: under the hypotheses of that theorem, if $\mathbf{P} \in E(\mathbb{F}_q)$ does not belong to $R$, then $N(\mathbf{P}) = \#\{(u, v) \in (\mathbb{F}_q)^2 | f(u) + f(v) = \mathbf{P}\}$ satisfies

$$|q - N(\mathbf{P})| \le 98\sqrt{q} + 23 \le 2^7 \cdot \sqrt{q}$$

as required. And obviously, there are at most $12^2 = 144$ points in $R$.

It remains to bound $N(\mathbf{P})$ for an $\mathbb{F}_q$-point $\mathbf{P} \in R \cap E(\mathbb{F}_q)$. To do so, consider again $Z = s^{-1}(\mathbf{P})$ the fiber at such a point, and $E' \subset E \times E$ the image of $Z$ under $h \times h$ (or equivalently, the fiber of the group law of $E$ at $\mathbf{P}$). The morphism $Z \to E'$ is of degree 16, so each point has at most 16 preimages. Hence

$$N(\mathbf{P}) \le 16 \cdot \#E'(\mathbb{F}_q) \le 16(q + 1 + 2\sqrt{q}) \le 2^5 \cdot q$$

since $q \ge 5$. This concludes the proof of Proposition 5.1.

### 5.3.4 Generalization to even characteristic

The previous technique carries over to Icart's function in characteristic 2 easily (see Figure 3.4 for the definition of Icart's function in characteristic 2). In this case, if $E$ is the elliptic curve $y^2 + xy = x^3 + ax^2 + b$ over a field $\mathbb{F}_q$ of characteristic 2, the curve $C \subset \mathbb{P}^2 \times E$ defining Icart's correspondence has the equation

$$u^4 + u^2 + xu + y + a^2 = 0.$$

It is smooth except at the point $(\infty, \mathbf{O})$ which blows up into 4 regular points in the normalization $\tilde{C}$. The second projection $h: \tilde{C} \to E$ is then of degree 4 and only ramified over the single point $\mathbf{R}$ of $E$ such that $x = 0$, with ramification type (2, 2). In particular, $\tilde{C}$ is a smooth curve of genus 2.

We can then consider the map $s: S = \tilde{C} \times \tilde{C} \to E$ again, and find that the fiber $Z = s^{-1}(\mathbf{P})$ at any point $\mathbf{P} \in E - \{[2] \cdot \mathbf{R}\}$ is a smooth geometrically integral curve. The morphism of $Z$ to its image $E'$ in $E \times E$ is of degree 16 and only ramified over $(\mathbf{R}, \mathbf{P} - \mathbf{R})$ and $(\mathbf{P} - \mathbf{R}, \mathbf{R})$, with ramification type (2, 2, 2, 2, 2, 2, 2, 2). Thus, $Z$ is of genus 9.

Using the notations from the proof of Lemma 5.4, the first projection $p: S \to \mathbb{P}^1 \times \mathbb{P}^1$ still induces a bijection $U(\mathbb{F}_q) \to \mathbb{A}^2(\mathbb{F}_q)$ on $\mathbb{F}_q$-points when $q \equiv 2 \pmod 3$ and $U =$
$p^{-1}(\mathbb{A}^2)$. Moreover, if $D$ denotes the complementary divisor on $S$, we can compute $Z \cdot D = n_{\infty}Z \cdot (l+m) = 4Z \cdot (l+m)$, while $K \equiv (2g_{\tilde{C}} - 2)(l+m) = 2(l+m)$. Thus, the adjunction formula gives $2g_Z - 2 = Z \cdot K + Z^2 = \frac{1}{2}Z \cdot D$. Hence:

$$ \#(Z \cap D)(\mathbb{F}_q) \leq Z \cdot D = 2 \cdot (2g_Z - 2) = 32. $$

Therefore, for any point $\mathbf{P} \in E(\mathbb{F}_q) - \{[2] \cdot \mathbf{R}\}$, we get

$$ q - 4\sqrt{q} - 31 \leq N(\mathbf{P}) \leq q + 4\sqrt{q} + 1. $$

Furthermore, we still have $N([2] \cdot \mathbf{R}) \leq 2^5 \cdot q$ as in the previous section.

Those results show that $F: (u, v) \mapsto f(u) + f(v)$ is still an admissible function when $f$ is Icart's function in characteristic 2.

## 5.4 A More General Construction

Our construction of §5.3 has the advantage of being simple and efficient as it only requires two evaluations of Icart's function. However, the proof involves somewhat technical tools from algebraic geometry, and it is not so simple to adapt to other encoding functions, such as the SWU encoding.

At the cost of a small performance penalty, however, we describe a more general construction that applies to a large class of encoding functions satisfying a few simple axioms. Those encoding functions include Icart's function, a simpler variant of the SWU function, new deterministic encodings in characteristic 3, etc. We call them weak encodings. They are defined as follows.

**Definition 5.4 (Weak Encoding).** A function $f: S \to R$ between finite sets is said to be an $\alpha$-weak encoding if it satisfies the following properties:

**Computable:** $f$ is computable in deterministic polynomial time.

**$\alpha$-bounded:** for $s$ uniformly distributed in $S$, the distribution of $f(s)$ is $\alpha$-bounded in $R$, i.e. the inequality $\mathrm{Pr}_s[f(s) = r] \leq \alpha/\#R$ holds for any $r \in R$.

**Samplable:** there is an efficient randomized algorithm $\mathcal{I}$ such that $\mathcal{I}(r)$ induces the uniform distribution in $f^{-1}(r)$ for any $r \in R$. Additionally $\mathcal{I}(r)$ returns $N_r = \#f^{-1}(r)$.

The function $f$ is a weak encoding if $\alpha$ is a polynomial function of the security parameter.

The main difference with an admissible encoding is that in the second criterion, the distribution of $f(s)$ is only required to be $\alpha$-bounded instead of being $\varepsilon$-indistinguishable from the uniform distribution. More precisely this criterion requires that, for all $r \in R$:

$$ \mathrm{Pr}_s[f(s) = r] = \frac{\#f^{-1}(r)}{\#S} \leq \frac{\alpha}{\#R}. \qquad (5.6) $$
In view of this inequality, we see that when #R/#S is bounded, any invertible function whose preimages have bounded cardinality is a weak encoding; in particular, this is the case for Icart's function, and indeed all the elliptic curve encodings introduced in Chapter 3.

**Lemma 5.5.** Suppose #R/#S is bounded, and let $f: S \to R$ be a polynomially computable function such that $B = \max_{r \in R} \#f^{-1}(r)$ is bounded. Assume that there exists a polynomial-time algorithm $\text{Inv}$ that for any $r \in R$ outputs the set $f^{-1}(r)$. Then $f$ is an $\alpha$-weak encoding, with $\alpha = B \cdot \#R/\#S$. In particular, Icart's function $f$ is an $\alpha$-weak encoding from $\mathbb{F}_q$ to $E(\mathbb{F}_q)$ with $\alpha = 4 \cdot \#E(\mathbb{F}_q)/q$.

*Proof.* We have $\text{Pr}_s[f(s) = r] = \#f^{-1}(r)/\#S \le B/\#S = \alpha/\#R$ by taking $\alpha = B \cdot \#R/\#S$; therefore, the distribution of $f(s)$ for uniform $s \in S$ is $\alpha$-bounded in $R$. Given $\text{Inv}(r) = f^{-1}(r)$, the algorithm $\mathcal{I}(r)$ simply generates a random element in the set $f^{-1}(r)$, and lets $N_r = \#f^{-1}(r)$. $\square$

When the output set of a weak encoding is a group (such as the group of points on an elliptic curve), we can construct an admissible encoding from it as follows.

**Theorem 5.3** (Weak $\to$ Admissible Encoding). Let $\mathbb{G}$ be cyclic group of order $N$ noted additively, and let $\mathbf{G}$ be a generator of $\mathbb{G}$. Let $f: S \to \mathbb{G}$ be an $\alpha$-weak encoding. Then the function $F: S \times \mathbb{Z}_N \to \mathbb{G}$ defined by $F(s, x) = f(s) + [x] \cdot \mathbf{G}$ is an $\varepsilon$-admissible encoding into $\mathbb{G}$, with $\varepsilon = (1 - 1/\alpha)^t$ for any $t$ polynomial in the security parameter $k$, and $\varepsilon = 2^{-k}$ for $t = \alpha \cdot k$.

We prove this theorem in the next section. As a consequence, we get that if $f: S \to \mathbb{G}$ is any weak encoding to a cyclic group with generator $\mathbf{G}$, then the hash function $\mathfrak{H}: \{0, 1\}^* \to \mathbb{G}$ defined by:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G} $$

where $\mathfrak{h}_1: \{0, 1\}^* \to \mathbb{G}$ and $\mathfrak{h}_2: \{0, 1\}^* \to \mathbb{Z}_N$ are hash functions, is indifferentiable from a random oracle in the random oracle model for $\mathfrak{h}_1$ and $\mathfrak{h}_2$. In particular, this is the case when $f$ is any of the elliptic curve encodings of Chapter 3.

Note also that the construction extends to non-cyclic finite abelian groups in an obvious way. For example, if $\mathbb{G}$ is a non-cyclic elliptic curve group, it is isomorphic to the product of two cyclic groups generated by points $\mathbf{G}_1$ and $\mathbf{G}_2$ of order $N_1, N_2$. Then the following hash function is indifferentiable from a random oracle:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G}_1 + [\mathfrak{h}_3(m)] \cdot \mathbf{G}_2 $$

when $\mathfrak{h}_1, \mathfrak{h}_2, \mathfrak{h}_3$ are modeled as random oracles to $\mathbb{G}, \mathbb{Z}_{N_1}$ and $\mathbb{Z}_{N_2}$ respectively.

### 5.4.1 Proof of Theorem 5.3

We must show that $F$ is an admissible encoding. Efficient computability is trivially satisfied. Regularity is also satisfied since for uniform $(s, x) \in S \times \mathbb{Z}_N$ the distribution of $F(s, x) = f(s) + [x] \cdot \mathbf{G}$ is uniform in $\mathbb{G}$.
It remains to prove that $F$ is samplable. Let $\mathcal{I}_f$ be the sampling algorithm of the $\alpha$-weak encoding $f: S \to \mathbb{G}$ with sampling algorithm $\mathcal{I}_f$. We denote $\mathbb{G}$ as $R$ as before. Observe that when $r$ is uniformly distributed in $R$, the distribution of $\mathcal{I}_f(r)$ is not necessarily close to uniform. Therefore we first describe in Algorithm 5.3 a new sampling algorithm $\mathcal{I}'_f$ which artificially aborts with some well chosen probability dependent on the input, so as to ensure that $\mathcal{I}'_f(r)$ is uniformly distributed in $S$ (when $\mathcal{I}'_f$ does not abort).

<caption>**Algorithm 5.3** Sampling algorithm with uniformly random preimages.</caption>

1: **procedure** $\mathcal{I}'_f(r)$
2:   $(s, N_r) \leftarrow \mathcal{I}_f(r)$
3:   $\delta_r = \frac{\#R \cdot N_r}{\alpha \cdot \#S}$
4:   With probability $(1 - \delta_r)$ **return** $\perp$
5:   Otherwise **return** $s$
6: **end procedure**

$\triangleright s \in f^{-1}(r) \cup \{\perp\}$ and $N_r = \#f^{-1}(r)$
$\triangleright 0 \le \delta_r \le 1$

**Lemma 5.6.** Algorithm $\mathcal{I}'_f$ aborts with probability at most $1 - 1/\alpha$, and for $r$ uniformly random in $R$, the distribution of $\mathcal{I}'_f(r)$ under the condition that $\mathcal{I}'_f(r) \ne \perp$ is uniform in $S$.

*Proof.* Given $r \in R$, we have that $\mathcal{I}'_f(r) \ne \perp$ with probability $\delta_r$ given by:

$$ \delta_r = \frac{\#R \cdot \#f^{-1}(r)}{\alpha \cdot \#S}. $$

Hence:

$$ \Pr_r[\mathcal{I}'_f(r) \neq \perp] = \sum_{r \in R} \frac{1}{\#R} \cdot \delta_r = \frac{1}{\alpha \cdot \#S} \sum_{r \in R} \#f^{-1}(r) = \frac{1}{\alpha}. $$

By definition, $\mathcal{I}(r)$ is uniformly distributed in the set $f^{-1}(r)$. As a result, we have for any $r \in R$ and any $s \in f^{-1}(r)$:

$$ \Pr[\mathcal{I}'_f(r) = s] = \delta_r \cdot \frac{1}{\#f^{-1}(r)} = \frac{\#R}{\alpha \cdot \#S}. $$

Since $\mathcal{I}'_f(r) = s$ only if $r = f(s)$, this gives for any $s \in S$:

$$ \Pr_r[\mathcal{I}'_f(r) = s] = \frac{1}{\alpha \cdot \#S} $$

and finally for any $s \in S$:

$$ \Pr_r[\mathcal{I}'_f(r) = s | \mathcal{I}'_f(r) \neq \perp] = \frac{\Pr_r[\mathcal{I}'_f(r) = s]}{\Pr_r[\mathcal{I}'_f(r) \neq \perp]} = \frac{1}{\#S} $$

which shows that the distribution of $\mathcal{I}'_f(r)$ conditioned on $\mathcal{I}'_f(r) \ne \perp$ is uniform in $S$. This concludes the proof. $\square$
We construct the sampling algorithm $\mathcal{I}_F$ of encoding $F$ as described in Algorithm 5.4, and show that it satisfies the samplability condition in the definition of an admissible encoding.

<caption>**Algorithm 5.4** Sampling algorithm for $F$.</caption>

1: **procedure** $\mathcal{I}_F(\mathbf{P})$
2:     **repeat** $t$ **times**
3:         Randomly choose $x \in \mathbb{Z}_N$
4:         $s \leftarrow \mathcal{I}_F'(\mathbf{P} - [x] \cdot \mathbf{G})$
5:         **if** $s \neq \perp$ **then**
6:             **return** $(s, x) \in S \times \mathbb{Z}_N$
7:             **end if**
8:         **end repeat**
9:         **return** $\perp$
10:     **end procedure**

We must show that for any $\mathbf{P} \in \mathbb{G}$, the distribution of $(s, x)$ is statistically close to uniform in $F^{-1}(\mathbf{P})$. From Lemma 5.6 and the uniform distribution of $\mathbf{P} - [x] \cdot \mathbf{G} \in \mathbb{G}$, we have $s = \perp$ at step $i$ with probability at most $1 - 1/\alpha$. Therefore algorithm $\mathcal{I}_F$ eventually outputs $s = \perp$ with probability at most $(1 - 1/\alpha)^t$. Moreover, Lemma 5.6 ensures that, under the condition $s \neq \perp$, the distribution of $s$ in uniform in $S$, and hence the distribution of $(s, x)$ is uniform in $S \times \mathbb{Z}_N$. Therefore, for any $\mathbf{P} \in \mathbb{G}$ the distribution of $\mathcal{I}_F(\mathbf{P})$ is $\varepsilon$-statistically close to uniform in $F^{-1}(\mathbf{P})$, with $\varepsilon = (1 - 1/\alpha)^t$. For $t = \alpha \cdot k$, we can take $\varepsilon = 2^{-k}$; this concludes the proof of Theorem 5.3.

## 5.4.2 Discussion

We see that the construction $\mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m))$ of §5.3 requires two evaluations of Icart's encoding $f$ but no scalar multiplication in the elliptic curve. Since the cost of evaluating $f$ is essentially that of a field exponentiation, and in practice field exponentiations are roughly 10 times faster than full-size scalar multiplications in $E(\mathbb{F}_q)$, the construction of §5.3 is approximately 5 times faster than the general construction given in this section.

As discussed in §3.6.1, we note that for a number of existing schemes that are proved secure in the random oracle model into an elliptic curve, it would actually be sufficient to use $\mathfrak{H}(m) = f(\mathfrak{h}(m))$ only. This is because for many existing schemes the underlying complexity assumption (such as CDH or DDH) has the random self-reducibility property. So in the security proof one “programs” the random oracle using a random instance generated from the original problem instance. Hence, instead of letting $\mathfrak{H}(m) = \mathbf{P}$ where $\mathbf{P}$ is from the random instance, one can adapt the proof by letting $f(\mathfrak{h}(m)) = \mathbf{P}$. To make sure that $\mathfrak{h}(m)$ is uniformly distributed, one can “replay” the random instance generation depending on the number of solutions to the equation $f(u) = \mathbf{P}$, as we do in the proof of Theorem 5.3.
However it is easy to construct a cryptosystem that is secure in the random oracle model but insecure with $\mathfrak{H}(m) = f(\mathfrak{h}(m))$. Consider for example the following symmetric-key encryption scheme: to encrypt with symmetric key $k$, generate a random $r$ and compute $c = m + \mathfrak{H}(k, r)$ where the message $m$ is a point on the curve and $\mathfrak{H}$ hashes into the curve; the ciphertext is $(c, r)$. This scheme is semantically secure in the random oracle model for $\mathfrak{H}$, since it is a one-time pad. But the scheme is insecure with $\mathfrak{H}(k, r) = f(\mathfrak{h}(k, r))$ because in that case, $\mathfrak{H}(k, r)$ is not uniformly distributed. Thus, for two messages $m_0$ and $m_1$ the attacker has a good advantage in distinguishing between the encryption of $m_0$ and $m_1$.<fnref n="1" />

The advantage of the two constructions of §5.3 and 5.4 is that we have a simple criterion to plug them into existing schemes: it suffices that the scheme has a proof in the random oracle model, and a single-stage security game. Whereas with $\mathfrak{H}(m) = f(\mathfrak{h}(m))$ it seems difficult to derive a formal criterion from the previous observations.

# 5.5 Extensions

In this section we consider three extensions that apply to both hash functions from §5.3 and §5.4. We show how to hash into any prime order subgroup of an elliptic curve (with cyclic or non-cyclic group), how to use hash functions mapping into bit strings (rather than $\mathbb{F}_q$) and how to take advantage of primes $p = 2^\ell - \omega$ where $\omega$ is small. These extensions are based on composition lemmas for admissible encodings, established in Appendix 5.A.

## 5.5.1 Extension to a prime order subgroup

In many applications only a prime order subgroup of $E(\mathbb{F}_q)$ is used, so we show how to adapt the constructions of §5.3 and §5.4 to hashing into a subgroup. Let $E$ be an elliptic curve over $\mathbb{F}_q$ with $N$ points, and let $\mathcal{G}$ be a subgroup of prime order $N'$ and generator $\mathcal{G}$. Let further $\ell$ be the co-factor, i.e. $N = \ell \cdot N'$. We assume that $N'$ does not divide $\ell$ (i.e. that $(N')^2$ does not divide $N$), which is satisfied in practice for key size and efficiency reasons.

To obtain a well-behaved hash function to $\mathcal{G}$, it suffices to use the constructions of §5.3 or §5.4 and multiply the result by the cofactor $\ell$. For example, consider the hash function $\mathfrak{H}: \{0, 1\}^* \to \mathcal{G}$ defined by:

$$ \mathfrak{H}(m) = [\ell] \cdot (f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m))) \quad (5.7) $$

where $\mathfrak{h}_1, \mathfrak{h}_2: \{0, 1\}^* \to \mathbb{F}_q$ are modeled as random oracles and $f$ is Icart's function.

**Proposition 5.2.** The hash function $\mathfrak{H}$ defined by (5.7) is $(t_{\mathcal{D}}, t_{\mathcal{S}}, q_{\mathcal{D}}, \varepsilon)$-indifferentiable from a random oracle in the random oracle model for $\mathfrak{h}_1$ and $\mathfrak{h}_2$, with $\varepsilon = 2^{10} \cdot q_{\mathcal{D}} \cdot 2^{-k}$.

<footnote n="1">¹If we take Icart's function for $f$, this is even worse: given $c$ the attacker can easily determine whether there exists $u$ and $v$ such that $c - m_0 = f(u)$ or $c - m_1 = f(v)$ and if one of the two equations has no solution then the attacker recovers the plaintext without uncertainty (this happens with good probability over $r$).</footnote>
Informally, we show that the composition of two admissible encodings remains an (almost) admissible encoding, and that multiplication by a co-factor is an $\epsilon$-admissible encoding, with $\epsilon = 0$. This proves that $\mathfrak{H}$ is an indifferentiable hash function. See Appendix 5.A.2 for the proof.

The same result holds for the construction of §5.4. In this case for both cyclic and non-cyclic elliptic curves we simply use $\mathfrak{H}(m) = [\ell] \cdot f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G}$ where $\mathbf{G}$ is a generator of the subgroup.

### 5.5.2 Extension to bit string-valued random oracles

The constructions in the previous sections are based on hash functions into $\mathbb{F}_q$ or $\mathbb{Z}_N$. However in practice a hash function outputs a fixed length string in $\{0, 1\}^\ell$. We can modify our construction as follows. We consider an elliptic curve $E$ over $\mathbb{F}_p$, with $p$ a $2k$-bit prime. We define the hash function $\mathfrak{H}: \{0, 1\}^* \to E(\mathbb{F}_p)$ with:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m) \bmod p) + f(\mathfrak{h}_2(m) \bmod p) $$

where $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are two hash functions from $\{0, 1\}^*$ to $\{0, 1\}^{3k}$ and $f$ is Icart's function.

**Proposition 5.3.** The previous hash function $\mathfrak{H}$ is $(t_\mathcal{D}, t_\mathcal{F}, q_\mathcal{D}, \epsilon)$-indifferentiable from a random oracle, in the random oracle model for $\mathfrak{h}_1$ and $\mathfrak{h}_2$, with $\epsilon = 2^{11} \cdot q_\mathcal{D} \cdot 2^{-k}$.

Informally, we first show that reduction modulo $p$ is an admissible encoding from $\{0, 1\}^\ell$ to $\mathbb{F}_p$ if $2^\ell \gg p$. Since the composition of two admissible encodings remains an (almost) admissible encoding, this shows that $F(u, v) = f(u \bmod p) + f(v \bmod p)$ is also an admissible encoding into $E(\mathbb{F}_p)$ and therefore $\mathfrak{H}$ is an indifferentiable hash function. Of course, the same result holds for the general construction of §5.4. See Appendix 5.A.3 for the proof.

### 5.5.3 Extension to primes $p = 2^\ell - \omega$

We show a slightly more efficient construction for primes $p$ of the form $p = 2^\ell - \omega$ for small $\omega$, as used for example in the NIST curves [FIPS186-3]. Let $E$ be an elliptic curve over $\mathbb{F}_p$ for such a prime $p$. Our construction $\mathfrak{H}: \{0, 1\}^* \to E(\mathbb{F}_p)$ is as follows:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m) \bmod p) + f(\mathfrak{h}_2(m) \bmod p) $$

where, this time, $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are two hash functions from $\{0, 1\}^*$ to $\{0, 1\}^\ell$ and $f$ is Icart's function. Note that the output size $\ell$ of $\mathfrak{h}_1$ and $\mathfrak{h}_2$ is the same as the bit size of $p$, as opposed to the previous section in which we took $\ell = 3k$ for a $2k$-bit prime $p$.

**Proposition 5.4.** $\mathfrak{H}$ is $(t_\mathcal{D}, t_\mathcal{F}, q_\mathcal{D}, \epsilon)$-indifferentiable from a random oracle, in the random oracle model for $\mathfrak{h}_1$ and $\mathfrak{h}_2$, with $\epsilon = q_\mathcal{D} \cdot (2^{10} \cdot 2^{-\ell/2} + 4\omega \cdot 2^{-\ell})$.

The proof is similar to the proof of Proposition 5.3, except that since $p \approx 2^\ell$, reduction modulo $p$ is now a generalized admissible encoding from $\{0, 1\}^\ell$ to $\mathbb{F}_p$. See Appendix 5.A.4 for the full proof. The same result holds for the general construction of §5.4, where we can take $\mathfrak{H}(m) := f(\mathfrak{h}_1(m) \bmod p) + [\mathfrak{h}_2(m)] \cdot \mathbf{G}$ with $\mathfrak{h}_1, \mathfrak{h}_2: \{0, 1\}^* \to \{0, 1\}^\ell$.
# 5.A Composition Lemmas

## 5.A.1 Generalized admissible encodings

The propositions of §5.5.1, §5.5.2 and §5.5.3 fit in a common framework: they assert that some function is admissible, and that we still get indifferentiable hashing when composing them with one of our constructions.

It is not quite correct that composing two admissible encodings yields another admissible encoding. To circumvent this problem, we introduce the slightly more general notion of generalized admissible encoding. We show that admissible encodings are generalized admissible encoding; that generalized admissible encodings are sufficient for indifferentiability; and that the composition of two admissible encodings is again a generalized admissible encoding.

**Definition 5.5 (Generalized Admissible Encoding).** A function $F: S \to R$ is said to be an $\varepsilon$-generalized admissible encoding if it satisfies the following properties:

**Computable:** $F$ is computable in deterministic polynomial time;

**Invertible:** there exists a probabilistic polynomial time algorithm $\mathcal{I}_F$ such that $\mathcal{I}_F(r) \in F^{-1}(r) \cup \{\perp\}$ for all $r \in R$, and the distribution of $\mathcal{I}_F(r)$ is $\varepsilon$-statistically indistinguishable from the uniform distribution in $S$ when $r$ is uniformly distributed in $R$.

$F$ is an generalized admissible encoding if $\varepsilon$ is a negligible function of the security parameter.

From Lemma 5.1 we have that an $\varepsilon$-admissible encoding is also a $2\varepsilon$-generalized admissible encoding. The next lemma says that Definition 5.5 is sufficient for obtaining the indifferentiability property; it follows immediately from our proof of Theorem 5.1.

**Lemma 5.7.** Let $F: S \to R$ be an $\varepsilon$-generalized admissible encoding. The construction $H(m) = F(h(m))$ is $(t_D, t_S, q, \varepsilon')$-indifferentiable from a random oracle, in the random oracle model for $h: \{0,1\}^* \to S$, with $\varepsilon' = 2q\varepsilon$ and $t_S = 2q \cdot t_I$, where $t_I$ is the maximum running time of $F$'s sampling algorithm.

Finally we prove that the composition of two generalized admissible encoding remains a generalized admissible encoding.

**Lemma 5.8.** Let $F: S \to R$ be an $\varepsilon_1$-generalized admissible encoding and $G: R \to T$ be an $\varepsilon_2$-generalized admissible encoding. Then $G \circ F$ is an $(\varepsilon_1 + \varepsilon_2)$-generalized admissible encoding from $S$ to $T$.

*Proof.* Firstly, $G \circ F$ is computable in polynomial time. Secondly, given $t$ uniformly distributed in $T$, the random variable $r = \mathcal{I}_G(t)$ is $\varepsilon_2$-statistically indistinguishable from the uniform distribution in $R$. Thus $s = \mathcal{I}_F(r)$ is $(\varepsilon_1 + \varepsilon_2)$-statistically indistinguishable from the uniform distribution in $S$. $\square$
### 5.A.2 Proof of Proposition 5.2

Proposition 5.2 is then an immediate consequence of Lemma 5.8 and of the following result.

**Lemma 5.9.** The map $M_\ell : E(\mathbb{F}_q) \to \mathbb{G}$, $\mathbf{P} \mapsto [\ell] \cdot \mathbf{P}$ is an $\varepsilon$-admissible encoding, with $\varepsilon = 0$.

*Proof.* The proof is the same as the proof of [BF01, Lemma 5.1]. Since $M_\ell$ is a group homomorphism, the distribution of $M_\ell(\mathbf{P})$ is uniform in $\mathbb{G}$ for uniform $P \in E$.

The group $E(\mathbb{F}_q)$ is isomorphic to $\mathbb{Z}_{\ell_1 N'} \times \mathbb{Z}_{\ell_2}$ for some $\ell_1, \ell_2$ such that $\ell = \ell_1 \ell_2$. Let $\mathbf{G}_1, \mathbf{G}_2$ be the points corresponding to $(1,0)$ and $(0,1)$ under this isomorphism. Given $\mathbf{Q} \in \mathbb{G}$, the sampling algorithm picks $u \in \mathbb{Z}_{\ell_1}$ and $v \in \mathbb{Z}_{\ell_2}$ uniformly at random, and returns $\mathbf{P} = [1/\ell] \cdot \mathbf{Q} + [uN'] \cdot \mathbf{G}_1 + [v] \cdot \mathbf{G}_2$. Here $1/\ell$ is computed in $(\mathbb{Z}_{N'})^*$. We have that $[\ell] \cdot \mathbf{P} = \mathbf{Q}$ as required, and $\mathbf{P}$ is uniformly distributed among the preimages of $\mathbf{Q}$ under $M_\ell$. $\square$

### 5.A.3 Proof of Proposition 5.3

Let $p$ be an integer. We first show that reduction modulo $p$ is an admissible encoding from $\{0,1\}^\ell$ to $\mathbb{Z}_p$ if $2^\ell \gg p$.

**Lemma 5.10** ($\{0,1\}^\ell \to \mathbb{Z}_p$). Let $p$ be an integer and $k$ be a security parameter. Let $\ell = k + \lceil \log_2 p \rceil + 1$. The function $\text{Mod}_p : [0, 2^\ell - 1] \to \mathbb{Z}_p$ with $\text{Mod}_p(x) = x \bmod p$ is a $2^{-k}$-generalized admissible encoding.

*Proof.* Let $\mu \in \mathbb{Z}$ such that $2^\ell - p < \mu \cdot p \le 2^\ell$. We consider the sequence:

$$ \{0,1\}^\ell \xrightarrow{F} [0, \mu \cdot p] \xrightarrow{G} \mathbb{Z}_p $$

where $F(x) = x \bmod (\mu \cdot p)$ and $G(y) = y \bmod p$. We show that both $F$ and $G$ are generalized admissible encodings; therefore from Lemma 5.8 the composition of $F$ and $G$ remains a generalized admissible encoding. For $F$ we actually prove a slightly more general result.

**Lemma 5.11.** Let $F : S \to (S \cup \Delta_2) \setminus \Delta_3$ be a polynomially computable function such that $F(x) = x$ for all $x \in S \setminus \Delta_1$. Assume that set membership for $S \setminus \Delta_1$ can be decided in polynomial time. Then $F$ is an $\varepsilon$-generalized admissible encoding, with $\varepsilon = (\#\Delta_1 + \#\Delta_2 + \#\Delta_3)/\#S$.

*Proof.* Given $x \in S \cup \Delta_2$, the sampling algorithm $\mathcal{I}_F(x)$ returns $x$ for $x \in S \setminus \Delta_1$ and $\perp$ otherwise. Therefore for uniform $x \in (S \cup \Delta_2) \setminus \Delta_3$ the distribution of $\mathcal{I}_F(x)$ is $\varepsilon$-indistinguishable from the uniform distribution in $S$, with $\varepsilon = (\#\Delta_1 + \#\Delta_2 + \#\Delta_3)/\#S$. $\square$

Applying Lemma 5.11 with $S = \{0,1\}^\ell$, $\Delta_1 = [\mu \cdot p, 2^\ell - 1[$, $\Delta_2 = \emptyset$ and $\Delta_3 = \Delta_1$, we obtain that $F$ is an $\varepsilon$-generalized admissible encoding, with $\varepsilon = 2p/2^\ell \le 2^{-k}$. Moreover,
it is easy to see that $G$ is an $\varepsilon$-admissible encoding for $\varepsilon = 0$. From Lemma 5.8 the composition of two generalized admissible encodings remains a generalized admissible encoding. This concludes the proof of Lemma 5.10. $\square$

We now proceed with the proof of Proposition 5.3. With $p$ a $2k$-bit prime and $\ell = 3k$, from Lemma 5.10 we obtain that reduction mod $p$ is a $2^{-k+1}$-admissible encoding from $\{0,1\}^\ell$ to $\mathbb{Z}_p$. Using Lemma 5.8, this shows that $F: \{0,1\}^\ell \times \{0,1\}^\ell \to E(\mathbb{F}_p)$ with:

$$F(u, v) = f(u \bmod p) + f(v \bmod p)$$

is an $\varepsilon$-generalized admissible encoding with $\varepsilon = 2^9 \cdot 2^{-k} + 2^{-k+1} \le 2^{10} \cdot 2^{-k}$. Applying Lemma 5.7, this proves Proposition 5.3.

### 5.A.4 Proof of Proposition 5.4

We consider the function $G: \{0,1\}^\ell \to \mathbb{Z}_p$ with $G(u) = u \bmod p$. Since $p = 2^\ell - \omega$, applying Lemma 5.11 with $S = \{0,1\}^\ell$, $\Delta_1 = [p, 2^\ell[, \Delta_2 = \emptyset$ and $\Delta_3 = \Delta_1$, we obtain that $G$ is an $\varepsilon$-generalized admissible encoding with $\varepsilon = 2\omega \cdot 2^{-\ell}$. Using Lemma 5.8, this shows that $F: \{0,1\}^\ell \times \{0,1\}^\ell \to E(\mathbb{F}_p)$ with:

$$F(u, v) = f(u \bmod p) + f(v \bmod p)$$

is an $\varepsilon$-generalized admissible encoding with $\varepsilon = 2^9 \cdot 2^{-\ell/2} + 2\omega \cdot 2^{-\ell}$. Applying Lemma 5.7, this proves Proposition 5.4.
<figure><img src="image_11.png" /></figure>
# Well-Distributed Encodings: A Framework for Indifferentiable Hashing to (Hyper)elliptic Curves

## 6.1 Introduction

### 6.1.1 Background

In the previous chapter, we considered the problem of constructing “well-behaved” hash functions to elliptic curves based on the constant-time encodings presented in Chapter 3. We mainly proposed two constructions, both shown to be *indifferentiable from a random oracle*, which implies, as we discussed previously, that they can serve as plug-in replacement for random oracles in most cryptosystems while preserving security proofs in the random oracle model.

The first construction is as follows:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) $$

where $f$ is Icart's encoding [Ica09] and $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are modeled as random oracles to $\mathbb{F}_q$. This construction has the advantage of being quite efficient, requiring only two evaluations of $f$ (and hence, essentially two exponentiations in $\mathbb{F}_q$). However, the geometric proof given in §5.3 only applies to Icart's encoding, and seems difficult to generalize to elliptic curve encodings with a more complicated geometric description, such as the SWU encoding [SvdW06, Ula07, BCI+10a], and even more so to a higher genus setting. In fact, even extending the result to an encoding that is very close to Icart's, such as the Hessian curve encoding of Farashahi [Far11], while most likely possible, would require studying the geometric properties of the morphisms involved all over again from scratch.

The second construction, for a cyclic elliptic curve group of order $N$ and generator $\mathbf{G}$, can be written as:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G} $$
where $f$ is essentially any of the known elliptic curve encodings, and $h_1$ and $h_2$ are modeled as random oracles to $\mathbb{F}_q$ and $\mathbb{Z}_N$ respectively. The indifferentiability proof for this construction is much simpler, and it isn't restricted to just Icart's encoding (indeed, it applies to all so-called weak encodings, which is a very mild condition). However it is also much less efficient, and still does not readily generalize to hyperelliptic curves.

## 6.1.2 Our contributions

In this chapter, we introduce a new approach to deal with hash function constructions of the more general form:

$$ \mathfrak{H}(m) = f(h_1(m)) + \dots + f(h_s(m)) \qquad (6.1) $$

when $f$ is any of the known deterministic encodings. We can show in particular that this construction is well-behaved (indifferentiable from a random oracle, in the random oracle model for the $\mathbb{F}_q$-valued hash functions $h_i$) as soon as $s$ is greater than the genus of the target curve (that is, $s \ge 2$ for elliptic curves, $s \ge 3$ for genus 2 curves, etc.). In particular, with this new approach, we recover the results of the previous chapter about Icart's function as a special case, and with sharper bounds. The methodology also extends to all known deterministic encodings, including encodings to hyperelliptic curves.

For that purpose, we introduce the notion of *well-distributed encoding*, based on a new type of character sums associated with characters of the groups of points of the Jacobians of the target curves. We show that these sums can be estimated using classical results of Weil [Wei95] and Bombieri [Bom66], and combine these estimates with standard number theoretic technique in order to get explicit regularity results for functions of the form $(u_1, \dots, u_s) \mapsto f(u_1) + \dots + f(u_s)$.

An expanded version of this work is to appear in *Math. Comp.* [FFS$^{+}$11].

## 6.1.3 Outline

In §6.2, we introduce the notion of *well-distributed encoding*, and show how it can be used to derive regularity results formally (Theorem 6.1 and Theorem 6.2). Combining these results with those of Chapter 5, we obtain, in essence, that a well-distributed encoding can be used in a construction of the form (6.1) to obtain an indifferentiable hash function.

We then introduce some arithmetic machinery in §6.3 to establish Theorem 6.3. This theorem reduces the problem of proving that a given encoding is well-distributed to checking some relatively simple geometric properties of the morphisms of curves associated with an encoding (which is a lot simpler than the higher-dimensional geometry that the approach of §5.3 required).

And finally, in §6.4, we pick three representative examples of deterministic encodings to elliptic and hyperelliptic curves, apply this theorem to prove that they are well-distributed, and deduce from our general results that they give rise to hash functions indifferentiable from a random oracle. In particular, we obtain indifferentiable hashing to Jacobians of certain hyperelliptic curves.
## 6.2 Well-Distributed Encodings

### 6.2.1 Character sums

Consider an encoding $f$ into a curve $X$, and let $J$ denote the Jacobian of $X$. Assume that $X$ has an $\mathbb{F}_q$-rational point $O$, so that we can fix an embedding $X \to J$ (sending a point $P$ to the degree 0 divisor $(P) - (O)$). Regularity properties of functions $f^{\otimes s}$ of the form:

$$f^{\otimes s}: (\mathbb{F}_q)^s \to J(\mathbb{F}_q) \\ (u_1, \dots, u_s) \mapsto f(u_1) + \dots + f(u_s)$$

can be derived formally from the behavior of $f$ with respect to characters of $J(\mathbb{F}_q)$. More precisely, introduce the character sums

$$S_f(\chi) = \sum_{u \in \mathbb{F}_q} \chi(f(u)), \qquad (6.2)$$

where $\chi$ is any character of the abelian group $J(\mathbb{F}_q)$. We say that $f$ is *well-distributed* if we have good bounds on the magnitude of $S_f(\chi)$ for nontrivial characters $\chi$.

**Definition 6.1.** Let $X$ be a smooth projective curve over a finite field $\mathbb{F}_q$, $J$ its Jacobian, $f$ a function $\mathbb{F}_q \to X(\mathbb{F}_q)$ and $B$ a positive constant. We say that $f$ is *B-well-distributed* if for any nontrivial character $\chi$ of $J(\mathbb{F}_q)$, the following holds:

$$|S_f(\chi)| \le B\sqrt{q}. \qquad (6.3)$$

We say that $f$ is *well-distributed* if it is *B-well-distributed* for some $B$ bounded independently of the security parameter.

As we show in §6.4, essentially all known deterministic encoding functions into elliptic and hyperelliptic curves satisfy (6.3) and we can thus establish results on the regularity of $f^{\otimes s}$ for any such encoding similar to those obtained in Chapter 5 for $f^{\otimes 2}$ when $f$ is Icart's function.

### 6.2.2 Collision probability

Besides character sums our estimates also depend on the number of solutions $W_f$ to the equation $f(u) = f(v)$ where $u, v \in \mathbb{F}_q$. We note that

$$\rho_f = W_f/q^2$$

is the probability of a collision. For all functions considered in this chapter we have a bound of the type

$$\rho_f \le \frac{A_0}{q} + \frac{B_0}{q^2} \qquad (6.4)$$

with some explicit constants $A_0$ and $B_0$ (different for each function $f$).
### 6.2.3 Distribution of image sums

Fix a positive integer $s$, and consider for any element $\mathbf{D} \in J(\mathbb{F}_q)$ the number of tuples $(u_1, \dots, u_s)$ such that $\mathbf{D} = f(u_1) + \dots + f(u_s)$:

$$N_s(\mathbf{D}) = \#\{(u_1, \dots, u_s) \in (\mathbb{F}_q)^s \mid \mathbf{D} = f(u_1) + \dots + f(u_s)\}$$

We can establish the following result.

**Theorem 6.1.** If $f: \mathbb{F}_q \to X(\mathbb{F}_q)$ is a B-well-distributed encoding into a curve $X$, then for all $\mathbf{D} \in J(\mathbb{F}_q)$, we have:

$$\left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{B^{s-2}}{q^{s/2-1}} \left( \rho_f - \frac{1}{\#J(\mathbb{F}_q)} \right).$$

*Proof.* Using the orthogonality relation

$$\sum_{\chi} \chi(\mathbf{D}) = \begin{cases} \#J(\mathbb{F}_q) & \text{if } \mathbf{D} \text{ is the zero divisor } J(\mathbb{F}_q) \\ 0 & \text{otherwise,} \end{cases}$$

where the summation is over all characters of $J(\mathbb{F}_q)$, $N_s(\mathbf{D})$ can be expressed in terms of character sums:

$$\begin{aligned} N_s(\mathbf{D}) &= \sum_{u_1, \dots, u_s \in \mathbb{F}_q} \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi} \chi(f(u_1) + \dots + f(u_s) - \mathbf{D}) \\ &= \sum_{\chi} \frac{\chi(-\mathbf{D})}{\#J(\mathbb{F}_q)} \sum_{u_1, \dots, u_s \in \mathbb{F}_q} \chi(f(u_1) + \dots + f(u_s)) \\ &= \sum_{\chi} \frac{\chi(-\mathbf{D})}{\#J(\mathbb{F}_q)} (S_f(\chi))^s. \end{aligned}$$

Putting aside the contribution of the trivial character $\chi_0$, we get:

$$N_s(\mathbf{D}) - \frac{q^s}{\#J(\mathbb{F}_q)} = \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi \neq \chi_0} \chi(-\mathbf{D}) (S_f(\chi))^s.$$

Therefore, using (6.3), we derive

$$\left| N_s(\mathbf{D}) - \frac{q^s}{\#J(\mathbb{F}_q)} \right| \le \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi \ne \chi_0} |S_f(\chi)|^s \le \frac{(B\sqrt{q})^{s-2}}{\#J(\mathbb{F}_q)} \sum_{\chi \ne \chi_0} |S_f(\chi)|^2.$$

On the other hand, $W_f$, defined in §6.2.2, is just:

$$W_f = \#\{(u_1, u_2) \in (\mathbb{F}_q)^2 \mid f(u_1) - f(u_2) = 0\} = \sum_{u_1, u_2 \in \mathbb{F}_q} \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi} \chi(f(u_1) - f(u_2))$$

and hence the same computations as above give:

$$W_f - \frac{q^2}{\#J(\mathbb{F}_q)} = \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi \neq \chi_0} S_f(\chi)S_f(\bar{\chi}) = \frac{1}{\#J(\mathbb{F}_q)} \sum_{\chi \neq \chi_0} |S_f(\chi)|^2 \quad (6.5)$$

from which the result follows immediately. $\square$
We see from (6.5) that

$$ \rho_f - \frac{1}{\#J(\mathbb{F}_q)} \le \frac{B^2}{q}. \qquad (6.6) $$

Therefore we have the following corollary.

**Corollary 6.1.** If $f: \mathbb{F}_q \to X(\mathbb{F}_q)$ is a B-well-distributed encoding into a curve $X$, then for all $\mathbf{D} \in J(\mathbb{F}_q)$, we have:

$$ \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{B^s}{q^{s/2}}. $$

Suppose that $X$ is of genus $g_X$. Then $\#J(\mathbb{F}_q) = q^{g_X} + O(q^{g_X - 1/2})$, so the bound of Corollary 6.1 is negligible compared to $1/\#J(\mathbb{F}_q)$ provided that $s/2 > g_X$. In other words, if $f$ is a well-distributed encoding, then for $s > 2g_X$, all elements $D \in J(\mathbb{F}_q)$ have the same number of preimages by $f^{\otimes s}$ up to negligible deviation.

When $f$ is Icart's function, this says that all the points of the target elliptic curve have almost the same number of preimages by $f^{\otimes s}$ for $s \ge 3$. This cannot be improved to $s = 2$, as the analysis in the proof of Proposition 5.1 in the previous chapter shows that there is in fact a bounded number of points which have several times more preimages by $f^{\otimes 2}$ than the others.

Nevertheless, we could obtain our indifferentiability result by bounding the statistical distance between the distribution defined by $f^{\otimes 2}$ and the uniform distribution. We can establish a general result of this type for well-distributed encodings.

**Theorem 6.2.** If $f: \mathbb{F}_q \to X(\mathbb{F}_q)$ is a B-well-distributed encoding into a curve $X$, then the statistical distance between the distribution defined by $f^{\otimes s}$ on $J(\mathbb{F}_q)$ and the uniform distribution is bounded as:

$$ \sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{B^{s-1}}{q^{(s-1)/2}} \sqrt{\rho_f \#J(\mathbb{F}_q) - 1}. $$

*Proof.* Consider first the sum of squared deviations. Let

$$ V_s = \sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right|^2. $$

Then, as in the proof of Theorem 6.1, we have:

$$ \begin{aligned} V_s &= \sum_{\mathbf{D} \in J(\mathbb{F}_q)} \frac{1}{q^{2s} \#J(\mathbb{F}_q)^2} \sum_{\chi, \eta \neq \chi_0} \chi(-\mathbf{D}) \bar{\eta}(-\mathbf{D}) \left( \sum_{u,v \in \mathbb{F}_q} \chi(f(u)) \bar{\eta}(f(v)) \right)^s \\ &= \frac{1}{q^{2s} \#J(\mathbb{F}_q)^2} \sum_{\chi, \eta \neq \chi_0} \left( \sum_{\mathbf{D} \in J(\mathbb{F}_q)} \bar{\chi}(\mathbf{D}) \eta(\mathbf{D}) \right) \left( \sum_{u,v \in \mathbb{F}_q} \chi(f(u)) \bar{\eta}(f(v)) \right)^s \\ &= \frac{1}{q^{2s} \#J(\mathbb{F}_q)} \sum_{\chi \neq \chi_0} |S_f(\chi)|^{2s}. \end{aligned} $$
Now, using (6.5), we derive

$$V_s \le \frac{B^{2s-2}}{q^{s-1}} \left( \rho_f - \frac{1}{\#J(\mathbb{F}_q)} \right).$$

On the other hand, by the Cauchy-Schwarz inequality, we have:

$$\sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \sqrt{\#J(\mathbb{F}_q) V_s}$$

and combining the two previous estimates concludes the proof. □

In view of (6.6), the following corollary follows.

**Corollary 6.2.** If $f: \mathbb{F}_q \to X(\mathbb{F}_q)$ is a B-well-distributed encoding into a curve $X$, then the statistical distance between the distribution defined by $f^{\otimes s}$ on $J(\mathbb{F}_q)$ and the uniform distribution is bounded as:

$$\sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{B^s}{q^{s/2}} \sqrt{\#J(\mathbb{F}_q)}.$$

In particular, we see from Corollary 6.2 that if $f$ is a well-distributed encoding, then for $s > g_X$, the distribution defined by $f^{\otimes s}$ on $J(\mathbb{F}_q)$ is statistically indistinguishable from the uniform distribution. If $f$ is also computable and samplable (which is easily verified to be the case when $f$ is any of the known deterministic encodings), then it is admissible. In particular, the following hash function construction:

$$\mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + \dots + f(\mathfrak{h}_s(m)) \quad (s = g_X + 1)$$

is indifferentiable from a random oracle if $\mathfrak{h}_1, \dots, \mathfrak{h}_s$ are seen as independent random oracles into $\mathbb{F}_q$.

## 6.3 Character Sums on Curves

Let $Y \to X$ be a morphism of curves<fnref n="1" /> over $\mathbb{F}_q$ which is an abelian covering with Galois group $G$ (that is, a non-constant morphism such that the corresponding extension of function fields $\mathbb{F}_q(Y)/\mathbb{F}_q(X)$ is abelian with Galois group $G$).

Any character of $G$ determines, via the Artin map, a corresponding character on the group of $\mathbb{F}_q$-divisors on $X$ prime to the ramification locus $S$ of $Y \to X$, which extends to a multiplicative map $\chi$: $\mathrm{Div}_{\mathbb{F}_q}(X) \to \mathbb{C}$ vanishing on divisors not prime to $S$. Let us call such a map $\chi$ an *Artin character* of $X$. One associates to $\chi$ a distinguished effective divisor $f(\chi)$ of support $S$ called the conductor (in particular, if $Y \to X$ is unramified, $f(\chi) = 0$; the character itself is then said to be unramified).

<footnote n="1">¹In this section, “curve over $k$” means smooth, projective, geometrically connected curve over $k$.</footnote>
**Example 6.1.** We consider the following examples of Artin characters.

* Let $E$ be an elliptic curve over $\mathbb{F}_q$. Then any character of the abelian group $E(\mathbb{F}_q)$ extends to an unramified Artin character of $E$. Indeed, if $F$ denotes the Frobenius endomorphism of $E$, $(1-F): E \to E$ is an unramified abelian covering with group $G = E(\mathbb{F}_q)$, and characters of $G$ determine Artin characters of $E$ whose restriction to $E(\mathbb{F}_q)$ is as expected.

* More generally, let $X$ be any curve over $\mathbb{F}_q$ with an $\mathbb{F}_q$-point, and $J$ its Jacobian. As usual, we can embed $X$ in $J$ using this rational point. Then any character of the group $J(\mathbb{F}_q)$ extends to an Artin character of $X$. It is constructed similarly; $(1-F): J \to J$ is again an unramified abelian covering with group $J(\mathbb{F}_q)$ which can be pulled back to an abelian covering $Y \to X$ with group $J(\mathbb{F}_q)$ along the embedding $X \to J$.

* If $\chi$ is an Artin character on $X$, and $h: \tilde{X} \to X$ is a non constant morphism of curves, there is a natural Artin character $\tilde{\chi} = h^*\chi$ on $\tilde{X}$ obtained by pulling back the abelian covering of $X$ along $h$. On divisors, $\tilde{\chi}$ can be defined as $\tilde{\chi}(\mathbf{D}) = \chi(h_*\mathbf{D})$. Clearly, if $\chi$ is unramified, then $\tilde{\chi}$ is too, and more generally, $f(\tilde{\chi}) = h^*f(\chi)$.

* Assume that $q$ is odd. The nontrivial quadratic character (i.e. the “generalized Legendre symbol”) $\chi_q(\cdot)$ on $\mathbb{P}^1(\mathbb{F}_q)$, which sends the point of abscissa $x$ to $1, -1$, or $0$ according as whether $x$ is a quadratic residue, a quadratic nonresidue or $0, \infty$, extends to the nontrivial Artin character $\chi_2$ defined by the ramified quadratic covering $\mathbb{P}^1 \to \mathbb{P}^1: x \mapsto x^2$. One has $f(\chi_2) = (0) + (\infty)$.

* More generally, if $X$ is a curve over $\mathbb{F}_q$ and $\varphi$ a non constant, rational function on $X$, the Legendre symbol of $\varphi$ extends to a Artin character on $X$, namely $\varphi^*\chi_2$. Its conductor is the sum of the divisor of zeros of $\varphi$ and its divisor of poles. In particular, $\deg f(\varphi^*\chi_2) = 2 \deg \varphi$.

When $\chi$ is nontrivial, Weil [Wei95] has proved the following estimate for sums related to $\chi$, as a consequence of the Riemann hypothesis for curves (see, for example, [KS00, §2] or [Ros02, Chapter 9]). For any Artin character $\chi$ of $X$, let:

$$S_X(\chi) = \sum_{\mathbf{P} \in X(\mathbb{F}_q)} \chi(\mathbf{P}).$$

**Lemma 6.1.** If $\chi$ is nontrivial and $X$ is of genus $g$, one has

$$|S_X(\chi)| \le (2g - 2 + \deg f(\chi)) \sqrt{q}.$$

We can now easily deduce the following result, which forms the basis of the proofs of well-distributedness in §6.4.

**Theorem 6.3.** Let $h: \tilde{X} \to X$ be a non constant morphism of curves, and $\chi$ be any nontrivial character of $J(\mathbb{F}_q)$, where $J$ is the Jacobian of $X$. Assume that $h$ does not
factor through a nontrivial unramified morphism $Z \to X$. Then:

$$ \left| \sum_{\mathbf{P} \in \tilde{X}(\mathbb{F}_q)} \chi(h(\mathbf{P})) \right| \le (2\tilde{g} - 2)\sqrt{q} \qquad (6.7) $$

where $\tilde{g}$ is the genus of $\tilde{X}$. Furthermore, if $q$ is odd and $\varphi$ is a non constant rational function on $\tilde{X}$:

$$ \left| \sum_{\mathbf{P} \in \tilde{X}(\mathbb{F}_q)} \chi(h(\mathbf{P}))\chi_q(\varphi(\mathbf{P})) \right| \le (2\tilde{g} - 2 + 2 \deg \varphi)\sqrt{q}. \qquad (6.8) $$

*Proof.* Denote also by $\chi$ the Artin character of $X$ extending the given character of $J(\mathbb{F}_q)$. The left-hand side of (6.7) is then just $|S_{\tilde{X}}(h^*\chi)|$, and we know that $h^*\chi$ is an unramified Artin character of $\tilde{X}$, so the inequality follows from Lemma 6.1 provided that we can prove that $h^*\chi$ is nontrivial. But if it is a trivial character, $h_*$ maps all divisors of $\tilde{X}$ to the kernel of $\chi$: this means that $h$ factors through the unramified covering $Z \to X$ defined by the kernel of $\chi$, which is impossible by hypothesis. Hence inequality (6.7).

Similarly, the left-hand side of (6.8) is $|S_{\tilde{X}}(\tilde{\chi})|$ for $\tilde{\chi}$ the Artin character of $\tilde{X}$ defined as the product of $h^*\chi$ and $\varphi^*\chi_2$. This character cannot be trivial: otherwise, $\varphi^*\chi_2$ would be the inverse of $h^*\chi$, and hence unramified, which it is not. Thus, Lemma 6.1 gives $|S_{\tilde{X}}(\tilde{\chi})| \le (2\tilde{g} - 2 + \deg f(\tilde{\chi}))\sqrt{q}$. Since $h^*\chi$ is unramified, we have $\deg f(\tilde{\chi}) = \deg f(\varphi^*\chi_2) = 2\deg \varphi$, which concludes the proof. $\square$

## 6.4 Examples of Well-Distributed Encodings

### 6.4.1 Icart's encoding

Recall from §3.5.2 that Icart [Ica09] defined a family of deterministic functions to elliptic curves $E: y^2 = x^3 + ax + b$ over finite fields $\mathbb{F}_q$ such that $q \equiv 2 \pmod 3$. His map $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ is given by $u \mapsto (x, y)$ with

$$ x = \left( v^2 - b - \frac{u^2}{27} \right)^{1/3} + \frac{u^2}{3} \quad \text{and} \quad y = ux + v \qquad (6.9) $$

where $v = (3a - u^4)/(6u)$. The image of 0 is chosen as the neutral element of the elliptic curve.

Icart showed that a point $(x, y)$ is the image of $u$ if and only if

$$ u^4 - 6xu^2 + 6yu - 3a = 0. \qquad (6.10) $$

This makes it possible to give a simple geometric interpretation of Icart's function, as has been done in [FSV10, FT10a, BCI+10a].
Indeed, let $K = \mathbb{F}_q(E)$ be the function field of $E$, and introduce the smooth projective curve $C$ whose function field is the quartic extension $L = K[u]/(P)$ of $K$, where $P = u^4 - 6xu^2 + 6yu - 3a$. The inclusions $\mathbb{F}_q(u) \subset L$ and $K \subset L$ give rise to rational maps $g: C \to \mathbb{P}^1$ and $h: C \to E$ which are in fact morphisms, since these curves are smooth and complete.

Then, Icart's function can be described as $f(u) = h(g^{-1}(u))$. This is well-defined when $q \equiv 2 \pmod 3$ because in that case, $g$ induces a bijection from the set of points in $C(\mathbb{F}_q)$ which are not poles of $u$ to $\mathbb{A}^1(\mathbb{F}_q) = \mathbb{F}_q$.

This geometric point of view makes it possible to express the character sum $S_f(\chi)$, for any character $\chi$ of $E(\mathbb{F}_q)$, in terms of the Artin character sum $S_C(h^*\chi)$ (they are the same up to a few “bad points”), and then to use Theorem 6.3 to show that Icart’s function is well-distributed.

**Theorem 6.4.** Let $f$ be Icart's function (6.9). For any nontrivial character $\chi$ of $E(\mathbb{F}_q)$, the character sum $S_f(\chi)$ given by (6.2) satisfies:

$$|S_f(\chi)| \le 12\sqrt{q} + 3.$$

*Proof.* The map $h: C \to E$ defined above is a non constant morphism of curves. Moreover, we know from the analysis of Chapters 4-5 (see also [FSV10]) that if $a \ne 0$, $C$ is of genus 7, and that the Galois closure of the quartic extension $\mathbb{F}_q(C)/\mathbb{F}_q(E)$ has Galois group $S_4$ (for $a = 0$, the discussion in analogous). It follows that $\mathbb{F}_q(C)/\mathbb{F}_q(E)$ has no nontrivial intermediate extension, and it is clearly ramified (because an unramified covering of an elliptic curve must be of genus 1). Thus, $h$ fulfills the hypotheses of Theorem 6.3, and we get

$$\left| \sum_{\mathbf{P} \in C(\mathbb{F}_q)} \chi(h(\mathbf{P})) \right| \le (2 \cdot 7 - 2)\sqrt{q} = 12\sqrt{q}.$$

Now recall that $g$ induces a bijection from $C(\mathbb{F}_q) \setminus \{\text{poles of } u\}$ to $\mathbb{F}_q$. Thus:

$$\sum_{\mathbf{P} \in C(\mathbb{F}_q)} \chi(h(\mathbf{P})) = S_f(\chi) + \sum_{\substack{\mathbf{P} \in C(\mathbb{F}_q) \\ u(\mathbf{P}) = \infty}} \chi(h(\mathbf{P})).$$

It is shown in the proof of Lemma 5.2 in the previous chapter that $u$ has exactly 3 poles on $C$, hence the result. $\square$

In other words, Theorem 6.4 asserts that $f$ is a $(12+3q^{-1/2})$-well-distributed encoding.

In particular, as a well-distributed encoding to a curve of genus 1, Icart's function $f$ satisfies that $f^{\otimes s}$ is regular for $s \ge 2$. Since $f^{\otimes 2}$ is clearly computable and samplable, it is admissible. Thus, we get a new, simpler and conceptually different proof of the main result of the previous chapter, that

$$\mathfrak{S}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m))$$

is indifferentiable from a random oracle when $\mathfrak{h}_1, \mathfrak{h}_2$ are seen as random oracles to $\mathbb{F}_q$.
We also get more general results, since we have information about $f^{\otimes s}$ for $s > 2$, and the bounds we obtain are also sharper than those in the previous chapters. If we denote the collision probability for $f$ by $\rho_f$, we have:

$$ \rho_f = q^{-2} \sum_{\mathbf{P} \in E(\mathbb{F}_q)} \#f^{-1}(\mathbf{P})^2 \le 4q^{-2} \sum_{\mathbf{P} \in E(\mathbb{F}_q)} \#f^{-1}(\mathbf{P}) = 4q^{-1} $$

because points on $E$ have at most 4 preimages. Theorem 6.1 then gives:

**Corollary 6.3.** For all $\mathbf{P} \in E(\mathbb{F}_q)$ and all $s$, we have

$$ \left| \frac{N_s(\mathbf{P})}{q^s} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \frac{(12 + 3q^{-1/2})^{s-2} (4\#E(\mathbb{F}_q)q^{-1} - 1)}{q^{s/2-1}\#E(\mathbb{F}_q)}. $$

Similarly, Theorem 6.2 gives:

**Corollary 6.4.** For all $s$, the statistical distance between the distribution given by $f^{\otimes s}$ and the uniform distribution on $E(\mathbb{F}_q)$ is bounded as

$$ \sum_{\mathbf{P} \in E(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{P})}{q^s} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \frac{(12 + 3q^{-1/2})^{s-1} \sqrt{4\#E(\mathbb{F}_q)q^{-1} - 1}}{q^{(s-1)/2}}. $$

Since $\#E(\mathbb{F}_q) = q + O(q^{1/2})$, the bounds of Corollaries 6.3 and 6.4 simplify as

$$ \left| \frac{N_s(\mathbf{P})}{q^s} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \frac{3 \cdot 12^{s-2} + O(q^{-1/2})}{q^{s/2}} \qquad (6.11) $$

and

$$ \sum_{\mathbf{P} \in E(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{P})}{q^s} - \frac{1}{\#E(\mathbb{F}_q)} \right| \le \frac{\sqrt{3} \cdot 12^{s-1} + O(q^{-1/2})}{q^{(s-1)/2}}. \qquad (6.12) $$

For $s = 2$, this gives a bound of the statistical distance of the form $12\sqrt{3}q^{-1/2}+O(q^{-1})$, which is a significant improvement over the estimate from §5.3. We can refine this further by computing the collision probability precisely.

**Remark 6.1.** As we saw in Chapter 4, the Chebotarev density theorem gives the prevalence of points with any given number of preimages: the number of permutations in $\text{Gal}(\mathbb{F}_q(C)/\mathbb{F}_q(E)) = S_4$ with exactly 1 (respectively 2, 4) fixed point(s) is 8 (respectively 6, 1), so the density of points with 1 (respectively 2, 4) preimages is 8/24 (respectively 6/24, 1/24). Using an effective version of the Chebotarev density theorem, this gives:

$$ q^2 \rho_f = 1^2 \cdot \left( \frac{8q}{24} + O(\sqrt{q}) \right) + 2^2 \cdot \left( \frac{6q}{24} + O(\sqrt{q}) \right) + 4^2 \cdot \left( \frac{q}{24} + O(\sqrt{q}) \right). $$

Thus $\rho_f = 2q^{-1} + O(q^{-3/2})$, which allows us to drop the factors 3 and $\sqrt{3}$ from (6.11) and (6.12), respectively.
## 6.4.2 The Kammerer-Lercier-Renault encodings

As discussed in §3.5.3, Kammerer, Lercier and Renault [KLR10] have recently introduced a series of new encodings based on the same principles as Icart's function, namely solving curve equations in radicals. One such example is an encoding $f$ to hyperelliptic curves of genus 2 over fields $\mathbb{F}_q$ such that $q \equiv 2 \pmod 3$ of the form:

$$H: x^3 + (y + c) \left( 3x + 2a + \frac{2b}{y} \right) = 0.$$

The precise description of the encoding is rather complicated, and we refer the reader to [KLR10, §3.2.2] for details, but the geometric picture is the same as for Icart's function. The parameter $u$ defining the encoding satisfies a relation of the form:

$$4u^2(u^2 - 3y - a^2 - c)^3 + u^8 + \alpha u^4 + \beta u^2 + \gamma = 0 \quad (6.13)$$

where $\alpha, \beta, \gamma$ are constants in $\mathbb{F}_q$ defined in terms of $a, b, c$, which we assume are nonzero.

In particular, if $\mathbb{K} = \mathbb{F}_q(x, y)$ is the function field of $H$, one can consider the extension $\mathbb{L} = \mathbb{K}[u]/(P)$ where $P$ is the polynomial of degree 8 given by equation 6.13. This defines a covering $h: C \to H$ of degree 8 by a certain smooth projective curve $C$, and the rational function $u$ on $C$ provides a morphism $g: C \to \mathbb{P}^1$ of degree 9 which induces a bijection on $\mathbb{F}_q$-rational points over $\mathbb{A}^1(\mathbb{F}_q) \setminus S$ where $S$ is a finite set of points shown in [KLR10] to be of size at most 75. The encoding $f: \mathbb{F}_q \to H(\mathbb{F}_q)$ is then defined as $u \mapsto h(g^{-1}(u))$ for $u \in \mathbb{F}_q \setminus S$, and is extended in some way to all of $\mathbb{F}_q$.

Our machinery applies again to show that $f$ is a well-distributed encoding. Denote by $J$ the Jacobian of $H$, and fix an embedding $H \to J$.

**Theorem 6.5.** Let $f$ be the encoding function described above. For any nontrivial character $\chi$ of $J(\mathbb{F}_q)$, the character sum $S_f(\chi)$ given by (6.2) satisfies:

$$|S_f(\chi)| \le 96\sqrt{q} + 759.$$

*Proof.* The map $h: C \to H$ defined above is a non constant morphism of curves. Let us compute the genus of $C$.

Note first that $P(u)$ can be written as $Q(t)$ where $t = u^2$, which defines a factorization $C \to D \to H$, with $[D: H] = 4$. The discriminant of $Q$ is a polynomial of degree 12 in $y$, and each of its 12 roots corresponds to 3 ramified points on $H$, since each value of $y$ corresponds to 3 values of $x$. Moreover, when regarded as a polynomial over $\mathbb{F}_q((1/y))$, the quartic $Q$ has a Newton polygon with integer slopes $(-3$ with length 1 and 1 with length 3). Thus, $D$ is unramified over points with $y = \infty$. All in all, the Riemann-Hurwitz formula gives $2g_D - 2 = 4 \cdot (2g_H - 2) + 3 \cdot 12 = 44$: $D$ is of genus 23.

Then, the quadratic covering $C \to D$ is ramified exactly at points such that $t = 0$ or $t = \infty$. At finite distance, this gives $\gamma = 0$, which is excluded, so all the ramification is at infinity. By the previous Newton polygon argument, over each point of $H$ with $y = \infty$ lie 4 points of $D$, one with $t = 0$ and three with $t = \infty$. And there are 2 such points of $H$, by another Newton polygon argument. Hence $2g_C - 2 = 2 \cdot (2g_D - 2) + 2 \cdot 4 = 96$, and $C$ is of genus 49.
Let us now show that $h: C \to H$ does not factor nontrivially through an unramified covering. To see this, consider $D_0 \to \mathbb{P}^1$, the ramified covering of degree 4 defined by $Q$ (which pulls back to $D \to H$ along $x: H \to \mathbb{P}^1$). We see like before that all points of $D_0$ ramified over $\mathbb{P}^1$ have ramification index 2. Thus, the monodromy group of this covering is a transitive subgroup of $S_4$ generated by transpositions, hence all of $S_4$.

By inspection of the ramification of $x: H \to \mathbb{P}^1$, it follows that $D \to H$ also has $S_4$ as its monodromy group. In particular, it has no quadratic subcovering. Now suppose $h: C \to H$ factors through some abelian unramified extension $Z \to H$, which we can assume is quadratic. Then the function fields $\mathbb{F}_q(Z)$ and $\mathbb{F}_q(D)$ are everywhere linearly disjoint over $\mathbb{F}_q(H)$ (i.e. all of their embeddings in some algebraic closure of $\mathbb{F}_q(H)$ are linearly disjoint). Thus $\mathbb{F}_q(C) = \mathbb{F}_q(D) \otimes_{\mathbb{F}_q(H)} \mathbb{F}_q(D)$, and in particular, $C \to D$ is the pullback of $Z \to H$ along $D \to H$. This implies that $C \to D$ is unramified, which we know is not the case.

Thus, $h$ does not factor nontrivially through an abelian unramified covering, and hence fulfills the hypotheses of Theorem 6.3. We get

$$ \left| \sum_{\mathbf{P} \in C(\mathbb{F}_q)} \chi(h(\mathbf{P})) \right| \le (2g_C - 2)\sqrt{q} = 96\sqrt{q}. $$

Now recall that $g$ induces a bijection from $C(\mathbb{F}_q) \setminus g^{-1}(S \cup \{\infty\})$ to $\mathbb{F}_q \setminus S$. Thus:

$$ \begin{aligned} \sum_{\mathbf{P} \in C(\mathbb{F}_q)} \chi(h(\mathbf{P})) &= \sum_{u \in \mathbb{F}_q \setminus S} \chi(f(u)) + \sum_{\mathbf{P} \in g^{-1}(S \cup \{\infty\})} \chi(h(\mathbf{P})) \\ &= S_f(\chi) - \sum_{u \in S} \chi(f(u)) + \sum_{\mathbf{P} \in g^{-1}(S \cup \{\infty\})} \chi(h(\mathbf{P})). \end{aligned} $$

Since $\#S \le 75$ and $g$ is of degree 9, we get

$$ |S_f(\chi)| \le 96\sqrt{q} + 9 \cdot 76 + 75 = 96\sqrt{q} + 759 $$

as required.

□

In other words, $f$ is a $(96 + 759q^{-1/2})$-well-distributed encoding to $H$. In particular, as a well-distributed encoding to a curve of genus 2, it satisfies that $f^{\otimes s}$ is regular for any $s \ge 3$. Thus, $f^{\otimes 3}$ is regular and clearly also computable and samplable, so the following construction:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) + f(\mathfrak{h}_3(m)) \in J(\mathbb{F}_q) $$

is indifferentiable from a random oracle when $\mathfrak{h}_1, \mathfrak{h}_2, \mathfrak{h}_3$ are seen as random oracles to $\mathbb{F}_q$. This is the first example of an efficient, well-behaved hash function to the Jacobians of a large family of curves of genus 2.

We now estimate (quite coarsely) the collision probability for $f$: since $h$ is of degree 8, any given point on $H$ has at most 8 preimages by $f$. Thus,

$$ \rho_f = q^{-2} \sum_{\mathbf{P} \in H(\mathbb{F}_q)} \#f^{-1}(\mathbf{P})^2 \le 8q^{-2} \sum_{\mathbf{P} \in H(\mathbb{F}_q)} \#f^{-1}(\mathbf{P}) = 8q^{-1} $$

and so $q\rho_f \le 8$ as required. Thus, Theorem 6.1 gives the following estimate:
**Corollary 6.5.** For all $\mathbf{D} \in J(\mathbb{F}_q)$ and all $s$, we have

$$ \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{8 (96 + 759q^{-1/2})^{s-2}}{q^{s/2}}. $$

Furthermore, from Theorem 6.2 we derive:

**Corollary 6.6.** For all $s$, the statistical distance between the distribution given by $f^{\otimes s}$ and the uniform distribution on $J(\mathbb{F}_q)$ is bounded as

$$ \sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{\sqrt{8} \cdot (96 + 759q^{-1/2})^{s-1} \sqrt{\#J(\mathbb{F}_q)}}{q^{s/2}}. $$

Using that $\#J(\mathbb{F}_q) = q^2 + O(q^{3/2})$ one can also obtain simplified versions of Corollaries 6.5 and 6.6 similar to the bounds (6.11) and (6.12).

Of course, we have considered only one of the encodings from [KLR10], but the same technique applies to all of them. In some cases, it is even much easier to apply. For example, in the case of the encoding to hyperelliptic curves $H_a: y^2 = x^{2d} + x^d + a$, the covering curve is $H_a$ itself (the parameter $u$ is in fact just $y - x^d \in \mathbb{F}_q(x, y)$), so the hypotheses of Theorem 6.3 are trivially verified.

### 6.4.3 The simplified SWU encoding

Recall from §3.5.4 the description of the simplified Shallue-van de Woestijne-Ulas encoding over fields $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$, as introduced in [BCI+10a] with the sign tweak from [FT10a]. The function is based on the following observation. Let $g(x) = x^3+ax+b \in \mathbb{F}_q[x]$ with $ab \ne 0$, and define:

$$ X_2(u) = -\frac{b}{a} \left( 1 + \frac{1}{u^4 - u^2} \right) \qquad X_3(u) = -u^2 X_2(u) $$

and

$$ Z(u) = u^3 g(X_2(u)). $$

Then we have $Z(u)^2 = -g(X_2(u)) \cdot g(X_3(u))$.

Let $S = \{0, 1, -1\} \cup \{\text{roots of } g(X_j(u)) = 0, j = 2, 3\}$. For any $u \notin S$, $X_2(u)$ and $X_3(u)$ are well-defined and non zero. Since $-1$ is a quadratic nonresidue in $\mathbb{F}_q$, this implies that for any $u \in \mathbb{F}_q \setminus S$, exactly one of $g(X_2(u))$ or $g(X_3(u))$ is a square. Therefore, we can define an encoding function $f$ to the elliptic curve $E: y^2 = x^3 + ax + b$ by

$$ f(u) = \left( X_j(u) ; (-1)^j \sqrt{g(X_j(u))} \right), $$

where $j = 2$ or $3$ is the index such that $g(X_3(u))$ is a square, and $\sqrt{}$ is the standard square root in $\mathbb{F}_q$, given by exponentiation by $(q+1)/4$ (thus, the $y$-coordinate is a quadratic residue if $j = 2$ and a quadratic nonresidue if $j = 3$).
As discussed in §4.5, this encoding function admits the following geometric interpretation. It is easy to see that for all $u \in \mathbb{F}_q \setminus \{-1, 0, 1\}$,

$$ 
\begin{aligned}
x &= X_2(u) \iff u^4 - u^2 + \frac{1}{\omega} = 0 \\
x &= X_3(u) \iff u^4 - \omega u^2 + \omega = 0
\end{aligned}
$$

where $\omega = \frac{a}{b}x + 1$. Thus, we can introduce coverings $h_j: C_j \to E, j = 2, 3$, by the smooth projective curves whose function fields are the extensions of $\mathbb{F}_q(x, y)$ defined respectively by $u^4 - u^2 + 1/\omega = 0$ and $u^4 - \omega u^2 + \omega = 0$. The parameter $u$ is a rational function on each of the $C_j$ giving rise to morphisms $g_j: C_j \to \mathbb{P}^1$, such that any point in $\mathbb{A}^1(\mathbb{F}_q) \setminus S$ has exactly two preimages in one of the two curves $C_j(\mathbb{F}_q)$, $j = 2, 3$, and none in the other.

If $u \in \mathbb{F}_q \setminus S$ has its preimages in $C_j(\mathbb{F}_q)$, those preimages are conjugate under $y \mapsto -y$, so that exactly one of them satisfies $\chi_q(y) = (-1)^j$. Let $\mathbf{P} \in C_j(\mathbb{F}_q)$ be that preimage. Then, $f(u) = h_j(\mathbf{P})$. This geometric interpretation is enough to apply Theorem 6.3 and establish that $f$ is well-distributed.

**Theorem 6.6.** Let $f$ be the encoding described above. For any nontrivial character $\chi$ of $E(\mathbb{F}_q)$, the character sum $S_f(\chi)$ given by (6.2) satisfies:

$$ |S_f(\chi)| \le 52\sqrt{q} + 151. $$

*Proof.* In light of the previous discussion, the character sum $S_f(\chi)$, when restricted to parameters $u$ in $\mathbb{F}_q \setminus S$, can be written as:

$$ \sum_{u \notin S} \chi(f(u)) = \sum_{\mathbf{P} \in C_2(\mathbb{F}_q) \setminus S_2} \chi(h_2(\mathbf{P})) + \sum_{\mathbf{P} \in C_3(\mathbb{F}_q) \setminus S_3} \chi(h_3(\mathbf{P})) \quad (6.14) $$

where $S_j = g_j^{-1}(S \cup \{\infty\})$. To estimate such sums, observe that:

$$ 
\begin{aligned}
& \sum_{\mathbf{P} \in C_j(\mathbb{F}_q)} \chi(h_j(\mathbf{P})) \cdot \left( \frac{1 + (-1)^j \chi_q(y)}{2} \right) \\
& = \sum_{\substack{\mathbf{P} \in C_j(\mathbb{F}_q) \\ \chi_q(y) = (-1)^j}} \chi(h_j(\mathbf{P})) + \frac{1}{2} \sum_{\substack{\mathbf{P} \in C_j(\mathbb{F}_q) \\ \chi_q(y) = 0}} \chi(h_j(\mathbf{P})).
\end{aligned}
\quad (6.15) $$

The first sum on the right-hand side of (6.15) is almost what we want (up to a bounded number of “bad terms”) and the second sum on the right-hand side contains at most $3 \cdot 4 = 12$ terms.

Furthermore, the left-hand side of (6.15) is directly estimated using Theorem 6.3. Indeed, by the Eisenstein criterion, $h_2$ and $h_3$ are totally ramified over points in $H$ such that $\omega = 0$ (that is, $x = -b/a$), so they cannot factor through any unramified covering of
E. Hence, Theorem 6.3 applies and gives:

$$ \left| \sum_{\mathbf{P} \in C_j(\mathbb{F}_q)} \chi(h_j(\mathbf{P})) \cdot \left( \frac{1 + (-1)^j \chi_q(y)}{2} \right) \right| \le (2g_{C_j} - 2 + \deg y) \sqrt{q} $$

where $g_{C_j}$ is the genus of $C_j$, and $\deg y$ is the degree of $y$ as a rational function on $C_j$. Clearly, $\deg y = [\mathbb{F}_q(x, y, u) : \mathbb{F}_q(x, y)] \cdot [\mathbb{F}_q(x, y) : \mathbb{F}_q(y)] = 4 \cdot 3 = 12$. Furthermore, to compute $g_{C_j}$, note that in addition to the totally ramified points mentioned previously, $C_j \to E$ has ramification type (2, 2) at points with $\omega = 4$ and at infinity, and is unramified elsewhere. Thus, the Riemann-Hurwitz formula gives $2g_{C_j} - 2 = 0 + 2 \cdot 3 + 2 \cdot (1 + 1) + 2 \cdot (1 + 1) = 14$: the curves $C_j$ are of genus 8. Thus:

$$ \left| \sum_{\mathbf{P} \in C_j(\mathbb{F}_q)} \chi(h_j(\mathbf{P})) \cdot \left( \frac{1 + (-1)^j \chi_q(y)}{2} \right) \right| \le 26\sqrt{q}. $$

Plugging this estimate back into (6.14) using (6.15), we get:

$$ \left| \sum_{u \notin S} \chi(f(u)) \right| \le (26\sqrt{q} + \#S_2 + 6) + (26\sqrt{q} + \#S_3 + 6) \\ = 52\sqrt{q} + 12 + \#S_2 + \#S_3. $$

Thus $|S_f(\chi)| \le 52\sqrt{q} + 12 + \#S_2 + \#S_3 + \#S$. Now $\#S \le 3 + 2 \cdot 12 = 27$, and since $g_j$ is a map of degree 2, $\#S_j \le 2(\#S + 1) \le 56$, which concludes the proof. $\square$

Thus, we see from Theorem 6.6 that the simplified Shallue-Woestijne-Ulas encoding is $(52 + 151q^{-1/2})$-well-distributed. As in §6.4.1 and §6.4.2, using Theorem 6.1 and Theorem 6.2, we can deduce precise bounds on the maximum deviation of functions of the form $f^{\otimes s}$ and on the statistical distance of the distribution they define on $E(\mathbb{F}_q)$ and the uniform distribution.

In particular, we get that $f^{\otimes s}$ is regular for $s \ge 2$. Since $f^{\otimes 2}$ is clearly computable and samplable, it is admissible, and we obtain that

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) $$

is indifferentiable from a random oracle when $\mathfrak{h}_1, \mathfrak{h}_2$ are seen as random oracles to $\mathbb{F}_q$.

Once again, the method generalizes to other SWU-like encodings, such as the Ulas encoding to hyperelliptic curves of the form $y^2 = x^5 + ax + b$.
<figure><img src="image_12.png" /></figure>
# Hashing and Encoding to Odd Hyperelliptic Curves

## 7.1 Introduction

In this chapter, which can serve as an illustration for the results of Chapters 3, 5 and 6, we propose a very simple and efficient encoding function from $\mathbb{F}_q$ to points of a hyperelliptic curve over $\mathbb{F}_q$ of the form $H: y^2 = g(x)$ where $g$ is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves.

Our new encoding is nearly a bijection to the set of $\mathbb{F}_q$-rational points on $H$. This makes it easy to construct well-behaved hash functions to the Jacobian $J$ of $H$, as well as injective maps to $J(\mathbb{F}_q)$ which can be used to encode scalars for such applications as El Gamal encryption.

The new encoding is already interesting in the genus 1 case, where it provides a well-behaved encoding to Joux's supersingular elliptic curves.

This work was presented at Pairing 2010 [FT10a].

### 7.1.1 Hyperelliptic curve encodings.

While there are now rather general and efficient constructions for elliptic curves, encodings to hyperelliptic curves are scarce. The first such encoding was proposed by Ulas in [Ula07], for curves of the form $y^2 = x^n + ax + b$ or $y^2 = x^n + ax^2 + bx$. Kammerer, Lercier and Renault, in their recent paper [KLR10], have presented several additional families of hyperelliptic curves for which an Icart-like encoding can be constructed, but the target curves are still of a special form and may not be convenient to use for cryptographic applications. Efficiency is also a problem for both of these constructions.

Moreover, all of these algorithms construct points on the curve itself, whereas the relevant object in cryptography is the group attached to it, namely its Jacobian variety. We have seen in Chapter 6 how to build a well-behaved hash function to the Jacobian based on an encoding to the curve, but the relatively complex geometric description
of a function like the Kammerer-Lercier-Renault genus 2 encoding led to rather large constants in the results of §6.4.2.

### 7.1.2 Our contribution

This chapter presents a new encoding for hyperelliptic curves of the form $H : y^2 = g(x)$ where $g$ is an odd polynomial over $\mathbb{F}_q$, with $q = 3 \pmod 4$. From this encoding to the curve $H$, we also deduce efficient injective encodings and well-behaved hash functions to its Jacobian. The new encoding has the following desirable properties:

* it can be very efficiently computed using one exponentiation and no division, in constant time and without branching;

* the encoding is an efficiently invertible bijection: thus, it is possible to encode messages as points on the curve and recover them. This has numerous applications, e.g. to encryption;

* in genus 1, it provides an encoding to supersingular elliptic curves, similar to Boneh and Franklin's construction [BF01], but for different base fields;

* in higher genus, many cryptographically interesting curves are of the form $H$, including the curves considered in [FKT03, HKT05, Sat09];

* many constructions of pairing-friendly hyperelliptic curves yield curves of the form $H$ [KT08, FS11];

* since the encoding has a simple geometric description, it is easy to obtain well-behaved hash functions from it, and the corresponding regularity bounds are optimally tight.

## 7.2 Odd Hyperelliptic Curves

Let $g$ be an odd monic polynomial over a finite field $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$), which has simple roots in $\bar{\mathbb{F}}_q$. We denote its degree by $2k + 1$, and consider the hyperelliptic curve over $\mathbb{F}_q$ defined by:

$$H: y^2 = f(x) = x^{2k+1} + a_1 x^{2k-1} + \dots + a_k x$$

Let us call such curves *odd hyperelliptic curves*. Many hyperelliptic curves relevant to cryptography, and particularly pairing-based cryptography, are of this form. For example:

* the supersingular elliptic curves of Joux [Jou02]: $y^2 = x^3 + ax$;

* the genus 2 curves studied by Furukawa et al. [FKT03] and their extension to higher genus by Haneda et al. [HKT05]: $y^2 = x^{2k+1} + ax$ (for which one can compute the zeta function);

* in particular, the Type II pairing-friendly curves of genus 2 constructed by Kawazoe and Takahashi [KT08];
* the genus 2 hyperelliptic curves for which Satoh [Sat09] gave an efficient class group counting algorithm: $y^2 = x^5 + ax^3 + bx$;

* in particular, some of the pairing-friendly genus 2 curves constructed by Freeman and Satoh [FS11] (although the case $q \equiv 1 \pmod 4$ is more common).

Additionally, odd hyperelliptic curves and their Jacobians admit an automorphism of order 4 over $\mathbb{F}_{q^2}$ (namely $(x, y) \mapsto (-x, \sqrt{-1} \cdot y)$) which can be used to map points over $\mathbb{F}_q$ to linearly independent points over $\mathbb{F}_{q^2}$, another useful property for pairings.

*Remark 7.1.* A hyperelliptic curve over $\mathbb{F}_q$ is birational to an odd hyperelliptic curve when the set of points in $\mathbb{P}^1$ over which it is ramified is invariant under an automorphism of $\mathbb{P}^1$ of order 2 fixing two of them, both $\mathbb{F}_q$-rational. For example, hyperelliptic curves of the form:

$$H': y^2 = x^6 + ax^5 + bx^4 - bx^2 - ax - 1$$

are birational to odd hyperelliptic curves, since they are ramified over a set of points invariant under $x \mapsto 1/x$ and containing $\pm 1$. One possible change of variables is $x \mapsto (x - 1)/(x + 1)$.

This remark shows that the coarse moduli space of odd hyperelliptic curves of genus $k$ over $\overline{\mathbb{F}}_q$ is a subvariety of dimension $k - 1$ of the dimension $2k - 1$ moduli space of genus $k$ hyperelliptic curves.

# 7.3 Our New Encoding

## 7.3.1 Definition

Let $H: y^2 = g(x)$ be an odd hyperelliptic curve over $\mathbb{F}_q$, $q \equiv 3 \pmod 4$. Denote by $\sqrt{q}$. The usual square root function on the set of quadratic residues in $\mathbb{F}_q$ (exponentiation by $(q+1)/4$), and by $\chi_q(\cdot)$ the nontrivial quadratic character of $\mathbb{F}_q$.

Over $\mathbb{F}_q$, $-1$ is a quadratic nonresidue, and for any $t \in \mathbb{F}_q$, we have $g(-t) = -g(t)$, so unless $g(t) = 0$, exactly one of $g(t)$ or $g(-t)$ is a square. In other words, exactly one of $t$ or $-t$ is the abscissa of an $\mathbb{F}_q$-rational point on $H$.

This observation allows us to define a point encoding function $f$ to $H(\mathbb{F}_q)$ as follows:

$$f: \mathbb{F}_q \to H(\mathbb{F}_q) \\ t \mapsto \left( \varepsilon(t) \cdot t ; \varepsilon(t) \sqrt{\varepsilon(t) \cdot g(t)} \right) \qquad (7.1)$$

where $\varepsilon(t) = \chi_q(g(t))$. We claim that this function is well-defined and “almost” a bijection.

More precisely, recall that a *Weierstrass point* of $H$ is a point where the rational function $y$ is ramified: these are the points $(x, 0)$ for $x$ a root of $g$ together with the point at infinity $\infty$. Then, let $W \subset H(\mathbb{F}_q)$ be the set of $\mathbb{F}_q$-rational Weierstrass points on $H$, and $T \subset \mathbb{F}_q$ the set of roots of $f$.
**Theorem 7.1.** The function $f$ given by (7.1) is well-defined, maps all points in $T$ to $(0,0) \in W$, and induces a bijection $\mathbb{F}_q \setminus T \to H(\mathbb{F}_q) \setminus W$.

*Proof.* For $t \in T$, we have $\varepsilon(t) = 0$, hence $f(t) = (0,0) \in W$. Now let $t \in \mathbb{F}_q \setminus T$, and $x = \varepsilon(t) \cdot t$. Since $g$ is odd and $\varepsilon(t) = \pm 1$, $g(x) = \varepsilon(t) \cdot g(t)$. In particular, recalling that $\chi_q(-1) = -1$, we can write:

$$ \chi_q(g(x)) = \chi_q(\varepsilon(t) \cdot g(t)) = \varepsilon(t) \cdot \chi_q(g(t)) = \varepsilon(t)^2 = 1 $$

Thus, the second component $y = \varepsilon(t)\sqrt{\varepsilon(t) \cdot g(t)}$ of $f(t)$ is well-defined, and we have $y^2 = \varepsilon(t) \cdot g(t) = g(x)$, so $f(t)$ is an affine point on $H(\mathbb{F}_q)$ as required. The condition $t \notin T$ further implies that $g(t) \neq 0$, so $y \neq 0$. Therefore, $f(t) \in \mathbb{F}_q \setminus W$.

Let us show that the restriction of $f$ to $\mathbb{F}_q \setminus T$ is injective. Indeed, suppose $f(t) = f(u)$ with $t, u \notin T$. Equating $x$-coordinates, we get $\varepsilon(t) \cdot t = \varepsilon(u) \cdot u$, hence $u = \pm t$. If $u = -t$, then comparing the $y$-coordinates, we obtain

$$ \begin{aligned} \varepsilon(t)\sqrt{\varepsilon(t) \cdot g(t)} &= \varepsilon(u)\sqrt{\varepsilon(u) \cdot g(u)} \\ &= \varepsilon(-t)\sqrt{\varepsilon(-t) \cdot g(-t)} = -\varepsilon(t)\sqrt{\varepsilon(t) \cdot g(t)} \end{aligned} $$

which is a contradiction. Therefore, $t = u$ and $f$ is injective on $\mathbb{F}_q \setminus T$.

Finally, we claim that $f(\mathbb{F}_q \setminus T) = H(\mathbb{F}_q) \setminus W$. To see this, take $(x, y) \in H(\mathbb{F}_q) \setminus W$ and let $t = \delta \cdot x$, where $\delta = \pm 1$ is defined by $y = \delta\sqrt{g(x)}$. We have

$$ \varepsilon(t) = \chi_q(g(\delta x)) = \chi_q(\delta \cdot g(x)) = \delta \cdot \chi_q(g(x)) = \delta $$

since $g(x) = y^2$ is a square. Thus:

$$ f(t) = \left( \delta^2 \cdot x ; \delta\sqrt{\delta \cdot g(\delta x)} \right) = \left( x ; \delta\sqrt{g(x)} \right) = (x; y) $$

as required.

□

**Corollary 7.1.** The cardinality of $H(\mathbb{F}_q)$ is $q + 1$.

*Proof.* From the above, we get $\#H(\mathbb{F}_q) = \#(\mathbb{F}_q \setminus T) + \#W = q - \#T + \#W$. But $W$ consists of the point at infinity on $H$, and all points of the form $(x, 0)$, $x \in T$. Thus, $\#W = \#T + 1$, and hence $\#H(\mathbb{F}_q) = q + 1$. □

**Remark 7.2.** • Since $f$ is an efficiently computable bijection between all of $\mathbb{F}_q$ and $H(\mathbb{F}_q)$ except at most $2k + 2$ points on both sides, with an efficiently computable inverse (namely $(x, y) \mapsto \chi_q(y) \cdot x$), it is a very well-behaved encoding function.

In particular, it is clear that if $t$ is uniformly distributed in $\mathbb{F}_q$, the distribution of $f(t)$ in $H(\mathbb{F}_q)$ is statistically indistinguishable from the uniform distribution. According to the results of Chapter 5, it follows that if $\mathfrak{h}$ is a hash function to $\mathbb{F}_q$ modeled as a random oracle, then $\mathfrak{h}(m) = f(\mathfrak{h}(m))$ defines a function into $H(\mathbb{F}_q)$ that is indifferentiable from a random oracle. When the genus of $H$ is at least 2, however,
one is usually interested in hashing to the Jacobian of $H$ rather than $H$ itself. This will be discussed in §7.4.

The fact that, unlike most other encodings, $f$ is almost injective, makes it suitable for other purposes than hashing, such as encoding a message to be encrypted, for example with El Gamal.

* Since $\#T = \#(W \setminus \{\infty\})$, it is in fact easy to modify the definition of $f$ to obtain a bijection $f': \mathbb{F}_q \to H(\mathbb{F}_q) \setminus \{\infty\}$ which misses only one rational point on $H$. This modified encoding $f'$ is slightly less efficient to compute, however, and using one or the other makes no difference in practice (as one is not concerned with a few exceptional points), so we shall stick to $f$ as defined by (7.1).

* When $H$ is in fact an elliptic curve $E$ (i.e. $\deg g = 3$), Corollary 7.1 says that $E$ is supersingular. These are in fact the supersingular elliptic curves $y^2 = x^3 + ax$ discussed by Joux in [Jou02]. Thus, the function $f$ provides a convenient way to encode points into supersingular elliptic curves over $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$. This is an interesting addition to the original encoding of Boneh and Franklin [BF01], which applies to supersingular curves of the form $y^2 = x^3 + b$ over fields $\mathbb{F}_q$ with $q \equiv 2 \pmod 3$. In particular, our encoding can be used in characteristic 3.

* In the general case, we see that $\#H(\mathbb{F}_{q^n}) = q^n + 1$ for any odd extension degree $n$. This gives some constraints on the zeta function of $H$, but in genus $k \ge 2$, many isogeny classes are possible for the Jacobian $J$ of $H$ nonetheless, so the proposed encoding applies to a wide range of curves. It is not always easy to determine the order of $J(\mathbb{F}_q)$: an approach is given by Satoh in [Sat09] for $g = 2$.

### 7.3.2 Efficient computation

The definition of $f$ involves a generalized Legendre symbol and one square root, which suggests that its computation might be costly, especially if it is to be done in constant time, an important property in settings where side-channel attacks are a concern. However, it is actually possible to compute $f$ with a single exponentiation, a few multiplications and no division, making it one of the most efficient deterministic encoding function proposed to date. One such implementation is described as Algorithm 7.1. Note that this implementation is also branch-free, contrary to what happens for encodings such as the one by Shallue and van de Woestijne [SvdW06]; this also prevents certain active side-channel attacks.

To see that this implementation is correct, consider $\alpha$ and $\beta$ as defined in Algorithm 7.1. For $t \in T$, we have $\alpha = 0$, hence the procedure returns $f(t) = (0, 0)$ as required. Now let $t \notin T$. We have

$$ \beta^2 = \alpha^{\frac{q-3}{2}} = \frac{1}{\alpha}\chi_q(\alpha) = \frac{\varepsilon(t)}{\alpha} $$

In particular, $\alpha\beta^2t = \varepsilon(t) \cdot t$ is indeed the abscissa of $f(t)$.
**Algorithm 7.1** Constant-time, single-exponentiation implementation of the encoding $f$. The constant $r$ is $(q-3)/4$ if $q \equiv 3 \pmod 8$, $(q-3)/4 + (q-1)/2$ otherwise.

1: **function** $f(t)$

2: $\alpha \leftarrow g(t)$

3: $\beta \leftarrow \alpha^r$

4: **return** $(\alpha\beta^2t, \alpha\beta)$

5: **end function**

Moreover, suppose $q \equiv 3 \pmod 8$. Then $(q+1)/4$ is odd and $\varepsilon(t) = \pm 1$, so we have

$$ \alpha\beta = \alpha^{\frac{q-3}{4}+1} = \varepsilon(t) \cdot \varepsilon(t) \cdot g(t)^{\frac{q+1}{4}} \\ = \varepsilon(t) \cdot (\varepsilon(t) \cdot g(t))^{\frac{q+1}{4}} = \varepsilon(t) \sqrt{\varepsilon(t) \cdot g(t)} $$

so the algorithm is correct.

Similarly, when $q \equiv 7 \pmod 8$, $(q+1)/4$ is odd and we obtain

$$ \alpha\beta = \alpha^{\frac{q-1}{2}+\frac{q-3}{4}+1} = \varepsilon(t) \cdot g(t)^{\frac{q+1}{4}} \\ = \varepsilon(t) \cdot (\varepsilon(t) \cdot g(t))^{\frac{q+1}{4}} = \varepsilon(t) \sqrt{\varepsilon(t) \cdot g(t)} $$

which concludes.

## 7.4 Mapping to the Jacobian

In the previous section, we have constructed a function $f: \mathbb{F}_q \to H(\mathbb{F}_q)$ which is efficiently computable and has a number of desirable properties. For cryptographic purposes, however, we are usually interested in obtaining elements of a group attached to the curve, namely the Jacobian, rather than points on the curve itself. In the case of elliptic curves, the curve and its Jacobian are isomorphic so no further work is needed, but for curves of genus $k \ge 2$, they are quite different objects.

In the following, we always denote the Jacobian of $H$ by $J$, and we regard $H$ as embedded in $J$ via the map $H \to J$ sending a point $\mathbf{P}$ to the class of the degree 0 divisor $(\mathbf{P}) - (\infty)$. In particular, if $\mathbf{P}, \mathbf{Q}$ are points in $H(\mathbb{F}_q)$, $\mathbf{P} + \mathbf{Q}$ denotes the class of $(\mathbf{P}) + (\mathbf{Q}) - 2(\infty)$.

We propose two constructions of maps to $J(\mathbb{F}_q)$ to accommodate for different use cases: an injective map with large image, which can be used to encode scalars as group elements (e.g. for encryption), and a map defining an essentially uniform distribution on $J(\mathbb{F}_q)$, to obtain well-behaved hash functions.

### 7.4.1 Injective encoding to the Jacobian

Let us first recall a few facts about hyperelliptic curves, for which we refer for example to [MWZ98]. Elements of $J(\mathbb{F}_q)$ are classes of $\mathbb{F}_q$-divisors on $H$ and admit a canonical
representation as so-called reduced divisors defined over $\mathbb{F}_q$. Let $\tilde{\cdot}$ denote the hyperelliptic involution on $H$, $(x, y) \mapsto (x, -y)$. A divisor $D = P_1 + \cdots + P_r$ (where the $P_i$ are not necessarily distinct points in $H(\mathbb{F}_q)$) is said to be reduced when $r$ is less than or equal to the genus $k$ of $H$, and $P_i \neq \tilde{P}_j$ for all $i \neq j$. The reduced divisors $D$ and $D'$ defined by $P_1, \dots, P_r$ and $P'_1, \dots, P'_r$ are distinct and non-equivalent as soon as the multisets $\{P_1, \dots, P_r\}$ and $\{P'_1, \dots, P'_r\}$ are different. Each divisor class in $J(\mathbb{F}_q)$ contains a unique reduced divisor defined over $\mathbb{F}_q$.

Now, with the notations of §7.3, the encoding $f: \mathbb{F}_q \to H(\mathbb{F}_q)$ defined by (7.1) satisfies that for all $t \in \mathbb{F}_q \setminus T$, the only $u$ such that $f(u) = \tilde{f}(t)$ is $u = -t$. Therefore, if $(t_1, \dots, t_k)$ is any tuple of $k$ elements of $\mathbb{F}_q \setminus T$ ($k$ being the genus of $H$) such that $t_i + t_j \neq 0$ for all $i, j$, then $f(t_1) + \cdots + f(t_k)$ is a reduced divisor. In particular, consider the set $X$ of $k$-element subsets of $\mathbb{F}_q \setminus T$ not containing any two opposite elements. Then it is immediate from the facts above that the map:

$$ F_{\text{inj}}: X \to J(\mathbb{F}_q) \\ \{t_1, \dots, t_k\} \mapsto f(t_1) + \dots + f(t_k) $$

is injective. We have

$$ \#X = 2^k \binom{(q - \#T)/2}{k} = \frac{1 - o(1)}{k!} \cdot q^k \ge c_k \cdot \#J(\mathbb{F}_q) $$

for some constant $c_k > 0$ depending only on $k$. Thus, $F_{\text{inj}}$ is an injective mapping to $J(\mathbb{F}_q)$ covering a constant positive fraction of all points. It is also very easy to compute since points in the image are directly given as reduced divisors, so no actual arithmetic on the Jacobian is needed.

In the case that is most relevant for cryptographic applications, namely $k = 2$, we can define an even simpler injective encoding, from the set $Y$ of 2-element subsets of $\mathbb{F}_q \setminus T$, which may be easier to manipulate than $X$:

$$ F'_{\text{inj}}: Y \to J(\mathbb{F}_q) \\ \{t_1, t_2\} \mapsto f(t_1) + f(-t_2) $$

This function injective, easy to compute, and reaches roughly one half of all points in $J(\mathbb{F}_q)$.

### 7.4.2 Indifferentiable hashing to the Jacobian

One can also use $f$ to construct well-behaved hash functions to $J(\mathbb{F}_q)$. For this purpose, we have shown in Chapter 5 how one could use functions to $J(\mathbb{F}_q)$ with good regularity properties, and described in Chapter 6 how character sum estimates could be used to prove such regularity properties for functions of the form:

$$ f^{\otimes s}: (\mathbb{F}_q)^s \to J(\mathbb{F}_q) \\ (t_1, \dots, t_s) \mapsto f(t_1) + \dots + f(t_s). $$
Since $f$ is so simple, we do not really need to rely on the entire framework of Chapter 6. Indeed, the following bound, which in the terminology of the previous chapter says that $f$ is a $(2k - 2 + \varepsilon)$-well-distributed encoding, can be proved using classical results on characters on algebraic curves. Note that this bound is very tight: it gives a better well-distributedness bound for $f$ in genus up to 6 than can be established for Icart's function in genus 1.

**Lemma 7.1.** For any character $\chi$ of the abelian group $J(\mathbb{F}_q)$, let

$$S(\chi) = \sum_{t \in \mathbb{F}_q} \chi(f(t)).$$

Then, whenever $\chi$ is nontrivial, we have

$$|S(\chi)| \le (2k - 2)\sqrt{q} + 4k + 3.$$

*Proof.* A nontrivial character $\chi$ of $J(\mathbb{F}_q)$ is also a nontrivial, unramified Artin character of $H$ (see [KS00, §2] or §6.3). In particular, the Riemann hypothesis for the $L$-function on $H$ associated with $\chi$ gives:

$$\left| \sum_{\mathbf{P} \in H(\mathbb{F}_q)} \chi(\mathbf{P}) \right| \le (2k - 2)\sqrt{q}.$$

The result then follows from the observation that

$$\begin{aligned} \sum_{t \in \mathbb{F}_q} \chi(f(t)) &= \#T \cdot \chi((0,0)) + \sum_{\mathbf{P} \in H(\mathbb{F}_q) \setminus W} \chi(\mathbf{P}) \\ &= \#T \cdot \chi((0,0)) - \sum_{\mathbf{P} \in W} \chi(\mathbf{P}) + \sum_{\mathbf{P} \in H(\mathbb{F}_q)} \chi(\mathbf{P}) \end{aligned}$$

since $\#T + \#W \le 4k + 3$. $\square$

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

We can then proceed like in §6.2 and deduce from this lemma a bound on the statistical distance between the distribution defined on $J(\mathbb{F}_q)$ by $f^{\otimes s}$ and the uniform distribution.

For any $\mathbf{D} \in J(\mathbb{F}_q)$, let $N_s(\mathbf{D})$ denote the number of preimages of $\mathbf{D}$ under $f^{\otimes s}$:

$$N_s(\mathbf{D}) = \#\{(t_1, \dots, t_s) \in (\mathbb{F}_q)^s \mid \mathbf{D} = f(t_1) + \dots + f(t_s)\}$$

Then we have the following result:

**Theorem 7.2.** The statistical distance between the distribution defined by $f^{\otimes s}$ and the uniform distribution on $J(\mathbb{F}_q)$ is bounded as:

$$\sum_{\mathbf{D} \in J(\mathbb{F}_q)} \left| \frac{N_s(\mathbf{D})}{q^s} - \frac{1}{\#J(\mathbb{F}_q)} \right| \le \frac{(2k + 2 + (4k + 3)q^{-1/2})^s \sqrt{\#J(\mathbb{F}_q)}}{q^{s/2}}.$$
*Proof.* This results from Corollary 6.2 in the previous chapter. □

Note that $\#J(\mathbb{F}_q) \sim q^k$, so that the bound we get on the statistical distance is in $O(q^{(k-s)/2})$. Therefore, as soon as $s > k$, the distribution defined by $f^{\otimes s}$ on $J(\mathbb{F}_q)$ is statistically indistinguishable from the uniform distribution. In particular, in the terminology of Chapter 5, the encoding $f^{\otimes(k+1)}$ to $J(\mathbb{F}_q)$ is regular (see Definition 5.3). It is also obviously computable and samplable, so $f^{\otimes(k+1)}$ is an admissible encoding to $J(\mathbb{F}_q)$.

This provides a simple, well-behaved hash function construction to the Jacobian of $H$. Indeed, it follows that the hash function defined by

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + \dots + f(\mathfrak{h}_{k+1}(m)) $$

is indifferentiable from a random oracle when $\mathfrak{h}_1, \dots, \mathfrak{h}_{k+1}$ are seen as independent random oracles into $\mathbb{F}_q$.

## 7.5 Conclusion

In this chapter, we provide a very efficient construction of a deterministic encoding into odd hyperelliptic curves. Odd hyperelliptic curves are a simple and relatively large class of hyperelliptic curves, compared to the families of curves covered by previous deterministic encodings. They also include many curves of cryptographic interest (because of efficient point-counting on the Jacobian, or pairing-friendliness), even in the elliptic curve case.

This encoding is almost a bijection, which can be useful for a number of applications, such as encryption, and allows us to construct the first efficient injections with large image to the Jacobians of odd hyperelliptic curves, as well as indifferentiable hash functions to these Jacobians with particularly tight regularity bounds.
<figure><img src="image_14.png" /></figure>
# Huff's Model for Elliptic Curves

## 8.1 Introduction

This chapter moves away from the problem of hashing and encoding to elliptic curves to concentrate on a very different practical concern arising in elliptic curve cryptography: constructing elliptic curve models with efficient arithmetic operations.

Specifically, we revisit an elliptic curve model introduced by Huff in 1948, originally to study a diophantine problem, and present explicit formulas for adding or doubling points on these curves with a number of desirable features, including completeness and independence on curve parameters. We also suggest extensions and generalizations of this model that may be of interest for cryptographic applications, and consider the problem of pairing computations over Huff curves. This work was presented at ANTS-IX [JTV10].

### 8.1.1 Background

*Cryptography and efficient elliptic curve arithmetic.* The use of elliptic curves in cryptography makes key sizes smaller compared to other groups where the discrete logarithm and related problems are hard, such as subgroups of $Z_p^*$, but the arithmetic of the underlying group is more complex (for example, with the widely-used Jacobian coordinates, the general addition of two points on an elliptic curve typically requires 16 multiplications in the base field). Therefore, a large amount of research has been devoted to analyzing how efficient the group operations can be made for many “shapes” of elliptic curves proposed in the mathematical literature: Weierstrass cubics, Jacobi intersections, Hessian curves, Jacobi quartics, or the more recent forms of elliptic curves due to Montgomery, Doche-Icart-Kohel or Edwards (see [BL08] for an encyclopedic overview of these models).

For instance, since 2007, there has been a rapid development of the curves introduced by Edwards in [Edw07] and their use in cryptology. Bernstein and Lange proposed a more general version of these curves in [BL07a] and the *inverted Edwards* coordinates in [BL07b]. Bernstein, Birkner, Joye, Lange, and Peters studied *twisted Edwards* curves in [BBJ+08]. Hisil, Wong, Carter and Dawson proposed *extended twisted Edwards* coordinates in [HWCD08]. Bernstein, Lange, and Farashahi covered the *binary case* in [BLF08].
The first formulas for computing *pairings* over Edwards curves were published by Das and Sarkar [DS08]. They were subsequently improved by Ionica and Joux [IJ08]. The best implementation to date is due to Arène, Lange, Naehrig, and Ritzenthaler [ALNR11]. The present chapter provides a similar study for a forgotten model of elliptic curves hinted to by Huff in 1948.

A diophantine problem. Huff [Huf48] considered rational distance sets $S$ (i.e., subsets $S$ of the plane $\mathbb{R}^2$ such that for all $s, t \in S$, the distance between $s$ and $t$ is a rational number) of the following form: given distinct $a, b \in \mathbb{Q}$, $S$ contains the four points $(0, \pm a)$ and $(0, \pm b)$ on the $y$-axis, plus points $(x, 0)$ on the $x$-axis, for some $x \in \mathbb{Q}$. Such a point $(x, 0)$ must then satisfy the equations $x^2 + a^2 = u^2$ and $x^2 + b^2 = v^2$ with $u, v \in \mathbb{Q}$. The system of associated homogeneous equations $x^2 + a^2z^2 = u^2$ and $x^2 + b^2z^2 = v^2$ defines a curve of genus 1 in $\mathbb{P}^3$. Huff, and later his student Peeples [Pee54], provided examples where this curve has positive rank over $\mathbb{Q}$, thus exhibiting examples of arbitrarily large rational distance sets of cardinality $k > 4$ such that exactly $k - 4$ points are on one line.

The above mentioned genus 1 curve is birationally equivalent to the curve

$$ax(y^2 - 1) = by(x^2 - 1) \qquad (8.1)$$

for some parameters $a$ and $b$ in $\mathbb{Q}$. It is easily seen that, over any field $\mathbb{K}$ of odd characteristic, Equation (8.1) defines an elliptic curve if $a^2 \neq b^2$ and $a, b \neq 0$. Indeed, if $ab \neq 0$, the gradient of the curve $F(X, Y, Z) = aX(Y^2 - Z^2) - bY(X^2 - Z^2)$ in the projective plane $\mathbb{P}^2(\mathbb{K})$ is

$$\left(\frac{\partial F}{\partial X}, \frac{\partial F}{\partial Y}, \frac{\partial F}{\partial Z}\right) = (a(Y^2 - Z^2) - 2bXY, 2aXY - b(X^2 - Z^2), 2(-aX + bY)Z),$$

which does not vanish at the three points at infinity $(1:0:0)$, $(0:1:0)$ and $(a:b:0)$ and vanishes at a finite point $(x:y:1)$ if and only if $ax = by$, which together with equation (8.1) implies that $x^2 = y^2$ and therefore $a^2 = b^2$. It is worth noting that in characteristic 2, the point $(1:1:1)$ is always singular and therefore the family of curves defined by (8.1) does not contain any smooth curve. As will be shown in §8.3, we can extend our study to even characteristic by considering a generalized model.

### 8.1.2 Our contributions

Our first contribution is a detailed study of Huff's form for elliptic curves over finite fields of odd characteristic and a statement of the addition law in these groups. We show in particular that all elliptic curves over non-binary finite fields with a subgroup isomorphic to $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ can be transformed to Huff's form. We then analyze their arithmetic and investigate several generalizations and extensions. In particular, we present explicit formulas (i.e., as a series of field operations) that

* compute a complete addition $(X_1 : Y_1 : Z_1) \oplus (X_2 : Y_2 : Z_2)$ using 12m;

* compute a unified addition $(X_1 : Y_1 : Z_1) \oplus (X_2 : Y_2 : Z_2)$ using 11m;
* compute a mixed addition $(X_1 : Y_1 : Z_1) \oplus (X_2 : Y_2 : 1)$ using $10m$;

* compute a doubling $[2](X_1 : Y_1 : Z_1)$ using $6m + 5s$

where $m$ and $s$ denote multiplications and squarings in the base field $K$.

As a further contribution, since bilinear pairings have found numerous applications in cryptography, we also present formulas for computing Tate pairings using Huff's form. Specifically, we present explicit formulas that

* compute a *full* Miller addition using $1M + (k + 15)m$;

* compute a *mixed* Miller addition using $1M + (k + 13)m$;

* compute a Miller doubling using $1M + 1S + (k + 11)m + 6s$

on a Huff curve over $K = \mathbb{F}_q$ of embedding degree $k$. $M$ and $S$ denote multiplications and squarings in the larger field $\mathbb{F}_{q^k}$ while $m$ and $s$ are operations in $\mathbb{F}_q$ as before.

**Outline.** The rest of this chapter is organized as follows. The next section introduces Huff's model. We develop efficient unified addition formulas and discuss the applicability of the model. We explicit the class of elliptic curves covered by Huff's model. In §8.3, we present several generalizations and extensions. We offer dedicated addition formulas. We generalize Huff's model to cover a larger class of elliptic curves. We also extend the model to the case of binary fields. §8.4 deals with pairings over Huff curves. We exploit the relative simplicity of the underlying group law to devise efficient formulas for the evaluation of the Tate pairing. Finally, we conclude in §8.5.

## 8.2 Huff's Model

Let $K$ denote a field of characteristic $\neq 2$. Consider the set of projective points $(X : Y : Z) \in \mathbb{P}^2(K)$ satisfying the equation

$$E/K: aX(Y^2 - Z^2) = bY(X^2 - Z^2) \qquad (8.2)$$

where $a, b \in K^\times$ and $a^2 \neq b^2$. This form is referred to as *Huff's model* of an elliptic curve.

The tangent line at $(0 : 0 : 1)$ is $aX = bY$, which intersects the curve with multiplicity 3, so that $O = (0 : 0 : 1)$ is an inflection point of $E$. $(E, O)$ is therefore an elliptic curve with $O$ as neutral element and whose group law, denoted $\oplus$, has the following property: for any line intersecting the cubic curve $E$ at the three points $P_1, P_2$ and $P_3$ (counting multiplicities), we have $P_1 \oplus P_2 \oplus P_3 = O$. In particular, the inverse of point $P_1 = (X_1 : Y_1 : Z_1)$ is $\ominus P_1 = (X_1 : Y_1 : -Z_1)$ and the sum of $P_1$ and $P_2$ is $P_1 \oplus P_2 = \ominus P_3$. We note that a point at infinity is its own inverse. Hence, the three points at infinity (i.e., on the line $Z = 0$ in $\mathbb{P}^2$) — namely, $(1 : 0 : 0)$, $(0 : 1 : 0)$ and $(a : b : 0)$, are exactly the three primitive 2-torsion points of $E$. The sum of any two of them is equal to the third
<figure><img src="image_15.png" /><figcaption>Figure 8.1: Example of a Huff curve (over $\mathbb{R}$).</figcaption></figure>

one. More generally, $(X_1 : Y_1 : Z_1) \oplus (1 : 0 : 0)$ is the inverse of the point of intersection of the “horizontal” line passing through $(X_1 : Y_1 : Z_1)$ with $E$. When $Z_1 \neq 0$, we have

$$ (X_1 : Y_1 : Z_1) \oplus (1 : 0 : 0) = (Z_1^2 : -X_1Y_1 : X_1Z_1), $$

and analogously,

$$ (X_1 : Y_1 : Z_1) \oplus (0 : 1 : 0) = (-X_1Y_1 : Z_1^2 : Y_1Z_1). $$

From $(a : b : 0) = (1 : 0 : 0) \oplus (0 : 1 : 0)$, when $Z_1 \neq 0$, we get $(X_1 : Y_1 : Z_1) + (a : b : 0) = (Z_1^2 : -X_1Y_1 : X_1Z_1) \oplus (0 : 1 : 0)$ and therefore

$$ (X_1 : Y_1 : Z_1) \oplus (a : b : 0) = \begin{cases} (a : b : 0) & \text{if } (X_1 : Y_1 : Z_1) = (0 : 0 : 1) \\ (Y_1Z_1 : X_1Z_1 : -X_1Y_1) & \text{otherwise} \end{cases}. $$

We remark that adding $(a : b : 0)$ to any of the points $(\pm 1 : \pm 1 : 1)$ transforms it into its inverse. It follows that these four points are the four solutions to the equation [2] $\mathbf{P} = (a : b : 0)$ and so are primitive 4-torsion points. The eight remarkable points we identified from a subgroup isomorphic to $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$. When $\mathbb{K} = \mathbb{Q}$, this must be the full torsion since, according to a theorem by Mazur, the torsion subgroup is of order at most 12 (and thus exactly 8 here).

*Remark 8.1.* In [Huf48, p. 445], it is noted that the inverse projective transformations

$$ \begin{gathered} \Upsilon : \mathbb{P}^2(\mathbb{K}) \to \mathbb{P}^2(\mathbb{K}) : \\ (X : Y : Z) \mapsto (U : V : W) = (ab(bX - aY) : ab(b^2 - a^2)Z : -aX + bY) \end{gathered} $$
and

$$ \Upsilon^{-1} : \mathbb{P}^2(\mathbb{K}) \to \mathbb{P}^2(\mathbb{K}) : $$

$$ (U : V : W) \mapsto (X : Y : Z) = (b(U + a^2W) : a(U + b^2W) : V) $$

induce a correspondence between equation (8.2) and the Weierstrass equation

$$ V^2W = U(U + a^2W)(U + b^2W) . $$

Observe that point at infinity (0 : 1 : 0) on the Weierstrass curve is mapped to (0 : 0 : 1) on the Huff curve through $\Upsilon^{-1}$. Observe also that map $\Upsilon^{-1}$ is a line-preserving transformation. This is another way to see that the group law on a Huff curve E follows the chord-and-tangent rule [Sil86, §2] with $O = (0 : 0 : 1)$ as neutral element.

### 8.2.1 Affine formulas

We give explicit formulas for the group law. Excluding the 2-torsion, we use the non-homogeneous form $ax(y^2 - 1) = by(x^2 - 1)$. Let $y = \lambda x + \mu$ denote the secant line passing through two different points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$. This line intersects the curve at a third point $\ominus P_3 = (-x_3, -y_3)$. Plugging the line equation into the curve equation, we get

$$ ax((\lambda x + \mu)^2 - 1) = b(\lambda x + \mu)(x^2 - 1) \implies \lambda(a\lambda - b)x^3 + \mu(2a\lambda - b)x^2 + \dots = 0 . $$

Whenever defined, we so obtain

$$ \begin{cases} x_3 = x_1 + x_2 + \frac{\mu(2a\lambda - b)}{\lambda(a\lambda - b)} \\ y_3 = \lambda x_3 - \mu \end{cases} $$

with $\lambda = \frac{y_1 - y_2}{x_1 - x_2}$ and $\mu = y_1 - \lambda x_1$. After simplification, we have

$$ \begin{aligned} x_3 &= x_1 + x_2 + \frac{(x_1y_2 - x_2y_1)(2a(y_1 - y_2) - b(x_1 - x_2))}{(y_1 - y_2)(a(y_1 - y_2) - b(x_1 - x_2))} \\ &= \frac{(x_1 - x_2)(a(y_1^2 - y_2^2) - b(x_1y_1 - x_2y_2))}{(y_1 - y_2)(a(y_1 - y_2) - b(x_1 - x_2))} \end{aligned} $$

and

$$ y_3 = - \frac{(y_1 - y_2)(b(x_1^2 - x_2^2) - a(x_1y_1 - x_2y_2))}{(x_1 - x_2)(a(y_1 - y_2) - b(x_1 - x_2))} . $$

The above formulas can be further simplified by reusing the curve equation. A simple calculation shows that

$$ (a(y_1 - y_2) - b(x_1 - x_2))(x_1 + x_2)y_1y_2 = a(x_2y_1 - x_1y_2)(y_1y_2 - 1) . $$
Hence, we can write

$$ 
\begin{aligned}
x_3 &= x_1 + x_2 - \frac{(2a(y_1 - y_2) - b(x_1 - x_2))(x_1 + x_2)y_1y_2}{(y_1 - y_2)a(y_1y_2 - 1)} \\
&= x_1 + x_2 - \frac{x_2y_1 - x_1y_2}{y_1 - y_2} - \frac{(x_1 + x_2)y_1y_2}{y_1y_2 - 1} \\
&= \frac{x_1y_1 - x_2y_2}{y_1 - y_2} - \frac{(x_1 + x_2)y_1y_2}{y_1y_2 - 1}.
\end{aligned}
$$

Furthermore, as easily shown

$$b(x_1y_1 - x_2y_2)(x_1x_2 + 1) = (y_1 - y_2)(ax_1x_2(y_1 + y_2) + b(x_1 + x_2)),$$

it thus follows that

$$ 
\begin{aligned}
x_3 &= \frac{ax_1x_2(y_1 + y_2) + b(x_1 + x_2)}{b(x_1x_2 + 1)} - \frac{(x_1 + x_2)y_1y_2}{y_1y_2 - 1} \\
&= \frac{(x_1 + x_2)(1 + y_1y_2)}{(1 + x_1x_2)(1 - y_1y_2)},
\end{aligned}
\quad (8.3) $$

since $ax_1x_2(y_1 + y_2)(1 - y_1y_2) = by_1y_2(x_1 + x_2)(1 - x_1x_2)$.

Likewise, by symmetry, we have

$$y_3 = \frac{(y_1 + y_2)(1 + x_1x_2)}{(1 - x_1x_2)(1 + y_1y_2)}. \quad (8.4)$$

Equations (8.3) and (8.4) are defined whenever $x_1x_2 \neq \pm 1$ and $y_1y_2 \neq \pm 1$. Advantageously, curve parameters are not involved. Moreover, this addition law is unified: it can be used to double a point (i.e., when $\mathbf{P}_2 = \mathbf{P}_1$).

### 8.2.2 Projective formulas

Previous affine formulas involve inversions in $\mathbb{K}$. To avoid these operations and get faster arithmetic, projective coordinates may be preferred.

We let $m$ and $s$ represent the cost of a multiplication and of a squaring in $\mathbb{K}$, respectively. The projective form of (8.3) and (8.4) is

$$ 
\left\{ 
\begin{aligned}
X_3 &= (X_1Z_2 + X_2Z_1)(Y_1Y_2 + Z_1Z_2)^2(Z_1Z_2 - X_1X_2) \\
Y_3 &= (Y_1Z_2 + Y_2Z_1)(X_1X_2 + Z_1Z_2)^2(Z_1Z_2 - Y_1Y_2) \\
Z_3 &= (Z_1^2Z_2^2 - X_1^2X_2^2)(Z_1^2Z_2^2 - Y_1^2Y_2^2)
\end{aligned}
\right. . \quad (8.5) $$

In more detail, this can be evaluated as

$$ 
\begin{aligned}
m_1 &= X_1X_2, \quad m_2 = Y_1Y_2, \quad m_3 = Z_1Z_2, \\
m_4 &= (X_1 + Z_1)(X_2 + Z_2) - m_1 - m_3, \quad m_5 = (Y_1 + Z_1)(Y_2 + Z_2) - m_2 - m_3, \\
m_6 &= (m_2 + m_3)(m_3 - m_1), \quad m_7 = (m_1 + m_3)(m_3 - m_2), \\
m_8 &= m_4(m_2 + m_3), \quad m_9 = m_5(m_1 + m_3), \\
X_3 &= m_8m_6, \quad Y_3 = m_9m_7, \quad Z_3 = m_6m_7,
\end{aligned}
$$

that is, with $\underline{12m}$.
### 8.2.3 Applicability

If $(x_1, y_1) \neq (0,0)$ then $(x_1, y_1) \oplus (a : b : 0) = -(\frac{1}{x_1}, \frac{1}{y_1})$. Observe that Equation (8.5) remains valid for doubling point $(a : b : 0)$ or for adding point $(a : b : 0)$ to another finite point (i.e., which is not at infinity) different from $O$; we get $(X_1 : Y_1 : Z_1) \oplus (a : b : 0) = (-Y_1Z_1 : -X_1Z_1 : X_1Y_1)$ as expected. The addition formula is however not valid for adding $(0 : 1 : 0)$ or $(1 : 0 : 0)$. More generally, we have:

**Theorem 8.1.** Let $\mathbb{K}$ be a field of characteristic $\neq 2$. Let $\mathbf{P}_1 = (X_1 : Y_1 : Z_1)$ and $\mathbf{P}_2 = (X_2 : Y_2 : Z_2)$ be two points on a Huff curve over $\mathbb{K}$. Then the addition formula given by (8.5) is valid provided that $X_1X_2 \neq \pm Z_1Z_2$ and $Y_1Y_2 \neq \pm Z_1Z_2$.

*Proof.* If $\mathbf{P}_1$ and $\mathbf{P}_2$ are finite, we can write $\mathbf{P}_1 = (x_1, y_1)$ and $\mathbf{P}_2 = (x_2, y_2)$. The above affine formula for $(x_3, y_3)$ as given by (8.3) and (8.4) is defined whenever $x_1x_2 \neq \pm 1$ and $y_1y_2 \neq \pm 1$. This translates into $X_1X_2 \neq \pm Z_1Z_2$ and $Y_1Y_2 \neq \pm Z_1Z_2$ for their projective coordinates.

It remains to analyze points at infinity. The points with their $Z$-coordinate equal to 0 are $(1:0:0)$, $(0:1:0)$ and $(a:b:0)$. If $\mathbf{P}_1$ or $\mathbf{P}_2 \in \{(1:0:0), (0:1:0)\}$, the condition $X_1X_2 \neq \pm Z_1Z_2$ and $Y_1Y_2 \neq \pm Z_1Z_2$ is not satisfied. Suppose now $\mathbf{P}_2 = (a:b:0)$. The condition becomes $X_1 \neq 0$ and $Y_1 \neq 0$, which corresponds to $\mathbf{P}_1 \notin \{O, (1:0:0), (0:1:0)\}$. As aforementioned, the addition law is then valid for adding $\mathbf{P}_1$ to $(a:b:0)$. $\square$

The previous theorem says that the addition on a Huff curve is almost complete. However, the exceptional inputs are easily prevented in practice. Cryptographic applications typically involve (large) prime-order subgroups. More specifically, we state:

**Corollary 8.1.** Let $E$ be a Huff curve over a field $\mathbb{K}$ of odd characteristic. Let also $\mathbf{P} \in E(\mathbb{K})$ be a point of odd order. Then the addition law in the subgroup generated by $\mathbf{P}$ is complete.

*Proof.* All points in $\langle \mathbf{P} \rangle$ are of odd order and thus are finite (remember that points at infinity are of order 2). It remains to show that for any points $\mathbf{P}_1 = (x_1, y_1)$, $\mathbf{P}_2 = (x_2, y_2) \in \langle \mathbf{P} \rangle$, we have $x_1x_2 \neq \pm 1$ and $y_1y_2 \neq \pm 1$. Note that $x_1, y_1, x_2, y_2 \neq \pm 1$ since this corresponds to points of order 4 (and thus not in $\langle \mathbf{P} \rangle$). Suppose that $x_1x_2 = \pm 1$. Then $ax_1(y_1^2-1) = by_1(x_1^2-1) \implies a\frac{1}{x_1}(y_1^2-1) = by_1(1-\frac{1}{x_1^2}) \implies \pm ax_2(y_1^2-1) = -by_1(x_2^2-1)$. Hence, since $ax_2(y_2^2-1) = by_2(x_2^2-1)$, it follows that $\mp y_2(y_1^2-1) = y_1(y_2^2-1) \implies (y_1 \pm y_2)(1 \mp y_1y_2) = 0 \implies y_2 = \mp y_1$ or $y_1y_2 = \pm 1$. As a result, when $x_1x_2 = \pm 1$, we have $(x_2, y_2) \in \{(\frac{1}{x_1}, -y_1), (\frac{1}{x_1}, \frac{1}{y_1}), (-\frac{1}{x_1}, y_1), (-\frac{1}{y_1}, -\frac{1}{x_1})\}$. In all cases, one of $(x_1, y_1) \oplus (x_2, y_2)$ or $(x_1, y_1) \ominus (x_2, y_2)$ is a 2-torsion point, a contradiction. Likewise, it can be verified that the case $y_1y_2 = \pm 1$ leads to a contradiction, which concludes the proof. $\square$

The completeness of the addition law is very useful as it yields a natural protection against certain side-channel attacks (e.g., see [BSS05]). Another useful feature is that the addition law is *independent* of the curve parameters.
### 8.2.4 Universality of the model

The next theorem states that every elliptic curve over a field of characteristic $\neq 2$ containing a copy of $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ can be put in Huff's form. Generalizations and extensions are discussed in §8.3.

**Theorem 8.2.** Any elliptic curve $(E, \mathbf{O})$ over a perfect field $\mathbb{K}$ of characteristic $\neq 2$ such that $E(\mathbb{K})$ contains a subgroup $\mathbb{G}$ isomorphic to $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ is birationally equivalent over $\mathbb{K}$ to a Huff curve.

*Proof.* The Riemann-Roch theorem implies that if $\mathbf{D} = a_1\mathbf{P}_1 + \cdots + a_r\mathbf{P}_r$ is a divisor of degree 0 on $E$ then the dimension of the vector space

$$ \mathcal{L}(\mathbf{D}) = \{f \in \mathbb{K}(E)^\times \mid \mathrm{div}(f) \geq -\mathbf{D}\} \cup \{\mathbf{0}\} $$

is equal to 1 when $a_1\mathbf{P}_1 \oplus \cdots \oplus a_r\mathbf{P}_r = \mathbf{O}$, and to 0 otherwise.

Let $\mathbf{H}_{++}$, $\mathbf{H}_{+-}$, $\mathbf{H}_{-+}$ and $\mathbf{H}_{--}$ denote the four points of $\mathbb{G}$ of order exactly 4 (with the convention $\mathbf{H}_{++} \oplus \mathbf{H}_{--} = \mathbf{O}$). Doubling these points produces a unique primitive 2-torsion point that we denote $\mathbf{R}$. We further let $\mathbf{P}$ and $\mathbf{Q}$ denote the other two 2-torsion points; say, $\mathbf{P} = \ominus \mathbf{H}_{++} \oplus \mathbf{H}_{+-}$ and $\mathbf{Q} = \mathbf{H}_{++} \oplus \mathbf{H}_{+-}$. We have $\mathbf{P} \oplus \mathbf{R} \ominus \mathbf{Q} \ominus \mathbf{O} = \mathbf{O}$; so there exists a nonzero rational function $x$ with divisor exactly $\mathbf{Q} + \mathbf{O} - \mathbf{P} - \mathbf{R}$. In particular, $x$ is well-defined and nonzero at $\mathbf{H}_{++}$ and thus without loss of generality we may assume that $x(\mathbf{H}_{++}) = 1$. Similarly, there exists a rational function $y$ with divisor $\mathbf{P} + \mathbf{Q} - \mathbf{Q} - \mathbf{R}$ such that $y(\mathbf{H}_{++}) = 1$.

The rational function $x-1$ has the same poles as $x$ and vanishes at $\mathbf{H}_{++}$. Its divisor $\mathrm{div}(x-1)$ is thus given by $\mathbf{H}_{++} + \mathbf{X} - \mathbf{P} - \mathbf{R}$ for some point $\mathbf{X}$. Since this divisor is principal, we have $\mathbf{H}_{++} \oplus \mathbf{X} \ominus \mathbf{P} \ominus \mathbf{R} = \mathbf{O}$. Hence, it follows that $\mathbf{X} = \mathbf{P} \oplus \mathbf{R} \ominus \mathbf{H}_{++} = \ominus \mathbf{H}_{++} \oplus \mathbf{H}_{+-} \oplus \mathbf{R} \ominus \mathbf{H}_{++} = \mathbf{H}_{+-}$. Consequently, we have $x(\mathbf{H}_{+-}) = 1$. Likewise, it is verified that $y(\mathbf{H}_{+-}) = 1$.

Now, consider the map $\iota$ taking a rational function $f$ to $\iota f : \mathbf{M} \mapsto f(\ominus \mathbf{M})$. This is an endomorphism of the vector space $\mathcal{L}(\mathbf{P}+\mathbf{R}-\mathbf{Q}-\mathbf{O})$. Indeed, the poles of $\iota f$ are $\ominus \mathbf{P} = \mathbf{P}$ and $\ominus \mathbf{R} = \mathbf{R}$ and its zeros are $\ominus \mathbf{Q} = \mathbf{Q}$ and $\ominus \mathbf{O} = \mathbf{O}$. Moreover, since $\iota^2 = \mathrm{id}$ and since $\mathcal{L}(\mathbf{P}+\mathbf{R}-\mathbf{Q}-\mathbf{O})$ is a one-dimensional vector space, $\iota$ is the multiplication map by 1 or $-1$. The equality $\iota x = x$ would imply $x(\mathbf{H}_{--}) = x(\mathbf{H}_{++}) = 1$, which contradicts the previous calculation of $\mathrm{div}(x-1)$. As a result, we must have $\iota x = -x$. In particular, noting that $\mathbf{H}_{+-} = \ominus \mathbf{H}_{+-}$, we obtain

$$ x(\mathbf{H}_{+-}) = \iota x(\mathbf{H}_{+-}) = -x(\mathbf{H}_{+-}) = -1, $$

and similarly for $\mathbf{H}_{--}$. Since $x+1$ has the same poles as $x$, its divisor is then given by $\mathrm{div}(x+1) = \mathbf{H}_{+-} + \mathbf{H}_{--} - \mathbf{P} - \mathbf{R}$. Analogously, we obtain $\mathrm{div}(y+1) = \mathbf{H}_{+-} + \mathbf{H}_{--} - \mathbf{Q} - \mathbf{R}$.

Finally, consider the rational functions $u = x(y^2 - 1)$ and $v = y(x^2 - 1)$. We have:

$$ \begin{aligned} \mathrm{div}(u) &= \mathrm{div}(x) + \mathrm{div}(y-1) + \mathrm{div}(y+1) \\ &= (\mathbf{Q} + \mathbf{O} - \mathbf{P} - \mathbf{R}) + (\mathbf{H}_{++} + \mathbf{H}_{+-} - \mathbf{Q} - \mathbf{R}) + (\mathbf{H}_{+-} + \mathbf{H}_{--} - \mathbf{Q} - \mathbf{R}) \\ &= \mathbf{H}_{++} + \mathbf{H}_{+-} + \mathbf{H}_{-+} + \mathbf{H}_{--} + \mathbf{O} - \mathbf{P} - \mathbf{Q} - 3\mathbf{R} \end{aligned} $$

and
$$
\begin{align*}
\mathrm{div}(v) &= \mathrm{div}(y) + \mathrm{div}(x-1) + \mathrm{div}(x+1) \\
&= (\mathbf{P} + \mathbf{O} - \mathbf{Q} - \mathbf{R}) + (\mathbf{H}_{++} + \mathbf{H}_{+-} - \mathbf{P} - \mathbf{R}) + (\mathbf{H}_{-+} + \mathbf{H}_{--} - \mathbf{P} - \mathbf{R}) \\
&= \mathbf{H}_{++} + \mathbf{H}_{+-} + \mathbf{H}_{-+} + \mathbf{H}_{--} + \mathbf{O} - \mathbf{P} - \mathbf{Q} - 3\mathbf{R}.
\end{align*}
$$

But the vector space $\mathcal{L}(\mathbf{P} + \mathbf{Q} + 3\mathbf{R} - \mathbf{O} - \mathbf{H}_{++} - \mathbf{H}_{+-} - \mathbf{H}_{-+} - \mathbf{H}_{--})$ is of dimension 1, so there exists a linear relation between $u$ and $v$. In other words, there exist $a, b \in \mathbb{K}^*$ such that $au = bv$; i.e., such that $ax(y^2 - 1) = by(x^2 - 1)$.

The rational map $E \to \mathbb{P}^2(\mathbb{K})$ given by $\mathbf{M} \mapsto (x(\mathbf{M}) : y(\mathbf{M}) : 1)$ extends to a morphism defined on all of $E$, and its image is contained in $E_{a,b}$ in view of the previous relation (and $E_{a,b}$ itself is a smooth irreducible curve as seen in §8.1.1). We therefore have a non-constant — and hence surjective — morphism of curves $E \to E_{a,b}$. Moreover, its degree is at most 1: indeed, if a point $(x_0 : y_0 : 1) \in E_{a,b}(\mathbb{K})$ has two distinct preimages $\mathbf{M} \neq \mathbf{M}' \in E(\mathbb{K})$, the functions $x - x_0$ and $y - y_0$ vanish at $\mathbf{M}$ and $\mathbf{M}'$. Since they have the same poles as $x$ and $y$, their divisors are respectively $\mathbf{M} + \mathbf{M}' - \mathbf{P} - \mathbf{R}$ and $\mathbf{M} + \mathbf{M}' - \mathbf{Q} - \mathbf{R}$, which yields $\mathbf{P} \oplus \mathbf{R} = \mathbf{M} \oplus \mathbf{M}' = \mathbf{Q} \oplus \mathbf{R}$, a contradiction. As a surjective morphism of degree 1, the map $E \to E_{a,b}$ is thus an isomorphism. $\square$

## 8.3 Generalizations and Extensions

This section presents dedicated addition formulas. It also presents a generalization of the model as originally introduced by Huff so that it covers more curves and extends to binary fields.

### 8.3.1 Faster computations

**Dedicated doubling.** The doubling formula can be sped up by evaluating squarings in $\mathbb{K}$ with a specialized implementation. The cost of a point doubling then becomes $7m + 5s$. When $s > \frac{3}{4}m$, an even faster way for doubling a point is given by

$$
\begin{align*}
m_1 &= X_1 Y_1, \quad m_2 = X_1 Z_1, \quad m_3 = Y_1 Z_1, \quad s_1 = Z_1^2, \\
m_4 &= (m_2 - m_3)(m_2 + m_3), \quad m_5 = (m_1 - s_1)(m_1 + s_1), \\
m_6 &= (m_1 - s_1)(m_2 - m_3), \quad m_7 = (m_1 + s_1)(m_2 + m_3), \\
X([2]\mathbf{P}_1) &= (m_6 - m_7)(m_4 + m_5), \quad Y([2]\mathbf{P}_1) = (m_6 + m_7)(m_4 - m_5), \\
Z([2]\mathbf{P}_1) &= (m_4 + m_5)(m_4 - m_5),
\end{align*}
$$

that is, with $10m + 1s$.

**Moving the origin.** Choosing $\mathbf{O}' = (0 : 1 : 0)$ as the neutral element results in translating the group law. If we let $\oplus'$ denote the corresponding point addition, we have $\mathbf{P}_1 \oplus' \mathbf{P}_2 = (\mathbf{P}_1 \ominus \mathbf{O}') \oplus (\mathbf{P}_2 \ominus \mathbf{O}') \oplus \mathbf{O}' = \mathbf{P}_1 \oplus \mathbf{P}_2 \oplus \mathbf{O}'$. Hence, we get

$$
\left\{
\begin{array}{l}
X_3 = (X_1 Z_2 + X_2 Z_1)(Y_1 Y_2 + Z_1 Z_2)(Y_1 Z_2 + Y_2 Z_1) \\
Y_3 = (X_1 X_2 - Z_1 Z_2)(Z_1^2 Z_2^2 - Y_1^2 Y_2^2) \\
Z_3 = (Y_1 Z_2 + Y_2 Z_1)(X_1 X_2 + Z_1 Z_2)(Y_1 Y_2 - Z_1 Z_2)
\end{array}
\right.
$$
This can be evaluated with 11m as

$$
\begin{align}
m_1 &= X_1 X_2, \quad m_2 = Y_1 Y_2, \quad m_3 = Z_1 Z_2, \nonumber \\
m_4 &= (X_1 + Z_1)(X_2 + Z_2) - m_1 - m_3, \quad m_5 = (Y_1 + Z_1)(Y_2 + Z_2) - m_2 - m_3, \tag{8.6} \\
X_3 &= m_4(m_2 + m_3)m_5, \quad Y_3 = (m_1 - m_3)(m_3 - m_2)(m_3 + m_2), \nonumber \\
Z_3 &= m_5(m_1 + m_3)(m_2 - m_3). \nonumber
\end{align}
$$

This addition formula is unified: it can be used for doubling as well.

For a mixed point addition (i.e., when $Z_2 = 1$), we have $m_3 = Z_1$ and the number of required multiplications drops to 10m. When used for dedicated doubling, the above addition formula requires 6m + 5s, which can equivalently be obtained as

$$
\begin{align}
s_1 &= X_1^2, \quad s_2 = Y_1^2, \quad s_3 = Z_1^2, \nonumber \\
s_4 &= (X_1 + Y_1)^2 - s_1 - s_2, \quad s_5 = (Y_1 + Z_1)^2 - s_2 - s_3, \tag{8.7} \\
X([2]\mathbf{P}_1) &= 2s_3s_4(s_2 + s_3), \quad Y([2]\mathbf{P}_1) = (s_1 - s_3)(s_3 - s_2)(s_3 + s_2), \nonumber \\
Z([2]\mathbf{P}_1) &= s_5(s_1 + s_3)(s_2 - s_3). \nonumber
\end{align}
$$

Note that the expression for the inverse of point $\mathbf{P}_1$ is unchanged: $\ominus'\mathbf{P}_1 = \ominus(\mathbf{P}_1 \ominus \mathbf{O}') \oplus \mathbf{O}' = \ominus\mathbf{P}_1 = (X_1 : Y_1 : -Z_1)$.

8.3.2 More formulas

Alternative addition formulas can be derived using the curve equation. For example,
whenever defined, we can write $(x_3, y_3) = (x_1, y_1) \oplus (x_2, y_2)$ with

$$
x_3 = \frac{(x_1 - x_2)(y_1 + y_2)}{(y_1 - y_2)(1 - x_1x_2)} \quad \text{and} \quad y_3 = \frac{(y_1 - y_2)(x_1 + x_2)}{(x_1 - x_2)(1 - y_1y_2)}.
$$

In projective coordinates, this gives

$$
\left\{
\begin{array}{l}
X_3 = (X_1 Z_2 - X_2 Z_1)^2 (Y_1 Z_2 + Y_2 Z_1) (Z_1 Z_2 - Y_1 Y_2) \\
Y_3 = (Y_1 Z_2 - Y_2 Z_1)^2 (X_1 Z_2 + X_2 Z_1) (Z_1 Z_2 - X_1 X_2) \\
Z_3 = (X_1 Z_2 - X_2 Z_1) (Y_1 Z_2 - Y_2 Z_1) (Z_1 Z_2 - X_1 X_2) (Z_1 Z_2 - Y_1 Y_2)
\end{array}
\right.
,
$$

which can be evaluated with 13m as

$$
\begin{align*}
m_1 &= X_1 Z_2, \quad m_2 = X_2 Z_1, \quad m_3 = Y_1 Z_2, \quad m_4 = Y_2 Z_1, \\
m_5 &= (Z_1 - X_1)(Z_2 + X_2) + m_1 - m_2, \quad m_6 = (Z_1 - Y_1)(Z_2 + Y_2) + m_3 - m_4, \\
m_7 &= (m_1 - m_2)m_6, \quad m_8 = (m_3 - m_4)m_5, \\
X_3 &= (m_1 - m_2)(m_3 + m_4)m_7, \quad Y_3 = (m_1 + m_2)(m_3 - m_4)m_8, \quad Z_3 = m_7 m_8.
\end{align*}
$$

Although not as efficient as the usual addition, this alternative formula is useful in some
pairing computations (see §8.4.2).
### 8.3.3 Twisted curves

As shown in Theorem 8.1, the group of points of a Huff elliptic curve contains a copy of $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$. This implies that the curve order is a multiple of 8. Several cryptographic standards, however, require elliptic curves with group order of the form $hn$ where $h \in \{1, 2, 3, 4\}$ and $n$ is a prime.

We can generalize Huff's model to accommodate the case $h = 4$. Let $P \in \mathbb{K}[t]$ denote a monic polynomial of degree 2, with non-zero discriminant, and such that $P(0) \neq 0$. We can then introduce the cubic curve

$$axP(y) = byP(x)$$

where $a, b \in \mathbb{K}^\times$. The set of points $\{(0:0:1), (0:1:0), (1:0:0), (a:b:0)\} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ belongs to the curve. Moreover, when $P$ factors in $\mathbb{K}$ — i.e., when $P(t) = (t - \omega_1)(t - \omega_2)$ with $\omega_1, \omega_2 \in \mathbb{K}^\times$, the four points $(\pm\omega_1 : \pm\omega_2 : 1)$ are also on the curve.

When $\mathbb{K} \neq 2$, we consider $P(t) = t^2 - d$ for some $d \in \mathbb{K}^\times$. So we deal with the set of projective points $(X:Y:Z) \in \mathbb{P}^2(\mathbb{K})$ satisfying the non-singular cubic equation

$$\hat{E}_d : aX(Y^2 - dZ^2) = bY(X^2 - dZ^2) \qquad (8.8)$$

where $a, b, d \in \mathbb{K}^\times$ and $a^2 \neq b^2$. This equation corresponds to Weierstrass equation $V^2W = U(U + \frac{a^2}{d}W)(U + \frac{b^2}{d}W)$ under the inverse transformations $(X:Y:Z) = (b(dU + a^2W):a(dU+b^2W):dV)$ and $(U:V:W) = (ab(bX-aY):ab(b^2-a^2)Z:d(-aX+bY))$. The transformation $(X:Y:Z) \leftarrow (X:Y:Z\sqrt{d})$ induces an isomorphism from $E = \hat{E}_1$ to $\hat{E}_d$ over $\mathbb{K}(\sqrt{d})$. Curves $\hat{E}_d$ are therefore quadratic twists of Huff curves.

In affine coordinates, we consider the curve equation $ax(y^2 - d) = by(x^2 - d)$. The sum of two finite points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ such that $x_1x_2 \neq \pm d$ and $y_1y_2 \neq \pm d$ is given by $(x_3, y_3)$ where

$$x_3 = \frac{d(x_1 + x_2)(d + y_1y_2)}{(d + x_1x_2)(d - y_1y_2)} \quad \text{and} \quad y_3 = \frac{d(y_1 + y_2)(d + x_1x_2)}{(d - x_1x_2)(d + y_1y_2)}. \qquad (8.9)$$

Extending the computations of § 8.2.2, it is readily verified that the sum of two points can be evaluated with $\mathfrak{12m}$ (plus a couple of multiplications by constant $d$) using projective coordinates. The faster computations of the previous section also generalize to twisted curves.

### 8.3.4 Binary fields

Huff's form can be extended to a binary field as

$$ax(y^2 + y + 1) = by(x^2 + x + 1).$$

This curve is birationally equivalent to Weierstrass curve

$$v(v + (a + b)u) = u(u + a^2)(u + b^2)$$
under the inverse maps

$$ (x, y) = \left( \frac{b(u + a^2)}{v}, \frac{a(u + b^2)}{v + (a + b)u} \right) \quad \text{and} \quad (u, v) = \left( \frac{ab}{xy}, \frac{ab(axy + b)}{x^2y} \right) . $$

The neutral element is $\mathbf{O} = (0, 0)$.

## 8.4 Pairings

### 8.4.1 Preliminaries

Let $(E, \mathbf{O})$ be an elliptic curve over $\mathbb{K} = \mathbb{F}_q$, with $q$ odd. Suppose that $\#E(\mathbb{F}_q) = hn$ where $n$ is a prime such that $\gcd(n, q) = 1$. Let further $k$ denote the embedding degree with respect to $n$, namely the smallest extension $\mathbb{F}_{q^k}$ of $\mathbb{F}_q$ containing all $n$-th roots of unity. In other words, $k$ is the smallest positive integer $k$ such that $n \mid q^k - 1$. For better efficiency, we further assume that $k > 1$ is even.

For any point $\mathbf{P} \in E(\mathbb{F}_q)[n]$, we let $f_{\mathbf{P}}$ denote a rational function on $E$ defined over $\mathbb{F}_q$ such that $\mathrm{div}(f_{\mathbf{P}}) = n\mathbf{P} - n\mathbf{O}$; it exists and is unique up to a multiplicative constant, according to the Riemann-Roch theorem. The group of $n$-th roots of unity in $\mathbb{F}_{q^k}$ is denoted by $\mu_n$. The (reduced) Tate pairing is then defined as

$$ T_n : E(\mathbb{F}_q)[n] \times E(\mathbb{F}_{q^k})/[n]E(\mathbb{F}_{q^k}) \to \mu_n : (\mathbf{P}, \mathbf{Q}) \mapsto f_{\mathbf{P}}(\mathbf{Q})^{(q^k-1)/n} . $$

This definition does not depend on the choice of $f_{\mathbf{P}}$ with the appropriate divisor, nor on the class of $\mathbf{Q}$ mod $[n]E(\mathbb{F}_{q^k})$.

In practice, $T_n$ can be computed using a technique due to Miller [Mil04], in terms of rational functions $g_{\mathbf{R},\mathbf{P}}$ depending on $\mathbf{P}$ and on a variable point $\mathbf{R}$. Function $g_{\mathbf{R},\mathbf{P}}$ is the so-called *line function* with divisor $\mathbf{R} + \mathbf{P} - \mathbf{O} - (\mathbf{R} \oplus \mathbf{P})$, which arises in addition formulas when $E$ is represented as a plane cubic. The core idea is to derive function $f_{\mathbf{P}}$ iteratively. Letting $f_{i,\mathbf{P}}$ be the function with divisor $\mathrm{div}(f_{i,\mathbf{P}}) = i\mathbf{P} - ([i]\mathbf{P}) - (i-1)\mathbf{O}$, it is easily verified that

$$ f_{i+j, \mathbf{P}} = f_{i, \mathbf{P}} \cdot f_{j, \mathbf{P}} \cdot g_{[i] \mathbf{P}, [j] \mathbf{P}} . $$

Observe that $f_{i,\mathbf{P}} = 1$ and $f_{n,\mathbf{P}} = f_{\mathbf{P}}$. Hence, if $n = \overline{n_{\ell-1}n_{\ell-1}\cdots n_{02}}$ is the binary representation of $n$, the Tate pairing can be computed as follows.

**Algorithm 8.1** Miller's algorithm.

1: $f \leftarrow 1$; $\mathbf{R} \leftarrow \mathbf{P}$

2: **for** $i = \ell - 2$ **down to** 0 **do**

3: $f \leftarrow f^2 \cdot g_{\mathbf{R},\mathbf{R}}(\mathbf{Q})$; $\mathbf{R} \leftarrow [2]\mathbf{R}$

4: **if** $(n_i = 1)$ **then**

5: $f \leftarrow f \cdot g_{\mathbf{R},\mathbf{P}}(\mathbf{Q})$; $\mathbf{R} \leftarrow \mathbf{R} \oplus \mathbf{P}$

6: **end if**

7: **end for**

8: **return** $f^{(q^k-1)/n}$
Contrary to Edwards curves or Jacobi quartics, Huff curves are represented as plane cubics. This makes Miller's algorithm, along with a number of improvements proposed for Weierstrass curves (e.g., as presented in [BLS04a]), directly applicable to the computation of pairings over Huff curves.

### 8.4.2 Pairing formulas for Huff curves

Throughout the for-loop of Algorithm 8.1, the line function is always evaluated at the same point $Q \in E(\mathbb{F}_{q^k}) \setminus E(\mathbb{F}_q)$. It is therefore customary to represent this point in affine coordinates. In our case, it is most convenient to choose the coordinates of $Q$ as $Q = (y, z) = (1 : y : z)$. Indeed, since the embedding degree $k$ is even, the field $\mathbb{F}_{q^k}$ can be represented as $\mathbb{F}_{q^{k/2}}(\alpha)$, where $\alpha$ is any quadratic non-residue in $\mathbb{F}_{q^{k/2}}$. As a result, $Q$ can be chosen of the form $Q = (y_Q, z_Q\alpha)$ with $y_Q, z_Q \in \mathbb{F}_{q^{k/2}}$ [BLS03]. To do so, it suffices to pick a point on a quadratic twist of $E$ over $\mathbb{F}_{q^{k/2}}$ and take its image under the isomorphism over $\mathbb{F}_{q^k}$.

Now, for any two points $\mathbf{R}, \mathbf{P}$ in $E(\mathbb{F}_q)$, let $\ell_{\mathbf{R},\mathbf{P}}$ denote the rational function vanishing on the line through $\mathbf{R}$ and $\mathbf{P}$. In general, we have

$$ \ell_{\mathbf{R},\mathbf{P}}(\mathbf{Q}) = \frac{(zX_{\mathbf{P}} - Z_{\mathbf{P}}) - \lambda(yX_{\mathbf{P}} - Y_{\mathbf{P}})}{Y_{\mathbf{P}}} $$

where $\lambda$ is the “$(y, z)$-slope” of the line through $\mathbf{R}$ and $\mathbf{P}$. Then, the divisor of $\ell_{\mathbf{R},\mathbf{P}}$ is

$$ \mathrm{div}(\ell_{\mathbf{R},\mathbf{P}}) = \mathbf{R} + \mathbf{P} + \mathbf{T} - (1:0:0) - (0:1:0) - (a:b:0) $$

where $\mathbf{T}$ is the third point of intersection (counting multiplicities) of the line through $\mathbf{R}$ and $\mathbf{P}$ with the elliptic curve. In particular, if the neutral element of the group law $\oplus$ is denoted by $\mathbf{U}$, the line function $g_{\mathbf{R},\mathbf{P}}$ can be written as

$$ g_{\mathbf{R},\mathbf{P}} = \frac{\ell_{\mathbf{R},\mathbf{P}}}{\ell_{\mathbf{R}\oplus\mathbf{P},\mathbf{U}}} $$

We concentrate on the case when $\mathbf{U} = \mathbf{O} = (0:0:1)$. Then for any $\mathbf{Q} = (y_{\mathbf{Q}}, z_{\mathbf{Q}}\alpha)$, we have

$$ \ell_{\mathbf{R}\oplus\mathbf{P},\mathbf{O}}(\mathbf{Q}) = y_{\mathbf{Q}} - \frac{Y_{\mathbf{R}\oplus\mathbf{P}}}{X_{\mathbf{R}\oplus\mathbf{P}}} \in \mathbb{F}_{q^{k/2}}. $$

Since this quantity lies in a proper subfield of $\mathbb{F}_{q^k}$, it goes to 1 after the final exponentiation in Miller's algorithm, which means that it can be discarded altogether. Similarly, divisions by $X_{\mathbf{P}}$ can be omitted, and denominators in the expression of $\lambda$ can be canceled. In other words, if $\lambda = A/B$, we can compute the line function as

$$ g_{\mathbf{R},\mathbf{P}}(\mathbf{Q}) = (zX_{\mathbf{P}} - Z_{\mathbf{P}}) \cdot B - (yX_{\mathbf{P}} - Y_{\mathbf{P}}) \cdot A $$

and get the required result.

We can now detail precise formulas for the addition and doubling steps in the so-called Miller loop (i.e., the main for-loop in Algorithm 8.1). We let $\mathbf{M}$ and $\mathbf{S}$ represent the cost of a multiplication and of a squaring in $\mathbb{F}_{q^k}$ while $\mathbf{m}$ and $\mathbf{s}$ are operations in $\mathbb{F}_q$ as before.
**Addition step.** In the case of addition, the $(y, z)$-slope of the line through $\mathbf{R} = (X_R : Y_R : Z_R)$ and $\mathbf{P} = (X_P : Y_P : Z_P)$ is

$$ \lambda = \frac{Z_{\mathbf{R}}X_{\mathbf{P}} - Z_{\mathbf{P}}X_{\mathbf{R}}}{Y_{\mathbf{R}}X_{\mathbf{P}} - Y_{\mathbf{P}}X_{\mathbf{R}}}. $$

Therefore, the line function to be evaluated is of the form

$$ g_{\mathbf{R},\mathbf{P}}(\mathbf{Q}) = (z_{\mathbf{Q}}\alpha \cdot X_{\mathbf{P}} - Z_{\mathbf{P}})(Y_{\mathbf{R}}X_{\mathbf{P}} - Y_{\mathbf{P}}X_{\mathbf{R}}) - (y_{\mathbf{Q}} \cdot X_{\mathbf{P}} - Y_{\mathbf{P}})(Z_{\mathbf{R}}X_{\mathbf{P}} - Z_{\mathbf{P}}X_{\mathbf{R}}). $$

Since $\mathbf{P}$ and $\mathbf{Q}$ are constant throughout the loop, the values depending only on $\mathbf{P}$ and $\mathbf{Q}$ — in this case $y'_{\mathbf{Q}} = y_{\mathbf{Q}} \cdot X_{\mathbf{P}} - Y_{\mathbf{P}}$ and $z'_{\mathbf{Q}} = z_{\mathbf{Q}}\alpha \cdot X_{\mathbf{P}}$, can be precomputed.

Then, each Miller addition step requires computing $\mathbf{R} \oplus \mathbf{P}$ (one addition on the curve over $\mathbb{F}_q$), evaluating $g_{\mathbf{R},\mathbf{P}}(\mathbf{Q})$, and computing $f \cdot g_{\mathbf{R},\mathbf{P}}(\mathbf{Q})$ (one multiplication in the field $\mathbb{F}_{q^k}$).

We consider two types of Miller addition steps: full addition, for which no assumption is made on the representation of $\mathbf{P}$, and mixed addition, for which we further assume that $\mathbf{P}$ is given in affine coordinates (i.e., $X_{\mathbf{P}} = 1$). Both steps start with computing $\mathbf{R} \oplus \mathbf{P}$, including all intermediate results.

**Full addition.** Computing $\mathbf{R} \oplus \mathbf{P}$ requires 13m using the dedicated addition formula from §8.3.1, including all intermediate results $m_1, \dots, m_8$. Compute further $m_9 = (X_{\mathbf{R}} + Y_{\mathbf{R}})(X_{\mathbf{P}} - Y_{\mathbf{P}})$. We then have

$$ g_{\mathbf{R},\mathbf{P}}(\mathbf{Q}) = (z'_{\mathbf{Q}} - Z_{\mathbf{P}})(m_9 + m_5 - m_6) - y'_{\mathbf{Q}}(m_1 - m_2) $$

where the first term requires $(\frac{k}{2} + 1)m$ and the second term $\frac{k}{2}m$. With the final multiplication over $\mathbb{F}_{q^k}$, the total cost of full addition is thus of $1M + (k + 15)m$.

**Mixed addition.** Now that $X_{\mathbf{P}} = 1$, computing $\mathbf{R} \oplus \mathbf{P}$ using the formula from §8.2.2, including all the intermediate results $m_1, \dots, m_9$, only requires 11m, since the computation of $m_1$ is free. We then have

$$ g_{\mathbf{R},\mathbf{P}}(\mathbf{Q}) = (z'_{\mathbf{Q}} - Z_{\mathbf{P}})(Y_{\mathbf{R}} - Y_{\mathbf{P}}X_{\mathbf{R}}) - y'_{\mathbf{Q}}(2Z_{\mathbf{R}} - m_4) $$

where both terms require the same number of multiplications as before, plus one for $Y_{\mathbf{P}}X_{\mathbf{R}}$. The total cost of mixed addition is thus of $1M + (k + 13)m$.

**Doubling step.** In the case of doubling, the $(y, z)$-slope of the tangent line at $\mathbf{R} = (X_R : Y_R : Z_R)$ is

$$ \lambda = \frac{a(Z_{\mathbf{R}})^2 - 2bY_{\mathbf{R}}Z_{\mathbf{R}} - a(X_{\mathbf{R}})^2}{b(Y_{\mathbf{R}})^2 - 2aY_{\mathbf{R}}Z_{\mathbf{R}} - b(X_{\mathbf{R}})^2} = \frac{A}{B}. $$

Thus, the line function is of the form

$$ g_{\mathbf{R},\mathbf{R}}(\mathbf{Q}) = z_{\mathbf{Q}}\alpha \cdot X_{\mathbf{R}}B - Z_{\mathbf{R}}B - y_{\mathbf{Q}} \cdot X_{\mathbf{R}}A + Y_{\mathbf{R}}A. $$
Miller's doubling involves computing the point $[2]R$, which we do using the formulas from §8.2.2 in 7m + 5s. Then the quantities $A$ and $B$ are obtained by computing the additional product $m_{10} = 2Y_RZ_R = (Y_R + Z_R)^2 - m_2 - m_3$ using a single squaring. Computing $g_{R,R}(Q)$ requires multiplying those two values by $X_R$ and $Y_R$ (resp. $X_R$ and $Z_R$), hence an additional 4m. And finally, multiplications by $y_Q$ and $z_Q\alpha$ both require $\frac{k}{2}$m. Taking into account the multiplication and the squaring in $\mathbb{F}_{q^k}$ needed to complete the doubling step, the total cost of Miller doubling is thus of $\underline{1M + 1S + (k+11)m + 6s}$.

**8.5 Conclusion and Perspectives**

This work introduced and studied Huff's model, a representation of elliptic curves to be considered alongside previous models such as Montgomery, Doche-Icart-Kohel and Edwards. This model provides efficient arithmetic, competitive with some of the fastest known implementations (although not quite as fast as "inverted Edwards" for now). Moreover, it has a number of additional desirable properties, including unified/complete addition laws and formulas that do not depend on curve parameters (both properties are useful in cryptographic applications to thwart certain implementation attacks). It is also suitable to other computations on elliptic curves, such as the evaluation of pairings.

Binary Huff curves, as introduced in §8.3.4, have been studied further by Devigne and Joye [DJ11]. They have proposed very efficient addition and doubling formulas, making Huff's model currently the most efficient representation for elliptic curve arithmetic in characteristic 2.

Additionally, further generalizations of Huff's model have been suggested in odd characteristic by Wu and Feng [WF10].
<figure><img src="image_16.png" /></figure>
# Cryptanalysis of RSA-based Schemes

## Overview

A year after the discovery of public-key cryptography by Diffie and Hellman in 1976 [Hel76], Rivest, Shamir and Adleman proposed the first example of a public-key cryptosystem [RSA78], which became known as RSA. Nowadays, the most widely used public-key cryptographic schemes, both for encryption and signature, are based on RSA and deployed in many everyday applications, from payment cards to secure web servers and virtual private networks.

Since its inception, the RSA function itself and the cryptographic protocols based on it have received a lot of attention from many researchers, and a number of attacks and vulnerabilities have been discovered, though, in the words of Boneh [Bon99], “none of them [were] devastating” for RSA-based cryptography at large. Rather, this large body of cryptanalytic work has shaped our understanding of the “proper way” to use the RSA function in cryptographic protocols, and underscored the dangers of incautious uses. It has also uncovered exploitable flaws in widespread systems and caused widely deployed standards to be withdrawn, but RSA as a whole remains robust.

Many different types of attacks have been considered. Here are a few examples.

**Factoring algorithms:** the most direct way to break RSA cryptosystems is certainly to factor the public modulus. As a result, there has arguably been more progress on the millennia-old problem of factoring integers in the last three decades than ever before. The recent factorization of the RSA-768 challenge modulus [KAF+10] using the General Number Field Sieve (GNFS) [LJMP90, LL93], as developed by Adleman, Buhler, Lenstra, Pollard, Pomerance and others, puts in perspective the prediction by Martin Gardner in 1977 that his proposed 129-digit (426-bit) RSA modulus would be safe for 40 quadrillion years!

**The RSA problem:** while it not known whether a random instance of the RSA problem
is equivalent to factoring, some instances are known to be weaker. For example, Wiener [Wie90] observed that given an RSA public key (N, e), it is possible to factor N efficiently, and hence solve RSA, when the private exponent $d \equiv 1/e \pmod N$ is small ($d < (1/3) \cdot N^{1/4}$, a bound which was later improved to $d < N^{0.292}$ by Boneh and Durfee [BD00] using techniques introduced by Coppersmith [Cop97]). On a different note, the best known attack on the “one more RSA” problem, by Joux, Naccache and Thomé [JNT07], has a better heuristic asymptotic complexity than GNFS.

**Special attack models:** for example, even if the RSA problem is hard, RSA encryption may not remain one-way when the same message is encrypted for several different recipients. Clearly, if the same message is encrypted with the same small public exponent *e* to more than *e* recipients with textbook RSA encryption, an eavesdropping adversary can recover the message using a simple application of the Chinese Remainder Theorem. A similar but more sophisticated attack in this so-call *broadcast* model was proposed by Håstad [Hås88], who showed that if what is encrypted is not the message itself but a polynomial function of it different for all recipients, it is still possible to recover it.

**Stronger security notions:** the one-wayness of textbook RSA encryption under chosen-plaintext attack and the universal unforgeability of textbook RSA signatures under key-only attack are both equivalent to the RSA problem, but these are relatively weak security notions that do not capture such simple flaws as the *blinding attacks* deriving from the homomorphic properties of the RSA function. Many *padding* methods were proposed early on to thwart those simple attacks, but they usually did not come with clearly stated security guarantees, and many publications exhibited vulnerabilities in those *ad-hoc* schemes, such as [CCG+08, JNT07, CJNP00, Gri00]. Additionally, attacks like that of Bleichenbacher against SSL [Ble98] made it clear that strong security notions like CCA-security were not just purely theoretical constructs, as some may have believed at the time, but actually mattered in applications too.

**Physical attacks:** as embedded cryptographic devices such as smart cards became more common, it was observed that a real-world adversary does not interact with a mathematical algorithm in a black-box way, but can gain information from observing the physical process of the computation and from tampering with it. Key-recovery attacks on physical implementations of RSA, in particular, have been an active research area since the seminal timing and DPA attacks by Kocher et al. [Koc96, KJJ99] and the fault attacks of Boneh, DeMillo and Lipton [BDL01].

This part of the thesis is devoted to various contributions to the vast research area that is RSA cryptanalysis. Those contributions include several different “types” of attacks, and use different mathematical techniques. Chapter 9 describes the implementation of an existential forgery attack on the ad-hoc RSA signature paddings ISO/IEC 9796-2 [ISO9796-2:2002] and EMV [EMV], using sieving techniques reminiscent of algorithms
such as the quadratic sieve and index calculus. Chapters 10–11 present fault attacks on implementations of RSA signatures that use the Chinese Remainder Theorem; our main technical tool in the orthogonal lattice technique of Nguyen and Stern [NS97]. Chapter 12 describes new attacks on the ad-hoc RSA encryption padding PKCS#1 v1.5 [PKCS#1 v1.5], some of which are similar to Bleichenbacher’s attack [Ble98], while others consider a broadcast model à la Håstad [Hås88] and are based on generalizations of the techniques of Coppersmith [Cop97]. Finally, Chapter 13 shows that certain RSA moduli of a special form introduced by Groth in [Gro05] can be factored faster than he suggested, making his proposed choice of parameters potentially insecure.
<figure><img src="image_17.png" /></figure>
# Contents

## 9 Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures

<table><tr><td>9.1 Introduction</td><td>149</td></tr><tr><td>9.1.1 Ad-hoc vs. provable RSA paddings</td><td>149</td></tr><tr><td>9.1.2 The ISO/IEC 9796-2 encoding</td><td>150</td></tr><tr><td>9.1.3 Our contribution</td><td>151</td></tr><tr><td>9.2 The ISO/IEC 9796-2 Standard</td><td>151</td></tr><tr><td>9.3 Previous Attacks</td><td>152</td></tr><tr><td>9.3.1 The Desmedt-Odlyzko forgery</td><td>152</td></tr><tr><td>9.3.2 The Coron-Naccache-Stern forgery</td><td>153</td></tr><tr><td>9.4 Building Blocks of the New Attack</td><td>155</td></tr><tr><td>9.4.1 Bernstein's smoothness detection algorithm</td><td>155</td></tr><tr><td>9.4.2 The large prime variant</td><td>156</td></tr><tr><td>9.4.3 Constructing smaller a &middot; &mu;(m) &minus; b &middot; N candidates</td><td>156</td></tr><tr><td>9.5 Attacking ISO/IEC 9796-2</td><td>157</td></tr><tr><td>9.5.1 The Amazon cloud</td><td>157</td></tr><tr><td>9.5.2 The experiment: Outline, details and results</td><td>158</td></tr><tr><td>9.6 Cost Estimates</td><td>160</td></tr><tr><td>9.7 Application to EMV Signatures</td><td>162</td></tr><tr><td>9.7.1 EMV Static Data Authentication, Issuer Public Key Data (SDA-IPKD)</td><td>162</td></tr><tr><td>9.7.2 Attacking SDA-IPKD</td><td>162</td></tr><tr><td>9.7.3 Summary</td><td>164</td></tr><tr><td>9.8 Conclusion</td><td>164</td></tr><tr><td>9.A Optimizing Bernstein's Batch Size</td><td>165</td></tr><tr><td>9.B Large Prime Variant: Complexity Analysis</td><td>166</td></tr></table>
TABLE OF CONTENTS

<table><tr><td>9.C</td><td>LLL Attack on EMV SDA-IPKD Encoding</td><td>167</td></tr><tr><td>9.C.1</td><td>The LLL attack</td><td>167</td></tr><tr><td>9.C.2</td><td>Practical value for EMV SDA-IPKD</td><td>168</td></tr><tr><td>9.D</td><td>EMV Signature Encoding Formats</td><td>169</td></tr><tr><td>9.E</td><td>Fewer Queries</td><td>170</td></tr><tr><td>9.F</td><td>Expected Number of Queries</td><td>171</td></tr></table>

10 Fault Attacks on EMV Signatures

<table><tr><td>10.1</td><td>Introduction</td><td>175</td></tr><tr><td>10.1.1</td><td>Fault attacks on RSA-CRT</td><td>176</td></tr><tr><td>10.1.2</td><td>The attack of Coron et al.</td><td>176</td></tr><tr><td>10.1.3</td><td>Our contribution</td><td>177</td></tr><tr><td>10.1.4</td><td>Outline</td><td>177</td></tr><tr><td>10.2</td><td>Preliminaries on Lattices</td><td>178</td></tr><tr><td>10.2.1</td><td>Notation and background</td><td>178</td></tr><tr><td>10.2.2</td><td>Lattices and lattice bases</td><td>178</td></tr><tr><td>10.2.3</td><td>Lattice volume</td><td>179</td></tr><tr><td>10.2.4</td><td>Lattice reduction</td><td>180</td></tr><tr><td>10.3</td><td>Modeling Faults on ISO/IEC 9796-2 Signatures</td><td>182</td></tr><tr><td>10.3.1</td><td>The ISO/IEC 9796-2 signature scheme</td><td>182</td></tr><tr><td>10.3.2</td><td>Attack model</td><td>183</td></tr><tr><td>10.4</td><td>The Small Root Attack</td><td>183</td></tr><tr><td>10.4.1</td><td>Single-fault attack</td><td>184</td></tr><tr><td>10.4.2</td><td>Extension to several faults</td><td>184</td></tr><tr><td>10.5</td><td>Our New Multiple-Fault Attack</td><td>185</td></tr><tr><td>10.6</td><td>Simulation Results</td><td>187</td></tr><tr><td>10.7</td><td>Application to EMV Signatures</td><td>188</td></tr><tr><td>10.7.1</td><td>The EMV specification</td><td>188</td></tr><tr><td>10.7.2</td><td>Fault attack</td><td>189</td></tr><tr><td>10.8</td><td>Proposed Countermeasures</td><td>190</td></tr></table>
## 11 Modulus Fault Attacks Against RSA-CRT Signatures

<table><tr><td>11.1 Introduction</td><td>191</td></tr><tr><td>11.1.1 Fault attacks on RSA-CRT signatures</td><td>191</td></tr><tr><td>11.1.2 Our contribution</td><td>192</td></tr><tr><td>11.1.3 Related work</td><td>193</td></tr><tr><td>11.1.4 Outline</td><td>193</td></tr><tr><td>11.2 The New Attack</td><td>193</td></tr><tr><td>11.2.1 Overview</td><td>193</td></tr><tr><td>11.2.2 Applying orthogonal lattice techniques</td><td>194</td></tr><tr><td>11.2.3 Attack summary</td><td>195</td></tr><tr><td>11.2.4 Simulation results</td><td>196</td></tr><tr><td>11.3 Extending the Attack to Unknown Faulty Moduli</td><td>196</td></tr><tr><td>11.3.1 Single byte faults</td><td>197</td></tr><tr><td>11.3.2 Faults on many least significant bits</td><td>198</td></tr><tr><td>11.4 Practical Experiments</td><td>200</td></tr><tr><td>11.4.1 First scenario: Known modulus</td><td>200</td></tr><tr><td>11.4.2 Second scenario: Unknown single byte faults</td><td>201</td></tr><tr><td>11.4.3 Third scenario: Least significant bytes faults</td><td>201</td></tr><tr><td>11.5 Countermeasures and Further Research</td><td>202</td></tr><tr><td>11.A Laser Fault Injection</td><td>202</td></tr><tr><td>11.A.1 Photoelectric effects of laser on silicon</td><td>203</td></tr><tr><td>11.A.2 Different parameters in a fault attack by laser</td><td>203</td></tr><tr><td>11.A.3 Practical CRT fault injection</td><td>204</td></tr></table>

## 12 On the Security of PKCS#1 v1.5 Encryption

<table><tr><td>12.1 Introduction</td><td>209</td></tr><tr><td>12.1.1 The PKCS#1 v1.5 standard</td><td>209</td></tr><tr><td>12.1.2 Our results</td><td>210</td></tr><tr><td>12.2 Preliminaries</td><td>210</td></tr><tr><td>12.2.1 Public-key encryption</td><td>210</td></tr><tr><td>12.2.2 Security definitions</td><td>211</td></tr><tr><td>12.2.3 RSA security</td><td>212</td></tr><tr><td>12.3 PKCS#1 v1.5 Encryption</td><td>213</td></tr><tr><td></td><td>147</td></tr></table>
TABLE OF CONTENTS

<table><tr><td>12.3.1 The PKCS#1 v1.5 encoding function</td><td>213</td></tr><tr><td>12.3.2 Previous attacks on PKCS#1 v1.5</td><td>213</td></tr><tr><td>12.4 On the OW-CPA-Security of PKCS#1 v1.5</td><td>214</td></tr><tr><td>12.5 PKCS#1 v1.5 Malleability and Indistinguishability</td><td>216</td></tr><tr><td>12.5.1 On the NM-CPA-security of PKCS#1 v1.5</td><td>216</td></tr><tr><td>12.5.2 On the IND-VCA-security of PKCS#1 v1.5</td><td>217</td></tr><tr><td>12.6 Broadcast Attack on PKCS#1 v1.5</td><td>219</td></tr><tr><td>12.6.1 The multivariate polynomial of broadcast PKCS#1 v1.5</td><td>220</td></tr><tr><td>12.6.2 Finding small modular roots of a multivariate polynomial</td><td>221</td></tr><tr><td>12.6.3 The Jochemsz-May lattice in broadcast PKCS#1 v1.5</td><td>223</td></tr><tr><td>12.6.4 Experimental results on the broadcast attack</td><td>225</td></tr><tr><td>12.7 Conclusion</td><td>226</td></tr></table>

13 Cryptanalysis of the RSA Subgroup Assumption

<table><tr><td>13.1 Introduction</td><td>229</td></tr><tr><td>13.1.1 Groth's small RSA subgroups</td><td>229</td></tr><tr><td>13.1.2 Our results</td><td>230</td></tr><tr><td>13.2 The New Attack</td><td>230</td></tr><tr><td>13.3 Attack Complexity</td><td>231</td></tr><tr><td>13.4 Algorithmic Details</td><td>232</td></tr><tr><td>13.5 Implementation</td><td>233</td></tr><tr><td>13.6 Conclusion</td><td>235</td></tr><tr><td>13.A Bostan's Algorithms</td><td>236</td></tr><tr><td>13.B Source Code of the Attack</td><td>237</td></tr></table>
# Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures

## 9.1 Introduction

In 1999, Coron, Naccache and Stern [CNS99] discovered an existential signature forgery attack against two popular RSA signature standards, ISO/IEC 9796-1 [ISO9796-1] and ISO/IEC 9796-2 [ISO9796-2]. Following that attack, ISO/IEC 9796-1 was withdrawn and ISO/IEC 9796-2 was amended by imposing higher parameter size requirements that make Coron et al.'s attack infeasible in practice.

In this chapter, we describe a number of algorithmic improvements for the attack by Coron, Naccache and Stern, which provide a speed-up of several orders of magnitude and make it possible to attack the amended version of ISO/IEC 9796-2 [ISO9796-2:2002]. With these improvements, we were able to actually implement the attack on the Amazon EC2 cloud, and obtain a forgery in two days for a total cost of about US$800.

In response to this new attack, the ISO/IEC 9796-2 standard was amended again in late 2010 [ISO9796-2:2010].

Our algorithmic improvements also apply to attacking RSA signatures following the EMV banking industry specifications, which are based on ISO/IEC 9796-2 but in a more constrained format. We estimate that an EMV forgery would cost around US$45,000 on Amazon EC2.

This work was presented at CRYPTO 2009 [CNTW09].

### 9.1.1 Ad-hoc vs. provable RSA paddings

RSA [RSA78] is the first, and certainly the most popular public-key cryptosystem, both for encryption and signature. However, it has long been known that, in its textbook form, it has a number of security flaws, due in particular to its homomorphic properties.
For example, if two messages $m_1, m_2$ are signed with textbook RSA:

$$ \sigma_1 = m_1^d \mod N $$

$$ \sigma_2 = m_2^d \mod N $$

then $(\sigma_1 \cdot \sigma_2) \mod N$ is a valid signature on $m_1 \cdot m_2$, which shows that textbook RSA signature is not unforgeable under chosen message attack.

As a result, to actually sign or encrypt with RSA, it is necessary to first “pad” the message using a certain encoding function $\mu$ before actually applying the RSA exponentiation. Thus, an RSA signature is really computed as:

$$ \sigma = \mu(m)^d \mod N. $$

We can roughly divide the RSA encoding functions $\mu$ in use nowadays in two categories:

*Ad-hoc encodings* are “handcrafted” to thwart certain classes of attacks. While still in use, ad-hoc encodings are now being phased out. PKCS#1 v1.5 [PKCS#1 v1.5], ISO/IEC 9796-1 [ISO9796-1] and ISO/IEC 9796-2 [ISO9796-2, ISO9796-2:2002] are typical examples of such encodings.

*Provably secure encodings* are designed to make cryptanalysis equivalent to inverting RSA (possibly in somewhat idealized attack models such as the Random Oracle Model [BR93]). OAEP [BR94] (for encryption) and PSS [BR96] (for signature) are typical examples of provably secure encodings.

For *ad-hoc encodings*, there is no guarantee that forging signatures is as hard as inverting RSA. And as a matter of fact, many such encodings were found to be weaker than the RSA problem. We refer the reader to [Ble98, CCG+08, JNT07, CJNP00, Gri00] for a few typical examples. It is thus a practitioner’s rule of thumb to use provably secure encodings whenever possible. Nevertheless, ad-hoc encodings remain in widespread use in many commercial products (such as EMV payment cards). A periodic re-evaluation of such encodings is thus necessary.

### 9.1.2 The ISO/IEC 9796-2 encoding

ISO/IEC 9796-2 is an international standard that defines a specific, add-hoc encoding function for RSA signatures [ISO9796-2]. In [CNS99], Coron, Naccache and Stern discovered an attack against it that led to a revision of the standard.

More precisely, ISO/IEC 9796-2 can be used with hash functions of various digest sizes $k_h$. Originally, ISO/IEC 9796-2 recommended $128 \le k_h \le 160$, but $k_h = 128$ was within reach of the attack by Coron et al., so the standard was amended and the official requirement became $k_h \ge 160$ [ISO9796-2:2002].

The attack by Coron et al. is based on an earlier cryptanalytic result by Desmedt and Odlyzko [DO85], which was first presented as a chosen-ciphertext attack on RSA encryption, but applies to RSA signatures as well, as noted in [Mis98], provided that
the encoding function $\mu$ maps to integers of small size (much smaller than the modulus $N$). The ISO/IEC 9796-2 encoding itself does not satisfy this requirement (it maps to integers to full size), but Coron et al. showed that the Desmedt-Odlyzko attack can be adapted to this setting nonetheless.

### 9.1.3 Our contribution

In this chapter, we describe an improved attack against the amended version of ISO/IEC 9796-2, with $k_h = 160$. The new attack applies to EMV signatures as well, which are ISO/IEC 9796-2-compliant signatures with extra redundancy.

Our attack is based on the same idea as Coron et al.'s forgery, with a number of algorithmic refinements: a more careful choice of queried messages, a more efficient algorithm due to Bernstein for detecting smooth integers, the use of "large primes" as is common in modern implementations of the quadratic and number field sieves, and an optimized exhaustive search.

Using these refinements, we were able to compute an ISO/IEC 9796-2 forgery in two days on a few dozen nodes of the Amazon EC2 cloud, for a total cost of US$800. The forgery was implemented for public exponent $e = 2$ but attacking odd exponents would not take significantly longer<fnref n="1" />. We estimate that under similar conditions an EMV signature forgery would cost US$45,000. Note that all costs are per modulus. After computing a first forgery for a given $N$, additional forgeries come at a negligible cost.

## 9.2 The ISO/IEC 9796-2 Standard

ISO/IEC 9796-2 is an standard for RSA signatures that defines RSA encoding functions allowing partial or total message recovery [ISO9796-2, ISO9796-2:2002]. Here we consider only partial message recovery. As we have already mentioned, ISO/IEC 9796-2 can be used with hash functions $H(m)$ of various output sizes $k_h$. For the sake of simplicity we assume that $k_h$, the size of $m$ and the size of $N$ (denoted $k$) are all multiples of 8;<fnref n="2" /> this is also the case in the EMV specifications. Then, the ISO/IEC 9796-2 encoding function has the following form:

$$ \mu(m) = 6A_{16} \|m[1]\| H(m) \|BC_{16} $$

where the message $m = m[1] \|m[2]$ is split in two: $m[1]$ consists of the $k - k_h - 16$ leftmost bits of $m$ and $m[2]$ represents all the remaining bits of $m$. The size of $\mu(m)$ is therefore always $k - 1$ bits.

<footnote n="1">¹It might slow down the final linear algebra stage of the attack somewhat, as sparse linear algebra in characteristic 2 can benefit from some bit fiddling optimizations on typical CPU architectures, but the linear algebra stage only takes a very small fraction of the overall CPU time anyway.</footnote>

<footnote n="2">²As will be clarified later, if we drop the assumption that $k \equiv 0 \mod 8$, the attack actually becomes faster. Indeed, if $m$ consists of an odd number of 4-bit nibbles, the encoding function becomes $\mu(m) = 7_{16} \|m[1]\| H(m) \|BC_{16}$, with only 12 fixed bits instead of 16, which in turn makes the involved integers about 4 bits shorter. For example, the RSA-2048 {a, b}-pair (see §9.4.3) becomes {45, 28} instead of {625, 332}.</footnote>
The original version of the standard recommended $128 \le k_h \le 160$ for partial message recovery (see [ISO9796-2], §5, note 4). The amended versions of ISO/IEC 9796-2 [ISO9796-2:2002, ISO9796-2:2010] require $k_h \ge 160$. The EMV specifications also use $k_h = 160$.

Note that newer versions of ISO/IEC 9796-2 [ISO9796-2:2002, ISO9796-2:2010] also define and recommend a different encoding function known as ISO/IEC 9796-2 mode 3, which is essentially a deterministic variant of PSS-R [PKCS#1 v2.1]. This encoding function does not suffer from the vulnerabilities described in this chapter. However, its adoption and deployment remain unclear.

## 9.3 Previous Attacks

### 9.3.1 The Desmedt-Odlyzko forgery

In Desmedt and Odlyzko's attack [Mis98] (existential forgery under a chosen-message attack), the forger asks for the signature of messages of his choice before computing, by his own means, the signature of a (possibly meaningless) message that was never signed by the legitimate owner the signing key.

The attack only applies if $\mu(m)$ is much smaller than $N$ and works as follows:

1. Select a bound $B$ and let $\mathfrak{P} = \{p_1, \dots, p_\ell\}$ be the list of all primes smaller than $B$.

2. Find $\tau \ge \ell + 1$ messages $m_i$ such that each $\mu(m_i)$ is a product of primes in $\mathfrak{P}$.

3. Express one $\mu(m_j)$ as a multiplicative combination of the other $\mu(m_i)$'s, by solving a linear system given by the exponent vectors of the $\mu(m_i)$ with respect to the primes in $\mathfrak{P}$.

4. Ask for the signatures of the $m_i$ for $i \ne j$ and forge the signature of $m_j$.

In the following we assume that $e$ is prime; this includes $e = 2$. We say that an integer is $B$-smooth if all its prime factors are smaller than $B$. The integers $\mu(m_i)$ obtained at step 2 are therefore $B$-smooth and we can write for all messages $m_i$, $1 \le i \le \tau$:

$$ \mu(m_i) = \prod_{j=1}^{\ell} p_j^{v_{i,j}}. \qquad (9.1) $$

To each $\mu(m_i)$ we associate the $\ell$-dimensional vector of the exponents modulo $e$:

$$ \mathbf{V}_i = (v_{i,1} \bmod e, \dots, v_{i,\ell} \bmod e). $$

Since $e$ is prime, the set of all $\ell$-dimensional vectors modulo $e$ forms a linear space of dimension $\ell$. Therefore, since $\tau \ge \ell + 1$, one can express one vector, say $\mathbf{V}_\tau$, as a linear combination of the others modulo $e$, which gives for $1 \le j \le \ell$:

$$ \mathbf{V}_\tau = \mathbf{\Gamma} \cdot e + \sum_{i=1}^{\tau-1} \beta_i \mathbf{V}_i $$
for some $\Gamma = (\gamma_1, \dots, \gamma_\ell) \in \mathbb{Z}^\ell$. That is,

$$v_{\tau,j} = \gamma_j \cdot e + \sum_{i=1}^{\tau-1} \beta_i \cdot v_{i,j}.$$

Then using (9.1), one obtains:

$$\mu(m_{\tau}) = \prod_{j=1}^{\ell} p_{j}^{v_{\tau,j}} = \prod_{j=1}^{\ell} p_{j}^{\gamma_{j} \cdot e + \sum_{i=1}^{\tau-1} \beta_{i} \cdot v_{i,j}} = \left( \prod_{j=1}^{\ell} p_{j}^{\gamma_{j}} \right)^{e} \cdot \prod_{j=1}^{\ell} \prod_{i=1}^{\tau-1} p_{j}^{v_{i,j} \cdot \beta_{i}}$$

$$\mu(m_{\tau}) = \left( \prod_{j=1}^{\ell} p_{j}^{\gamma_{j}} \right)^{e} \cdot \prod_{i=1}^{\tau-1} \left( \prod_{j=1}^{\ell} p_{j}^{v_{i,j}} \right)^{\beta_{i}} = \left( \prod_{j=1}^{\ell} p_{j}^{\gamma_{j}} \right)^{e} \cdot \prod_{i=1}^{\tau-1} \mu(m_{i})^{\beta_{i}}.$$

That is:

$$\mu(m_{\tau}) = \delta^{e} \cdot \prod_{i=1}^{\tau-1} \mu(m_{i})^{\beta_{i}}, \quad \text{where we let} \quad \delta = \prod_{j=1}^{\ell} p_{j}^{\gamma_{j}}. \qquad (9.2)$$

Therefore, we see that $\mu(m_{\tau})$ can be written as a multiplicative combination of the other $\mu(m_i)$. To produce a forgery, the attacker will ask for the signatures of $m_1, \dots, m_{\tau-1}$ and output the following valid signature on $m_{\tau}$:

$$\sigma_{\tau} = \mu(m_{\tau})^{d} = \delta \cdot \prod_{i=1}^{\tau-1} (\mu(m_{i})^{d})^{\beta_{i}} = \delta \cdot \prod_{i=1}^{\tau-1} \sigma_{i}^{\beta_{i}} \quad \text{mod } N.$$

Note that when $e=2$, one uses with Rabin-Williams signatures rather than RSA signatures, and an additional component in the vectors $V_i$ should be added to keep track of the Jacobi symbols of the messages involved, but apart from this minor modification, the attack works in exactly the same way.

The complexity of the attack depends on $\ell$ and on the probability that the integers $\mu(m_i)$ are B-smooth. But a “large” integer is very rarely B-smooth for a B corresponding to a manageable factor base $\mathfrak{P}$.

For example, the probability that a random 1024-bit integer is, say, $2^{25}$-smooth, is less than $2^{-247}$, so there is no hope to obtain a forgery in this way if the encoding function outputs random full size integers (as Full Domain Hash does, for example). On the other hand, a random 100-bit integer is $2^{25}$-smooth with probability about 0.5%, so finding $\ell \approx 2^{25}/\log(2^{25}) \approx 2^{21}$ of them should be easy. As a result, the Desmedt-Odlyzko attack is feasible when the encoding function $\mu$ outputs integers of small size.

See [CND+06] for an asymptotic complexity analysis. In practice, the attack is feasible only if the $\mu(m_i)$ are smaller than around 200 bits.

### 9.3.2 The Coron-Naccache-Stern forgery

In ISO/IEC 9796-2, the encoding function's output $\mu(m)$ is as long as $N$. This thwarts Desmedt and Odlyzko's attack. However, Coron, Naccache and Stern observed [CNS99] that it is actually sufficient to construct messages $m_i$ such that a fixed multiple $t_i$ of