view release on metacpan or  search on metacpan

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

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.