view release on metacpan or  search on metacpan

libsecp256k1/doc/ellswift.md  view on Meta::CPAN

any order which does not place $x_3$ first requires more complicated round-trip checks in the encoder.

### 3.1 Switching to *v, w* coordinates

Before working out the formulas for all this, we switch to different variables for $S_u.$ Let $v = (X/Y - u)/2$, and
$w = 2Y.$ Or in the other direction, $X = w(u/2 + v)$ and $Y = w/2:$
* $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

$$
\begin{array}{lcl}
  x_1 & = & v \\
  x_2 & = & -u - v \\
  x_3 & = & u + w^2 \\
  z   & = & \dfrac{g(x_3)}{w}(u^2 + uv + v^2 + a) = \dfrac{-g(u)g(x_3)}{w^3}
\end{array}
$$

We can now write the expressions for finding $(v, w)$ given $x$ explicitly, by solving each of the $\\{x_1, x_2, x_3\\}$
expressions for $v$ or $w$, and using the $S_u'$ equation to find the other variable:
* 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).

### 3.2 Avoiding computing all inverses

The *ElligatorSwift* algorithm as stated in Section 1 requires the computation of $L = F_u^{-1}(x)$ (the
set of all $t$ such that $(u, t)$ decode to $x$) in full. This is unnecessary.

Observe that the procedure of restarting with probability $(1 - \frac{\\#L}{8})$ and otherwise returning a
uniformly random element from $L$ is actually equivalent to always padding $L$ with $\bot$ values up to length 8,
picking a uniformly random element from that, restarting whenever $\bot$ is picked:

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

Now notice that the order of elements in $T$ does not matter, as all we do is pick a uniformly
random element in it, so we do not need to have all $\bot$ values at the end.
As we have 8 distinct formulas for finding $(v, w)$ (taking the variants due to $\pm$ into account),
we can associate every index in $T$ with exactly one of those formulas, making sure that:
* 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](#34-dealing-with-special-cases)
for an analysis of all the negligible cases.

If we define $T = (G_{0,u}(x), G_{1,u}(x), \ldots, G_{7,u}(x))$, with each $G_{i,u}$ matching one of the formulas,
the loop can be simplified to only compute one of the inverses instead of all of them:

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

This is implemented in `secp256k1_ellswift_xelligatorswift_var`.

### 3.3 Finding the inverse

To implement $G_{c,u}$, we map $c=0$ to the $x_1$ formula, $c=1$ to the $x_2$ formula, and $c=2$ and $c=3$ to the $x_3$ formula.
Those are then repeated as $c=4$ through $c=7$ for the other sign of $w$ (noting that in each formula, $w$ is a square root of some expression).
Ignoring the negligible cases, we get:

**Define** $G_{c,u}(x)$ as:
* 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).
* 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 $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).$

Whenever a square root of a non-square is taken, $\bot$ is returned; for both square roots this happens with roughly
50% on random inputs. Similarly, when a division by 0 would occur, $\bot$ is returned as well; this will only happen
with negligible probability. A division by 0 in the first branch in fact cannot occur at all, because $u^2 + uv + v^2 + a = 0$
implies $g(-u-x) = g(x)$ which would mean the $g(-u-x)$ is square condition has triggered
and $\bot$ would have been returned already.

**Note**: In the paper, the $case$ variable corresponds roughly to the $c$ above, but only takes on 4 possible values (1 to 4).
The conditional negation of $w$ at the end is done randomly, which is equivalent, but makes testing harder. We choose to
have the $G_{c,u}$ be deterministic, and capture all choices in $c.$

Now observe that the $c \in \\{1, 5\\}$ and $c \in \\{3, 7\\}$ conditions effectively perform the same $v \rightarrow -u-v$
transformation. Furthermore, that transformation has no effect on $s$ in the first branch
as $u^2 + ux + x^2 + a = u^2 + u(-u-x) + (-u-x)^2 + a.$ Thus we can extract it out and move it down:

**Define** $G_{c,u}(x)$ as:
* 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.$
* 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 $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).$

This shows there will always be exactly 0, 4, or 8 $t$ values for a given $(u, x)$ input.
There can be 0, 1, or 2 $(v, w)$ pairs before invoking $P_u^{'-1}$, and each results in 4 distinct $t$ values.

### 3.4 Dealing with special cases

libsecp256k1/doc/ellswift.md  view on Meta::CPAN

  * 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.$
* 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 $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 $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 $u$, using this algorithm over all $x$ and $c$ values, every $t$ value will be reached exactly once,
for an $x$ for which $F_u(t) = x$ holds, except for these cases that will not be reached:
* 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.$
* 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 $(u, t)$ for cryptographically sized curves.

### 3.5 Encoding for `secp256k1`

Specialized for odd-ordered $a=0$ curves:

**Define** $G_{c,u}(x)$ as:
* 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.$
* 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 $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).$

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.

Note that this logic does not take the remapped $u=0$, $t=0$, and $g(u) = -t^2$ cases into account; it just avoids them.
While it is not impossible to make the encoder target them, this would increase the maximum number of $t$ values for a given $(u, x)$
combination beyond 8, and thereby slow down the ElligatorSwift loop proportionally, for a negligible gain in uniformity.

## 4. Encoding and decoding full *(x, y)* coordinates

So far we have only addressed encoding and decoding x-coordinates, but in some cases an encoding
for full points with $(x, y)$ coordinates is desirable. It is possible to encode this information
in $t$ as well.

Note that for any $(X, Y) \in S_u$, $(\pm X, \pm Y)$ are all on $S_u.$ Moreover, all of these are
mapped to the same x-coordinate. Negating $X$ or negating $Y$ just results in $x_1$ and $x_2$
being swapped, and does not affect $x_3.$ This will not change the outcome x-coordinate as the order
of $x_1$ and $x_2$ only matters if both were to be valid, and in that case $x_3$ would be used instead.

Still, these four $(X, Y)$ combinations all correspond to distinct $t$ values, so we can encode
the sign of the y-coordinate in the sign of $X$ or the sign of $Y.$ They correspond to the
four distinct $P_u^{'-1}$ calls in the definition of $G_{u,c}.$

**Note**: In the paper, the sign of the y coordinate is encoded in a separately-coded bit.

To encode the sign of $y$ in the sign of $Y:$

**Define** *Decode(u, t)* for full $(x, y)$ as:
* 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 $G_{c,u}(x, y)$ function defined as:

**Define** $G_{c,u}(x, y)$ as:
* 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.$
* 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 $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').$

Note that $c$ now only ranges $[0,4)$, as the sign of $w'$ is decided based on that of $y$, rather than on $c.$
This change makes some valid encodings unreachable: when $y = 0$ and $sign(Y) \neq sign(0)$.

In the above logic, $sign$ can be implemented in several ways, such as parity of the integer representation
of the input field element (for prime-sized fields) or the quadratic residuosity (for fields where
$-1$ is not square). The choice does not matter, as long as it only takes on two possible values, and for $x \neq 0$ it holds that $sign(x) \neq sign(-x)$.

### 4.1 Full *(x, y)* coordinates for `secp256k1`

For $a=0$ curves, there is another option. Note that for those,
the $P_u(t)$ function translates negations of $t$ to negations of (both) $X$ and $Y.$ Thus, we can use $sign(t)$ to
encode the y-coordinate directly. Combined with the earlier remapping to guarantee all inputs land on the curve, we get
as decoder:

**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 $sign(x)$ function is the parity of $x$ when represented as in integer in $[0,q).$

The corresponding encoder would invoke the x-only one, but negating the output $t$ if $sign(t) \neq sign(y).$

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 $[0,q/2]$), the encoder in
[Section 3.5](#35-encoding-for-secp256k1) must be used, or a bias is reintroduced that undoes all the benefit of using ElligatorSwift
in the first place.