In this document we explain how the ellswift
module implementation is related to the
construction in the
"SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves"
paper by Jorge Chávez-Saab, Francisco Rodríguez-Henríquez, and Mehdi Tibouchi.
- 1. Introduction
- 2. The decoding function
- 3. The encoding function
- 4. Encoding and decoding full (x, y) coordinates
The ellswift
module effectively introduces a new 64-byte public key format, with the property
that (uniformly random) public keys can be encoded as 64-byte arrays which are computationally
indistinguishable from uniform byte arrays. The module provides functions to convert public keys
from and to this format, as well as convenience functions for key generation and ECDH that operate
directly on ellswift-encoded keys.
The encoding consists of the concatenation of two (32-byte big endian) encoded field elements
Decoding consists of decoding the field elements
Encoding a given
- Loop:
- Pick a uniformly random field element
$u.$ - Compute the set
$L = F_u^{-1}(x)$ of$t$ values for which$F_u(t) = x$ , which may have up to 8 elements. - With probability
$1 - \dfrac{\#L}{8}$ , restart the loop. - Select a uniformly random
$t \in L$ and return$(u, t).$
- Pick a uniformly random field element
This is the ElligatorSwift algorithm, here given for just x-coordinates. An extension to full
First some definitions:
-
$\mathbb{F}$ is the finite field of size$q$ , of characteristic 5 or more, and$q \equiv 1 \mod 3.$ - For
secp256k1
,$q = 2^{256} - 2^{32} - 977$ , which satisfies that requirement.
- For
- Let
$E$ be the elliptic curve of points$(x, y) \in \mathbb{F}^2$ for which$y^2 = x^3 + ax + b$ , with$a$ and$b$ public constants, for which$\Delta_E = -16(4a^3 + 27b^2)$ is a square, and at least one of$(-b \pm \sqrt{-3 \Delta_E} / 36)/2$ is a square. This implies that the order of$E$ is either odd, or a multiple of 4. If$a=0$ , this condition is always fulfilled.- For
secp256k1
,$a=0$ and$b=7.$
- For
- Let the function
$g(x) = x^3 + ax + b$ , so the$E$ curve equation is also$y^2 = g(x).$ - Let the function
$h(x) = 3x^3 + 4a.$ - Define
$V$ as the set of solutions$(x_1, x_2, x_3, z)$ to$z^2 = g(x_1)g(x_2)g(x_3).$ - Define
$S_u$ as the set of solutions$(X, Y)$ to$X^2 + h(u)Y^2 = -g(u)$ and$Y \neq 0.$ -
$P_u$ is a function from$\mathbb{F}$ to$S_u$ that will be defined below. -
$\psi_u$ is a function from$S_u$ to$V$ that will be defined below.
Note: In the paper:
-
$F_u$ corresponds to$F_{0,u}$ there. -
$P_u(t)$ is called$P$ there. - All
$S_u$ sets together correspond to$S$ there. - All
$\psi_u$ functions together (operating on elements of$S$ ) correspond to$\psi$ there.
Note that for
Define the decoding function
- Let
$(x_1, x_2, x_3, z) = \psi_u(P_u(t)).$ - Return the first element
$x$ of$(x_3, x_2, x_1)$ which is a valid x-coordinate on$E$ (i.e.,$g(x)$ is square).
- For
$a=0$ , unless:-
$u = 0$ or$t = 0$ (division by zero) -
$g(u) = -t^2$ (would give$Y=0$ ).
-
- For
$a \neq 0$ , unless:-
$X_0(u) = 0$ or$h(u)t^2 = -1$ (division by zero) -
$Y_0(u) (1 - h(u)t^2) = 2X_0(u)t$ (would give$Y=0$ ).
-
The functions
The function
Put together and specialized for
Define
- Let
$X = \dfrac{u^3 + b - t^2}{2t}.$ - Let
$Y = \dfrac{X + t}{u\sqrt{-3}}.$ - Return the first
$x$ in$(u + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u}{2}, \dfrac{X}{2Y} - \dfrac{u}{2})$ for which$g(x)$ is square.
To make sure that every input decodes to a valid x-coordinate, we remap the inputs in case
Define
- Let
$u'=u$ if$u \neq 0$ ;$1$ otherwise (guaranteeing$u' \neq 0$ ). - Let
$t'=t$ if$t \neq 0$ ;$1$ otherwise (guaranteeing$t' \neq 0$ ). - Let
$t''=t'$ if$g(u') \neq -t'^2$ ;$2t'$ otherwise (guaranteeing$t'' \neq 0$ and$g(u') \neq -t''^2$ ). - Let
$X = \dfrac{u'^3 + b - t''^2}{2t''}.$ - Let
$Y = \dfrac{X + t''}{u'\sqrt{-3}}.$ - Return the first
$x$ in$(u' + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u'}{2}, \dfrac{X}{2Y} - \dfrac{u'}{2})$ for which$x^3 + b$ is square.
The choices here are not strictly necessary. Just returning a fixed constant in any of the undefined cases would suffice, but the approach here is simple enough and gives fairly uniform output even in these cases.
Note: in the paper these conditions result in
This is implemented in secp256k1_ellswift_xswiftec_frac_var
(which decodes to an x-coordinate represented as a fraction), and
in secp256k1_ellswift_xswiftec_var
(which outputs the actual x-coordinate).
To implement
- Find all the
$(X, Y) \in S_u$ that could have given rise to$x$ , through the$x_1$ ,$x_2$ , or$x_3$ formulas in$\psi_u.$ - Map those
$(X, Y)$ solutions to$t$ values using$P_u^{-1}(X, Y).$ - For each of the found
$t$ values, verify that$F_u(t) = x.$ - Return the remaining
$t$ values.
The function
The third step above, verifying that
Since we know that exactly one or exactly three out of
Observe that
It is not possible that an encoding found through the
Before working out the formulas for all this, we switch to different variables for
-
$S_u'$ becomes the set of$(v, w)$ for which$w^2 (u^2 + uv + v^2 + a) = -g(u)$ and$w \neq 0.$ - For
$a=0$ curves,$P_u^{-1}$ can be stated for$(v,w)$ as$P_u^{'-1}(v, w) = w\left(\frac{\sqrt{-3}-1}{2}u - v\right).$ -
$\psi_u$ can be stated for$(v, w)$ as$\psi_u'(v, w) = (x_1, x_2, x_3, z)$ , where
We can now write the expressions for finding
- Assuming
$x = x_1$ , we find$v = x$ and$w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions). - Assuming
$x = x_2$ , we find$v = -u-x$ and$w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions). - Assuming
$x = x_3$ , we find$w = \pm\sqrt{x-u}$ and$v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2)$ (four solutions).
The ElligatorSwift algorithm as stated in Section 1 requires the computation of
Observe that the procedure of restarting with probability
Define ElligatorSwift(x) as:
- Loop:
- Pick a uniformly random field element
$u.$ - Compute the set
$L = F_u^{-1}(x).$ - Let
$T$ be the 8-element vector consisting of the elements of$L$ , plus$8 - \#L$ times$\{\bot\}.$ - Select a uniformly random
$t \in T.$ - If
$t \neq \bot$ , return$(u, t)$ ; restart loop otherwise.
- Pick a uniformly random field element
Now notice that the order of elements in
- Formulas that yield no solutions (due to division by zero or non-existing square roots) or invalid solutions are made to return
$\bot.$ - For the
$x_1$ and$x_2$ cases, if$g(-u-x)$ is a square,$\bot$ is returned instead (the round-trip check). - In case multiple formulas would return the same non-
$\bot$ result, all but one of those must be turned into$\bot$ to avoid biasing those.
The last condition above only occurs with negligible probability for cryptographically-sized curves, but is interesting to take into account as it allows exhaustive testing in small groups. See Section 3.4 for an analysis of all the negligible cases.
If we define
Define ElligatorSwift(x) as:
- Loop:
- Pick a uniformly random field element
$u.$ - Pick a uniformly random integer
$c$ in$[0,8).$ - Let
$t = G_{c,u}(x).$ - If
$t \neq \bot$ , return$(u, t)$ ; restart loop otherwise.
- Pick a uniformly random field element
This is implemented in secp256k1_ellswift_xelligatorswift_var
.
To implement
Define
- If
$c \in \{0, 1, 4, 5\}$ (for$x_1$ and$x_2$ formulas):- If
$g(-u-x)$ is square, return$\bot$ (as$x_3$ would be valid and take precedence). - If
$c \in \{0, 4\}$ (the$x_1$ formula) let$v = x$ , otherwise let$v = -u-x$ (the$x_2$ formula) - Let
$s = -g(u)/(u^2 + uv + v^2 + a)$ (using$s = w^2$ in what follows).
- If
- Otherwise, when
$c \in \{2, 3, 6, 7\}$ (for$x_3$ formulas):- Let
$s = x-u.$ - Let
$r = \sqrt{-s(4g(u) + sh(u))}.$ - Let
$v = (r/s - u)/2$ if$c \in \{3, 7\}$ ;$(-r/s - u)/2$ otherwise.
- Let
- Let
$w = \sqrt{s}.$ - Depending on
$c:$ - If
$c \in \{0, 1, 2, 3\}:$ return$P_u^{'-1}(v, w).$ - If
$c \in \{4, 5, 6, 7\}:$ return$P_u^{'-1}(v, -w).$
- If
Whenever a square root of a non-square is taken,
Note: In the paper, the
Now observe that the
Define
- If
$c \in \{0, 1, 4, 5\}:$ - If
$g(-u-x)$ is square, return$\bot.$ - Let
$s = -g(u)/(u^2 + ux + x^2 + a).$ - Let
$v = x.$
- If
- Otherwise, when
$c \in \{2, 3, 6, 7\}:$ - Let
$s = x-u.$ - Let
$r = \sqrt{-s(4g(u) + sh(u))}.$ - Let
$v = (r/s - u)/2.$
- Let
- Let
$w = \sqrt{s}.$ - Depending on
$c:$ - If
$c \in \{0, 2\}:$ return$P_u^{'-1}(v, w).$ - If
$c \in \{1, 3\}:$ return$P_u^{'-1}(-u-v, w).$ - If
$c \in \{4, 6\}:$ return$P_u^{'-1}(v, -w).$ - If
$c \in \{5, 7\}:$ return$P_u^{'-1}(-u-v, -w).$
- If
This shows there will always be exactly 0, 4, or 8
As mentioned before there are a few cases to deal with which only happen in a negligibly small subset of inputs.
For cryptographically sized fields, if only random inputs are going to be considered, it is unnecessary to deal with these. Still, for completeness
we analyse them here. They generally fall into two categories: cases in which the encoder would produce
- In the branch for
$x_1$ and$x_2$ (where$c \in \{0, 1, 4, 5\}$ ):- When
$g(u) = 0$ , we would have$s=w=Y=0$ , which is not on$S_u.$ This is only possible on even-ordered curves. Excluding this also removes the one condition under which the simplified check for$x_3$ on the curve fails (namely when$g(x_1)=g(x_2)=0$ but$g(x_3)$ is not square). This does exclude some valid encodings: when both$g(u)=0$ and$u^2+ux+x^2+a=0$ (also implying$g(x)=0$ ), the$S_u'$ equation degenerates to$0 = 0$ , and many valid$t$ values may exist. Yet, these cannot be targeted uniformly by the encoder anyway as there will generally be more than 8. - When
$g(x) = 0$ , the same$t$ would be produced as in the$x_3$ branch (where$c \in \{2, 3, 6, 7\}$ ) which we give precedence as it can deal with$g(u)=0$ . This is again only possible on even-ordered curves.
- When
- In the branch for
$x_3$ (where$c \in \{2, 3, 6, 7\}$ ):- When
$s=0$ , a division by zero would occur. - When
$v = -u-v$ and$c \in \{3, 7\}$ , the same$t$ would be returned as in the$c \in \{2, 6\}$ cases. It is equivalent to checking whether$r=0$ . This cannot occur in the$x_1$ or$x_2$ branches, as it would trigger the$g(-u-x)$ is square condition. A similar concern for$w = -w$ does not exist, as$w=0$ is already impossible in both branches: in the first it requires$g(u)=0$ which is already outlawed on even-ordered curves and impossible on others; in the second it would trigger division by zero.
- When
- Curve-specific special cases also exist that need to be rejected, because they result in
$(u,t)$ which is invalid to the decoder, or because of division by zero in the encoder:- For
$a=0$ curves, when$u=0$ or when$t=0$ . The latter can only be reached by the encoder when$g(u)=0$ , which requires an even-ordered curve. - For
$a \neq 0$ curves, when$X_0(u)=0$ , when$h(u)t^2 = -1$ , or when$w(u + 2v) = 2X_0(u)$ while also either$w \neq 2Y_0(u)$ or$h(u)=0$ .
- For
Define a version of
- If
$a=0$ and$u=0$ , return$\bot.$ - If
$a \neq 0$ and$X_0(u)=0$ , return$\bot.$ - If
$c \in \{0, 1, 4, 5\}:$ - If
$g(u) = 0$ or$g(x) = 0$ , return$\bot$ (even curves only). - If
$g(-u-x)$ is square, return$\bot.$ - Let
$s = -g(u)/(u^2 + ux + x^2 + a)$ (cannot cause division by zero). - Let
$v = x.$
- If
- Otherwise, when
$c \in \{2, 3, 6, 7\}:$ - Let
$s = x-u.$ - Let
$r = \sqrt{-s(4g(u) + sh(u))}$ ; return$\bot$ if not square. - If
$c \in \{3, 7\}$ and$r=0$ , return$\bot.$ - If
$s = 0$ , return$\bot.$ - Let
$v = (r/s - u)/2.$
- Let
- Let
$w = \sqrt{s}$ ; return$\bot$ if not square. - If
$a \neq 0$ and$w(u+2v) = 2X_0(u)$ and either$w \neq 2Y_0(u)$ or$h(u) = 0$ , return$\bot.$ - Depending on
$c:$ - If
$c \in \{0, 2\}$ , let$t = P_u^{'-1}(v, w).$ - If
$c \in \{1, 3\}$ , let$t = P_u^{'-1}(-u-v, w).$ - If
$c \in \{4, 6\}$ , let$t = P_u^{'-1}(v, -w).$ - If
$c \in \{5, 7\}$ , let$t = P_u^{'-1}(-u-v, -w).$
- If
- If
$a=0$ and$t=0$ , return$\bot$ (even curves only). - If
$a \neq 0$ and$h(u)t^2 = -1$ , return$\bot.$ - Return
$t.$
Given any
- All cases where
$P_u(t)$ is not defined:- For
$a=0$ curves, when$u=0$ ,$t=0$ , or$g(u) = -t^2.$ - For
$a \neq 0$ curves, when$h(u)t^2 = -1$ ,$X_0(u) = 0$ , or$Y_0(u) (1 - h(u) t^2) = 2X_0(u)t.$
- For
- When
$g(u)=0$ , the potentially many$t$ values that decode to an$x$ satisfying$g(x)=0$ using the$x_2$ formula. These were excluded by the$g(u)=0$ condition in the$c \in \{0, 1, 4, 5\}$ branch.
These cases form a negligible subset of all
Specialized for odd-ordered
Define
- If
$u=0$ , return$\bot.$ - If
$c \in \{0, 1, 4, 5\}:$ - If
$(-u-x)^3 + b$ is square, return$\bot$ - Let
$s = -(u^3 + b)/(u^2 + ux + x^2)$ (cannot cause division by 0). - Let
$v = x.$
- If
- Otherwise, when
$c \in \{2, 3, 6, 7\}:$ - Let
$s = x-u.$ - Let
$r = \sqrt{-s(4(u^3 + b) + 3su^2)}$ ; return$\bot$ if not square. - If
$c \in \{3, 7\}$ and$r=0$ , return$\bot.$ - If
$s = 0$ , return$\bot.$ - Let
$v = (r/s - u)/2.$
- Let
- Let
$w = \sqrt{s}$ ; return$\bot$ if not square. - Depending on
$c:$ - If
$c \in \{0, 2\}:$ return$w(\frac{\sqrt{-3}-1}{2}u - v).$ - If
$c \in \{1, 3\}:$ return$w(\frac{\sqrt{-3}+1}{2}u + v).$ - If
$c \in \{4, 6\}:$ return$w(\frac{-\sqrt{-3}+1}{2}u + v).$ - If
$c \in \{5, 7\}:$ return$w(\frac{-\sqrt{-3}-1}{2}u - v).$
- If
This is implemented in secp256k1_ellswift_xswiftec_inv_var
.
And the x-only ElligatorSwift encoding algorithm is still:
Define ElligatorSwift(x) as:
- Loop:
- Pick a uniformly random field element
$u.$ - Pick a uniformly random integer
$c$ in$[0,8).$ - Let
$t = G_{c,u}(x).$ - If
$t \neq \bot$ , return$(u, t)$ ; restart loop otherwise.
- Pick a uniformly random field element
Note that this logic does not take the remapped
So far we have only addressed encoding and decoding x-coordinates, but in some cases an encoding
for full points with
Note that for any
Still, these four
Note: In the paper, the sign of the y coordinate is encoded in a separately-coded bit.
To encode the sign of
Define Decode(u, t) for full
- Let
$(X, Y) = P_u(t).$ - Let
$x$ be the first value in$(u + 4Y^2, \frac{-X}{2Y} - \frac{u}{2}, \frac{X}{2Y} - \frac{u}{2})$ for which$g(x)$ is square. - Let
$y = \sqrt{g(x)}.$ - If
$sign(y) = sign(Y)$ , return$(x, y)$ ; otherwise return$(x, -y).$
And encoding would be done using a
Define
- If
$c \in \{0, 1\}:$ - If
$g(u) = 0$ or$g(x) = 0$ , return$\bot$ (even curves only). - If
$g(-u-x)$ is square, return$\bot.$ - Let
$s = -g(u)/(u^2 + ux + x^2 + a)$ (cannot cause division by zero). - Let
$v = x.$
- If
- Otherwise, when
$c \in \{2, 3\}:$ - Let
$s = x-u.$ - Let
$r = \sqrt{-s(4g(u) + sh(u))}$ ; return$\bot$ if not square. - If
$c = 3$ and$r = 0$ , return$\bot.$ - Let
$v = (r/s - u)/2.$
- Let
- Let
$w = \sqrt{s}$ ; return$\bot$ if not square. - Let
$w' = w$ if$sign(w/2) = sign(y)$ ;$-w$ otherwise. - Depending on
$c:$ - If
$c \in \{0, 2\}:$ return$P_u^{'-1}(v, w').$ - If
$c \in \{1, 3\}:$ return$P_u^{'-1}(-u-v, w').$
- If
Note that
In the above logic,
For
Define Decode(u, t) as:
- Let
$u'=u$ if$u \neq 0$ ;$1$ otherwise. - Let
$t'=t$ if$t \neq 0$ ;$1$ otherwise. - Let
$t''=t'$ if$u'^3 + b + t'^2 \neq 0$ ;$2t'$ otherwise. - Let
$X = \dfrac{u'^3 + b - t''^2}{2t''}.$ - Let
$Y = \dfrac{X + t''}{u'\sqrt{-3}}.$ - Let
$x$ be the first element of$(u' + 4Y^2, \frac{-X}{2Y} - \frac{u'}{2}, \frac{X}{2Y} - \frac{u'}{2})$ for which$g(x)$ is square. - Let
$y = \sqrt{g(x)}.$ - Return
$(x, y)$ if$sign(y) = sign(t)$ ;$(x, -y)$ otherwise.
This is implemented in secp256k1_ellswift_swiftec_var
. The used
The corresponding encoder would invoke the x-only one, but negating the output
This is implemented in secp256k1_ellswift_elligatorswift_var
.
Note that this is only intended for encoding points where both the x-coordinate and y-coordinate are unpredictable. When encoding x-only points
where the y-coordinate is implicitly even (or implicitly square, or implicitly in