Dependencies

For a prime \(q\), define the length of the encoded bit strings as

The base point of [bernstein2013a], Section 4.1 is \((x, y) = (4/V, 3/5)\), where \(V\) is the \(V\)-coordinate of the point of order \(4p_1\) on the Montgomery model at \(U = 4\).

A bit string \((\tau _0, \tau _1, \ldots , \tau _{n-1}) \in \{ 0,1\} ^n\) has binary value

Let \(q\) be a prime power congruent to \(3\) modulo \(4\), and let \(s\) be a nonzero element of \(\mathbb {F}_q\) with \((s^2 - 2)(s^2 + 2) \neq 0\). Define

Curve1174 is the complete Edwards curve

over \(\mathbb {F}_q\), obtained from the Elligator 1 construction with the parameter \(s\).

With \(c = 2/s^2\) as above, define

the coefficient of the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\).

The map \(\varphi : \mathbb {F}_q \to E(\mathbb {F}_q)\) of Definition 2, specialised to Curve1174.

For a coefficient \(d \notin \{ 0, 1\} \), the complete Edwards curve \(E\) over \(\mathbb {F}_q\) is given by the equation

With \(d = -(c + 1)^2/(c - 1)^2\) as in Theorem 1, let

be the set of affine points of the complete Edwards curve \(E\).

Let \(\mathbb {F}_q\) be the prime field with \(q = 2^{251} - 9\) elements.

For a modulus \(m\), a fuel bound \(fuel\), a base \(b\) and an exponent \(e\) define \(\operatorname {powMod}\) by binary exponentiation, so that \(\operatorname {powMod}(m, fuel, b, e) = b^e \bmod m\) whenever \(e {\lt} 2^{fuel}\).

Curve1174 is defined over \(\mathbb {F}_q\) with

With \(c = 2/s^2\) as above, define

Define the set of admissible bit strings as

i.e. the strings whose binary value lies in the lower half of \(\mathbb {F}_q\).

Define \(s \in \mathbb {F}_q\) to be

For a point \((x, y) \in \varphi (\mathbb {F}_q)\), with \(\bar u\) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) define

For a point \((x, y) \in \varphi (\mathbb {F}_q)\), with \(z\) and \(\bar X\) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), with \(u\) and \(r\) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), with \(c\), \(X\) and \(Y\) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), with \(u\) and \(v\) as above and \(\chi \) the quadratic character of \(\mathbb {F}_q\), define

For a point \((x, y) \in \varphi (\mathbb {F}_q)\), with \(\eta \) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), with \(u\), \(v\) and \(c\) as above, define

For \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), with \(r\) and \(X\) as above, define

For a point \((x, y) \in \varphi (\mathbb {F}_q)\), with \(\bar X\) as above, define

For a point \((x, y)\) of \(E(\mathbb {F}_q)\) with \(y + 1 \neq 0\), define

In the situation of Definition 2, assume that \(q\) is prime, and let \(b\), \(\sigma \) and \(S\) be as above. Define

by \(\iota (\tau ) = \varphi (\sigma (\tau ))\).

The set of curve points produced by the string encoding,

The string encoding of Theorem 4, viewed as a map

with codomain the image of \(\varphi \) rather than all of \(E(\mathbb {F}_q)\).

Define \(\sigma : \{ 0,1\} ^b \to \mathbb {F}_q\) by

Fix a prime power \(q \equiv 3 \pmod4\). Define \(\chi : \mathbb {F}_q \to \mathbb {F}_q\) as the quadratic character of \(\mathbb {F}_q\), with its values \(0, \pm 1\) read inside \(\mathbb {F}_q\); equivalently

If \(a\) is a nonzero square then \(\chi (a) = 1\); if \(a\) is a non-square then \(\chi (a) = -1\); if \(a = 0\) then \(\chi (a) = 0\).

In the situation of Theorem 1, the decoding function for the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\) is the function \(\varphi : \mathbb {F}_q \to E(\mathbb {F}_q)\) defined as follows:

if \(t \notin \{ \pm 1\} \) then \(\varphi (t) = (x, y)\).

The image of the decoding function of Definition 2,

The first of the three conditions characterizing \(\varphi (\mathbb {F}_q)\) inside \(E(\mathbb {F}_q)\) in Theorem 3: a point \((x, y)\) satisfies

The second of the three conditions characterizing \(\varphi (\mathbb {F}_q)\) inside \(E(\mathbb {F}_q)\) in Theorem 3: a point \((x, y)\) satisfies that

is a square, where \(\eta = (y - 1)/(2(y + 1))\).

The third of the three conditions characterizing \(\varphi (\mathbb {F}_q)\) inside \(E(\mathbb {F}_q)\) in Theorem 3: a point \((x, y)\) satisfies that if \(\eta r = -2\) then

The conjunction of the three conditions of Theorem 3 for a point \((x, y) \in E(\mathbb {F}_q)\): \(y + 1 \neq 0\); \((1 + \eta r)^2 - 1\) is a square, where \(\eta = (y - 1)/(2(y + 1))\); and if \(\eta r = -2\) then \(x = 2s(c - 1)\chi (c)/r\).

In the situation of Theorem 1, the decoding function for the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\) is the function \(\varphi : \mathbb {F}_q \to E(\mathbb {F}_q)\) with

Here \(\varphi \) is regarded as a map \(\mathbb {F}_q \to \mathbb {F}_q \times \mathbb {F}_q\), forgetting the proof that the image lies on \(E\).

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(r\), \(X\), \(Y\) be as above. Then

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(x\), \(y\) be as above. Then \((x, y)\) is a point of the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\), i.e.

In the situation of Theorem 4, the set of admissible strings satisfies

In the situation of Theorem 1, for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) the denominator of

is nonzero, i.e. \(1 + t \neq 0\).

In the situation of Theorem 1, let \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \) and let \(u, v, X, Y, x, y\) be as above. Then

In the situation of Theorem 1, \(Y \neq 0\) for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), so that

is defined.

In the situation of Theorem 1, \(rX + (1 + X)^2 \neq 0\) for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), so that

is defined.

In the situation of Theorem 1, the quantity

is defined for each \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), since \(c^2 \neq 0\).

For Curve1174 the string length of Theorem 4 is \(b = \lfloor \log _2 q \rfloor = 250\).

The point \((4/V, 3/5)\) satisfies the Curve1174 equation.

The point \((U, V) = (4, V)\) lies on the Montgomery curve

Since \(2^b \leq q\) and \(2^b {\gt} q/2\), each of \(0, 1, \ldots , (q-1)/2\) has a preimage under \(\sigma \), and the binary values of the strings in \(S\) are exactly

Distinct bit strings of length \(n\) have distinct binary values \(\sum _i \tau _i 2^i\).

Every integer \(m\) with \(0 \leq m {\lt} 2^n\) is the binary value of some bit string of length \(n\).

With \(s\) as above, \(c = 2/s^2\) equals

In the situation of Theorem 1, \(c = 2/s^2\) satisfies

The quadratic character of the Edwards coefficient satisfies \(\chi (d) = -1\).

In the situation of Theorem 1, \(d = -(c + 1)^2/(c - 1)^2\) is not a square in \(\mathbb {F}_q\): otherwise \(-1 = d(c - 1)^2/(c + 1)^2\) would be a square, a contradiction.

The neutral point \((0, 1)\), which is the value of \(\varphi (\pm 1)\) in Definition 2, lies on the complete Edwards curve \(E : x^2 + y^2 = 1 + d x^2 y^2\).

Since \(2^b {\gt} q/2\), the set \(\{ 0, 1, \ldots , (q-1)/2\} \) is a subset of \(\{ 0, 1, \ldots , 2^b - 1\} \); hence each of \(0, 1, \ldots , (q-1)/2\) has a preimage under \(\sigma \), lying in \(S\).

For every \(t \in \mathbb {F}_q\), at least one of \(t, -t\) lies in \(\{ 0, 1, \ldots , (q-1)/2\} = \sigma (S)\); that is, there is \(\tau \in S\) with \(\sigma (\tau ) = t\) or \(\sigma (\tau ) = -t\).

Let \(q\) be prime and let \(a, b \in \{ 0, 1, \ldots , (q-1)/2\} \) with \(a = -b\) in \(\mathbb {F}_q\). Then \(a = b\). This is the step of Theorem 4 that removes the sign ambiguity of \(\varphi \).

In the situation of Theorem 1, \(1 + X \neq 0\): if \(X = -1\) then \(u = -\chi (v)\), so \(v = -\chi (v)r^2\) and hence \(\chi (v) = -\chi (v)\), a contradiction.

The characteristic satisfies \(q \equiv 3 \pmod4\), so the standing hypotheses of Elligator 1 are met by \(\mathbb {F}_q\).

The number \(q = 2^{251} - 9\) is prime.

With \(c\) as above, \(r = c + 1/c\) equals

In the situation of Theorem 1, \(r = c + 1/c \neq 0\): if \(r = 0\) then \(c = -1/c\), so \(c^2 = -1\), a contradiction since \(-1\) is not a square in \(\mathbb {F}_q\).

The element \(s\) is nonzero and satisfies \((s^2 - 2)(s^2 + 2) \neq 0\).

Binary evaluation is injective, hence

For \(q \equiv 3 \pmod4\), the set \(S\) has exactly

elements.

For \(t \in \mathbb {F}_q\), the parameter \(\bar t\) reconstructed from \(\varphi (t)\) in Theorem 3.3 satisfies \(\bar t = t\) or \(\bar t = -t\). This is the key step showing that \(\varphi (t)\) has no preimages besides \(t\) and \(-t\).

With \(b = \lfloor \log _2 q \rfloor \) we have \(2^b \leq q\); hence the integers \(0, 1, \ldots , 2^b - 1\) are distinct in \(\mathbb {F}_q\).

In the situation of Theorem 1, \(u = (1 - t)/(1 + t) \neq 0\) for \(t \in \mathbb {F}_q \setminus \{ \pm 1\} \), since \(1 - t \neq 0\) and \(1 + t \neq 0\).

In the situation of Theorem 1, \(v \neq 0\).

In the situation of Theorem 1, \(XY \neq 0\); in particular \(Y \neq 0\), so \(x = (c - 1)sX(1 + X)/Y\) is defined.

In the situation of Theorem 1, \(x = (c - 1)sX(1 + X)/Y \neq 0\), since \(c \neq 1\), \(s \neq 0\), \(X \neq 0\) and \(1 + X \neq 0\).

In the situation of Theorem 1, \(X = \chi (v)u \neq 0\), since \(u \neq 0\) and \(\chi (v) \neq 0\).

Since \(2^b \leq q\), the integers \(0, 1, \ldots , 2^b - 1\) are distinct in \(\mathbb {F}_q\); hence \(\sigma \) is injective.

The forward part of statement 1 of Theorem 3: for every \(t \in \mathbb {F}_q\),

With \(c = 2/s^2\) as above,

so the complete Edwards curve of Theorem 1 and Definition 2 for this choice of \((q, s)\) is exactly Curve1174, \(x^2 + y^2 = 1 - 1174 x^2 y^2\).

The coefficient \(-1174\) is a non-square in \(\mathbb {F}_q\); this is the criterion of [bernstein2013a, Theorem 3.3] making Curve1174 a complete Edwards curve.

For every \(t \in \mathbb {F}_q\) the point \(\varphi (t)\) lies on Curve1174.

For Curve1174 the string encoding \(\iota \) is a bijection from \(S\) onto \(\varphi (\mathbb {F}_q)\).

The reverse part of statement 2 of Theorem 3: every \((x, y) \in E(\mathbb {F}_q)\) such that \(y + 1 \neq 0\); \((1 + \eta r)^2 - 1\) is a square, where \(\eta = (y - 1)/(2(y + 1))\); and \(x = 2s(c - 1)\chi (c)/r\) whenever \(\eta r = -2\), lies in \(\varphi (\mathbb {F}_q)\).

The forward part of statement 2 of Theorem 3: every \((x, y) \in \varphi (\mathbb {F}_q)\) satisfies \(y + 1 \neq 0\); \((1 + \eta r)^2 - 1\) is a square, where \(\eta = (y - 1)/(2(y + 1))\); and if \(\eta r = -2\) then \(x = 2s(c - 1)\chi (c)/r\).

Let \(p\) be a natural number and let \(L\) be a list of primes with \(\prod _{r \in L} r = p - 1\). If there is an \(a\) with \(a^{p-1} \equiv 1 \pmod p\) and \(a^{(p-1)/r} \not\equiv 1 \pmod p\) for every \(r \in L\), then \(p\) is prime.

For \((x, y) \in \varphi (\mathbb {F}_q)\) the denominator \(1 + \bar u\) of \(\bar t\) in Theorem 3.3 is nonzero, so \(\bar t\) is defined.

In the situation of Definition 2: if \(t \in \mathbb {F}_q\) then the set of preimages of \(\varphi (t)\) under \(\varphi \) is \(\{ t, -t\} \). Equivalently, \(\varphi (t) = \varphi (-t)\) if and only if no element of \(\mathbb {F}_q\) other than \(t\) and \(-t\) maps to \(\varphi (t)\).

In the situation of Definition 2: \(\varphi (\mathbb {F}_q)\) is the set of \((x, y) \in E(\mathbb {F}_q)\) such that

• \(y + 1 \neq 0\);

• \((1 + \eta r)^2 - 1\) is a square, where \(\eta = \frac{y - 1}{2(y + 1)}\); and

• if \(\eta r = -2\) then \(x = 2s(c - 1)\chi (c)/r\).

In the situation of Definition 2: if \((x, y) \in \varphi (\mathbb {F}_q)\) then the following elements \(\bar X, z, \bar u, \bar t\) of \(\mathbb {F}_q\) are defined and \(\varphi (\bar t) = (x, y)\):

In the situation of Theorem 4, \(\iota \) is an injective map from \(S\) to \(E(\mathbb {F}_q)\).

In the situation of Theorem 4, \(\iota (S) = \varphi (\mathbb {F}_q)\).

For \((x, y) \in \varphi (\mathbb {F}_q)\) the denominator \(2(y + 1)\) of \(\eta \) is nonzero, so \(\eta \) and hence \(\bar X\) of Theorem 3.3 are defined.

The denominator \(c^2\) occurring in \(z\) of Theorem 3.3 is nonzero, so \(z\) is defined.

Combining the injectivity of \(\iota \) with \(\iota (S) = \varphi (\mathbb {F}_q)\): the map

is a bijection.

The reverse part of statement 1 of Theorem 3: for \(t \in \mathbb {F}_q\), no element of \(\mathbb {F}_q\) other than \(t\) and \(-t\) is a preimage of \(\varphi (t)\) under \(\varphi \).