notes.md

---
jupyter:
  jupytext:
    formats: ipynb,md
    text_representation:
      extension: .md
      format_name: markdown
      format_version: '1.3'
      jupytext_version: 1.13.8
  kernelspec:
    display_name: SageMath 9.0
    language: sage
    name: sagemath
---

```sage
from glv import glv_decompose_simple,\
glv_decompose,glv_decompose_two,find_lambda,\
find_sigma, find_curve, dcp_instance, semaev
```

**Bitcoin curve - basic properties**

$p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$

$E: y^2=x^3+7$

CM - discriminant = $-3$

Frobenius discriminant = $-1 \cdot 3^3 \cdot 79^2 \cdot 349^2 \cdot 2698097^2 \cdot 1359580455984873519493666411^2$

Endomorphism algebra: 
- $K = \mathbb{Q}(\sqrt{-3})$, $O_K=\mathbb{Z}[\omega]$, $\omega = \frac{1+\sqrt{-3}}{2}$ 
- $O_K^{\times} = \{\pm 1, \pm \omega,\pm \omega^2\}$
- $(\beta x,y)$ as an endomorphism has order 3 for $\beta=\sqrt[3]{1}$. We can identify $(\beta x,y)=\omega$ and get $End(E)=O_K$
- $\omega$ acts as a scalar $\lambda$ on $E(\mathbb{F}_p)$ which satisfies $\lambda^2+\lambda+1=0 \pmod n$


```sage
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
F = GF(p)
E = EllipticCurve(F,[a,b])
n = E.order()
print(E)
lamb,beta = find_lambda(E)
print(f"beta: {beta}")
print(f"lambda: {lamb}")
```


**Bitcoin curve - Twists**

Twists of $E$ are of the form $E_{\mu}:y^2=x^3+\mu$ where $\mu \in \mathbb{F}_p\setminus(\mathbb{F}_p^{\times})^6$. If we identify curves isomorphic over $\mathbb{F}_p$ we get six isomorphic classes $\mathbb{F}_p/(\mathbb{F}_p^{\times})^6$ that can be represented, for example, by $\{\pm 1, \pm 7, \pm 49\}$. Overall, we have:

| $E_1$  | $E_7$  | $E_{49}$  |
|---|---|---|
| $E_{-1}$  |$E_{-7}$   |$E_{-49}$   |

 - horizontal isomorphisms are $(\sqrt[3]{7}x,\sqrt{7}y)$ and vertical are  $(\gamma x,iy)$  where $\gamma^2=\beta$
 - isomorphisms are defined over the second extension (see the maps)
 - Frobenius traces of $E_j$ and $E_{-j}$ are opposite
 - The group $E(\mathbb{F}_{p^2})$ is a (group) product of $E_j(\mathbb{F}_p)$ and $E_{-j}(\mathbb{F}_p)$ 

```sage
E_1 = EllipticCurve(F,[0,1])
E_49 = EllipticCurve(F,[0,49])
E_m1 = EllipticCurve(F,[0,-1])
E_m7 = EllipticCurve(F,[0,-7])
E_m49 = EllipticCurve(F,[0,-49])

print(f"E_1: {E_1}")
print(f"E_7: {n}")
print(f"E_49: {E_49}")
print(f"E_m1: {E_m1}")
print(f"E_m7: {E_m7}")
print(f"E_m49: {E_m49}")

```

**Bitcoin curve - GLV** 

Any scalar $k \in \mathbb{F}_{n}$ can be decomposed as $k=k_0+k_1\lambda \pmod n$ for $k_i\approx \sqrt{n}$

```sage
k = randint(1,n)
k0,k1 = glv_decompose(k,lamb,n)
print(f"k0: {k0}, size: {k0.nbits()} bits")
print(f"k1: {k1}, size: {k1.nbits()} bits")
```

We can consider higher dimensional decompositions: $k=\sum_{i=0}^r k_i\lambda^i \pmod n$
Since $\lambda^2+\lambda+1=0 \pmod n$ then decompositions with $r>2$ alone do not improve anything:

```sage
kis = glv_decompose(k,lamb,n,dim = 4)
print("".join(f"k{i} bitsize: {ki.nbits()}\n" for i,ki in enumerate(kis)))
```

Decomposition can be done using other endomorphisms. All of them are of the form $a+b\omega$ where $a,b \in \mathbb{Z}$. "Fast endomorphisms have small degree (typically deg=1 and elements of $O_K^{\times}$). Using $deg(a+b\omega)\geq |a^2-b^2|$ we get:

- deg 1: $a=\pm 1$, $b=0$ (which is $\pm 1$) and $a=0$, $b=\pm 1$ (which is $\pm \omega$) and $a=b=\pm 1$ (which is conjugate to $\omega$). Probably no others?
- deg 2: nothing (call E.isogenies_prime_degree(2) to verify)
- deg 3: $\sigma = \omega-1$ and $-\sigma$. Again, $\sigma$ satisfies quadratic equation: $\sigma^2+3\sigma+3 = 0 \pmod n$

These are not necessarily all of them

```sage
delta, sigma_map = find_sigma(E)
print(f"sigma map: {sigma_map}")
print((delta**2+3*delta+3)%n==0)
```

**Idea:** Does it make sense to minimize the decomposition with respect to something else then the size of $k_i$? What about the discrete log with base $\sigma$, i.e. minimize $\log_{\sigma}(k_i)$?

```sage
GF(n)(delta).multiplicative_order()
```

Decomposition using more than one endomorphism will not work due to linear dependency of $\sigma$ and $\omega$ (every endomorphism is an element of $\mathbb{Z}[\omega]$)

```sage
kis = glv_decompose_two(k,lamb,delta,n)
print("".join(f"k{i} bitsize: {ki.nbits()}\n" for i,ki in enumerate(kis)))
```

**Bitcoin isogenies**


```sage
for l in prime_range(20):
    print(f"Number of {l}-degree isogenies: {len(E.isogenies_prime_degree(l))}")
```

Careful: The 2nd Modular polynomial has roots for $j=0$. The isogeny is probably not normalized or whatever and therefore not found by the isogenies_prime_degree method.

```sage
ClassicalModularPolynomialDatabase()[2](0,PolynomialRing(F,'j2').gen()).roots()
```

If you call the method on EllipticCurve_from_j(F(54000)) then the codomain has a=0. Composing with isomorphism you can enforce E to be the codomain

```sage
print("Isogenies of degree 3:")
for isog in E.isogenies_prime_degree(3):
    print(f"Domain j: {E.j_invariant()}, Codomain j:{isog.codomain().j_invariant()}")
```

The first isogeny, call it $\alpha_3$, is a loop on j-invariants but not an endomorphism of curves (only isogeny). But we can compose it with an isomorphism $\mu$ "back" to bitcoin curve to get endomorphism $\mu\alpha_3 = \sigma\omega$ of degree 3:

```sage
isog = E.isogenies_prime_degree(3)[0]
print(f"alpha_3: {isog.rational_maps()}")
u  =F(-3)**(-1)
print(f"mu*alpha_3: {u*isog.rational_maps()[0]}")
print(f"omega*sigma: {beta*sigma_map}")
```

**Idea**: Can we talk about an "isogeny" decomposition? Let $\phi_1,\phi_2,\phi_3:E_1\to E_2$ be thre isogenies and $P\in E_2$ and $kP=Q$ which we wish to compute. Let $P = \phi_1(R)$ for some $R \in E_1$. Then $kP = k\phi_1(R)=a\phi_2(R)+b\phi_3(R)$. If $a,b$ are small this could simplify the computation (probably not small, check the degrees)


#### DCP problem

Motivation: For the ZVP side-channel attack, the attacker guesses some upper bits $k$ of a secret scalar $d$ used for scalar multiplication. If he can find point $P$ (attacker has control over the input point for the SM) such that some computations during the SM involving $kP$ cause zero-value register then this can be seen in the power/EM analysis (assuming the guess of $k$ is correct). We can formalize this as a mathematical problem:

Let $k \in \mathbb{F}_n$ and $f\in \mathbb{F}_p[x_1,x_2]$. Find $P=(x_1,y_1),Q=(x_2,y_2)\in E$ such that $kP=Q$ and $f(P,Q)=0$

Typical examples of $f$: $f(x_1,x_2) = x_1x_2+1$, $f(x_1,x_2) = x_1+x_2$, $f(y_1,y_2) = y_1+y_2$. 

Only known approach: compute multiplication-by-$k$ map $m_k(x_1)$ and substitute: $f(x_1,m_k(x_1))=0$ and find roots of this one-variable polynomial. For $k>2^40$ it is infeasible to compute $m_k$.

Possible improvement can be done by searching for small $l$ ($m_l$ is computable) such that $lk$ is small as well and solve $f(m_l(x_1),m_{lk}(x_1))$. However, the probability (assume uniform) that $lk<2^b$ is $2^{b-256}$. Although we have $2^b$ candidates for $l$, the chance is negligible.

Sources:

[Formula for disaster](https://link.springer.com/content/pdf/10.1007/978-3-030-92062-3_5.pdf)

[ZVP](https://link.springer.com/content/pdf/10.1007/10958513_17.pdf)


**DCP with Bitcoin**

Let $k=k_1+k_2\lambda$ be a decomposition then $m_{k_2\lambda}(x)=m_{k_2}(\beta x)$. Also let $S_3(x_1,x_2,x_3)$ be the third Semaev polynomial (polynomial with the property $A+B+C=\infty$ iff $S_3(A_{x},B_{x},C_{x})=0$). 

We are looking for $x_1,x_2$ such that $S_3(x_2,m_{k_1}(x_1),m_{k_2}(\beta x))$ and $f(x_1,x_2)=0$. If we can express $x_2$ from the second equation and substitute into the first we have again one-variable polynomial. This time $k_1,k_2$ are much smaller then $k$ (half the bit length). However, for $256$-bit curve it is still not enough (128 bit).

In principle, we could use higher dimensional decompositions and higher degree Semaev polynomial (in the same way). The degree of $m$-th Semaev polynomial is $2^{m-2}$ in each variable and $(m-1)2^{m-2}$ total degree. If we have $r$-dim decomposition then we need to compute $\sqrt[r]{n^2}$-degree division polynomial and $f_{r+1}$ Semaev polynomial. In total, the degree after substitution of division polynomial into Semaev would be $r2^{r-1}\sqrt[r]{n^2}$ where $n\approx 2^{256}$. We get $r2^{2\cdot 256/r+r-1}$ which is decreasing for $r<120$. However, we have no such decomposition (of dimension $>2$) and the final degree is too high for every decomposition.

```sage
print(semaev(2,a=0,b=7))
print(semaev(3,a=0,b=7))
```

**Idea:** We can modify the trick with small $l$ and $lk$ with decomposition. Instead of requiring $l$ to be small we can require $l_1,l_2$ to be small in $l=l_1+l_2\lambda$. This gives us twice (in bits) the freedom for $l$. But still not enough.

**Idea:** Can we decompose using anything other maps than endomorphisms, possibly general maps? We just need $kP = k_1P+k_2\alpha(P)$ for one point $P$ (if $\alpha$ is a homomorphism then it holds for all $P$ (cyclic group))


#### DCP transport

Let $E:y^2=x^3+b \to E':y^2=x^3+u^6b$ be an isomorphism given by $\mu_u: (x,y) \mapsto (xu^2,yu^3)$

- if $f=x_1+x_2$:
    then if $P,Q$ is a solution to DCP(k) on $E$ then $\mu_u(P), \mu_u(Q)$ is a solution to DCP(k) on $E'$. This follows from $x_1+x_2=0$ $\iff$ $u^2x_1+u^2x_2=0$. Hence if we solve DCP on any curve iso to E then we have a solution on E. 
    
    - *The problem is to solve this anywhere in the isomorphism class*
- if $f=x_1x_2+1$ and $P,Q=kP$ are any points on $E$ such that $-x_1x_2$ is a quadratic residue, i.e. $-x_1x_2=u^2$, then $\mu_{u^{-1/2}}(P)$, $\mu_{u^{-1/2}}(Q)$ is a solution of  DCP(k) on $E': y^2=x^3+u^3b$ (this is possibly a twist depending on whether $u$ is a square). We can therefore find a solution of DCP on some curve in the isomorphism class of $E$ but we have no control on which curve.

    - *The problem is to solve this exactly on curve $E$*
    - *It is easy to find a solution on some curve in the isomorphism class*

- if $f=y_1+y_2$ then $x_1^3=x_2^3$ and hence $x_1 = \beta x_2$, $x_1 = \beta^2 x_2$ or $x_1 = x_2$ which means that $k \in \{\pm 1, \pm \lambda, \pm \lambda^2\}$.

    - *The problem is easy but almost always has no solution*

```sage
#help(dcp_instance)
E, P, Q, k = dcp_instance(bits = 20)
assert k*P==Q and P[0]*Q[0]+1==0
```

#### $m_k$ transport

Clearly for any isomorphims $\mu: E:y^2=x^3+b \to E':y^2=x^3+u^6b$ we have $\mu(kP)=k\mu(P)$. If we denote $m_k(b,x)$ as multiplication map on curve with coefficient $b$, then $um_k(b,x)=m_k(bu^3,ux)$. In particular $xm_k(b,x) = m_k(bx^3,x^2)$.
- If $x_1+m_k(b,x_1)=0$ which equivalent to $1+m_k(b',1)=0$ for $b'=b/x^3$. *The goal is to find a curve on which the point with $x$-coordinate 1 multiplies-by-k to a points with $x$-coordinate -1*
- If $x_1x_2=-1$ is equivalent to $m_k(bx_1^3,x_1^2)=-1$


#### $\lambda$ transport

$m_{k\lambda}(x)= m_k(\beta x) = \beta m_k(x)$ implies:
- if $x_1+x_2=0$ then $x_1$ is a solution to $x+m_{k_1}(x)=0$, $\beta x+m_{k_2}(x)=0$, $\beta^2x+m_{k_3}(x)=0$ where $k_1=k,k_2=\lambda k, k_3 = \lambda^2 k$
- if $x_1x_2=-1$ then $x_1$ is a solution to $xm_{k_1}(x)=-1$, $xm_{k_2}(x)=-\beta$, $xm_{k_3}(x)=-\beta^2$

Experimentally, gcd between every 2 is $x+x_1$ or a quadratic/cubic polynomial (in the rare case of two/three solutions). **Idea**: use "recursive gcd" using for example $\psi_{m+n}\psi_{m-n}\psi_{r}^2= \psi_{m+r}\psi_{m-r}\psi_{n}^2+\psi_{n+r}\psi_{n-r}\psi_{m}^2$. Another approach is to use Bezout identity: If $e_1$ and $e_2$ are two polynomials with the solution $x_1$ as a common root, consider $u(x)e_1(x)+v(x)e_2(x)=x+x_1$. We can evaluate $e_1,e_2$ at any point, can we do the same for $u,v$? Notice that if $k=0 \pmod 3$ and $b$ is a quadratic residue then $(0,\sqrt{b})$ is a point of order 3 and hence $e_1(0)=0$.

```sage
Es, P, Q, k = dcp_instance(p=350.next_prime())
n = Es.order()
p = Es.base_field().order()
print(f"DCP instance for x1*x2+1=0: {Es},P={P},Q={Q},k={k}")
lamb,beta = find_lambda(Es)
k1,k2,k3 = k,(lamb*k)%n,(lamb**2*k)%n
print(f"k1: {k1}, k2: {k2}, k3: {k3}")

x = PolynomialRing(Es.base_field(),'x').gen()
mk1_num = Es._multiple_x_numerator(k1, x)
mk1_den = Es._multiple_x_denominator(k1, x)
mk2_num = Es._multiple_x_numerator(k2, x)
mk2_den = Es._multiple_x_denominator(k2, x)
mk3_num = Es._multiple_x_numerator(k3, x)
mk3_den = Es._multiple_x_denominator(k3, x)

# For f = x_1*x_2+1=0:
eq1 = x*mk1_num+mk1_den
eq2 = x*mk2_num+beta*mk2_den
eq3 = x*mk3_num+beta**2*mk3_den
print(gcd(eq1,eq2).roots(multiplicities=False))
```

<!-- #region -->
**Another viewpoint:**

Is the DCP problem difficult on every curve of given bitlength? The DLP is weak is on the following curves:
- smooth order
- low embedding degree
- supersingular curves (low e.d.)


- not really weak on curves with low CM-discriminant (such as Bitcoin curve)


The DCP and the DLP problem can be thought of as inverse problems: Consider the set $S = \{(P,Q)\mid f(P_x,Q_x)=0\}$. 
- Given a tuple $(P,Q)\in S$ find $k$ such that $kP=Q$ is the DLP (not the general but almost all DLPs have the same difficulty)
- Given a scalar $k$ find a tuple $(P,Q)\in S$ such that $kP=Q$ is the DCP 
<!-- #endregion -->

#### Space of freedom

Define the following types:
- Multiscalars $M=\{(k_1,\dots,k_m)\mid a_i \in \mathbb{F}_n, m \in \mathbb{N}\}$. This represents a factorization of a scalar. We identify $(k_i)$ with $k_i$.
- $\lambda$-tuples $T_{\lambda} = \{[k_1,k_2]\in \mathbb{F}_n\times\mathbb{F}_n\}$ which represent scalar decompositions $k_1+k_2\lambda$

We also denote $MT_{\lambda}$ a set of rooted trees where each node is of two types: $M$ or $T_{\lambda}$. To each node we additionally assign a scalar represented by the type (factorization, decompozition). The edges are defined as follows:
- if $V=(k_1,\dots,k_m)\in M$, then $V$ has $m$ children with assigned scalars $k_1,\dots$ and $k_m$
- if $V=[k_1,k_2] \in T_{\lambda}$, then $V$ has two children with assigned scalars $k_1$ and $k_2$.

Moreover the root and leafs are multiscalars of length 1.

<!-- #raw -->
Example: The scalar 36 can be represented as a $MT_{2}$ tree:

      36(M)
    /   |   \
4(M)  3(T_2)  3(M)
       /  \
     1(M)  1(M)
<!-- #endraw -->

We consider the following functions on the nodes of trees in $MT_{\lambda}$:
- $\lambda$-decomposition $F_1$: Given a leaf $V\in M$: change the leaf to decomposition node (with two children)
- $\lambda$-division $F_2$: Given a leaf $V \in M$: divide the leaf by $\lambda$
- factorization (not necessarily full) $F_3$: change the leaf to a multiscalar (with children)
- multiplication $F_4$: Given a multiscalar with leafs as children, change the node to a leaf
- $l$-inverse $F_5$: Given a leaf $V$ with scalar $k$, change it to a multiscalar (with children) $(lk,l^{-1})$
- $\lambda$-composition $F_6$: Given a $T_{\lambda}$ node with (two) children as leafs, change the node to a leaf by composing "back"


**Idea:** The goal is to start with a given scalar $k$ and a corresponding one-node tree, apply functions $F_i$ repeatedly with a one-node tree as a result which has small enough scalar

Problem: include the $l$-trick somehow (two trees?)


#### Another pathological cases

The DCP problem for $f=x_1+x_2$ is easy on curves $E:y^2=x^3+ax$ over $\mathbb{F}_p$ for $p=1\pmod 4$. For such curves the map $(x,y)\mapsto(-x,iy)$, for $i=\sqrt{-1}$, is an endomorphism. The characteristic equation is $x^2+1=0 \pmod m$ where $m$ is the order of $(x_1,y_1)$ (found out experimentally). Here we are not considering the group order as the modulus as the curve never has a prime order (Why?). Anyway, if $k$ exists then it must be the root of the equation modulo some divisor of the group order.

For $f=x_1+x_2$ and curves $E:y^2=x^3+ax$ over $\mathbb{F}_p$ with $p=3\pmod 4$, the DCP doesn't have a solution as $y_1^2=-y_2^2$ but $-1$ is not a quadratic residue.

<!-- #region -->
#### DCLP

(assume that the elliptic curve group is cyclic or deal with some minor problems)

Another problem related to DCP problem is the following (DCLP) problem:
- Given $G_1, G_2$, $k$ satisfying $G_2 = kG_1$ and $f$, find scalar $l$ such that $f(lG_1,lG_2)=0$.

The DCP problem reduces to DCLP:
- Given $k$ and $f$, pick any generator $G_1$. Then any $P,Q$ such that $kP=Q$ can be expressed as $P=lG_1$ and $Q=lG_2$ and $f(P,Q)=0$ is equivalent to $f(lG_1,lG_2)=0$.

The DCLP problem reduces to DCP assuming DLP is easy:
- Given $G_1, G_2$, $k$ and $f$, solce DCP for $k$,$f$. For resulting points $P,Q$, solve the DLP for one of the pairs $(Q,G_2)$ or $(P,G_1)$. The solution is the scalar $l$.

The DLP problem reduces to DCLP:
- Given $P,Q$ solve DCLP for $G_1=G_2=P$, $k=1$, $f=x_1-Q_x$. The resulting scalar $l$ is the DL for $P,Q$.



Statements above imply that DCLP and DCP are equivalent if DLP is easy. In particular this is the case of:
- Curves with smooth order
- Curves with small embedding degree
- Anomalous curves

Conversely: If DCP is easy then DCLP and DLP are equivalent. For now, we know only about two cases for which DCP is easy (above):
- If $f=y_1+y_2$ and $E:y^2=x^3+b$
- If $f=x_1+x_2$ and $E:y^2=x^3+ax$
- Both the cases from above are a special case of $f$ representing scalar multiplication (up to sign). More precisely, the DCP is easy if $f=u(x_1)-x_2v(x_1)$ where $u(x)/v(x)$ is the x-coordinate representation of $k$-scalar multiplication (it could be any $l$-scalar multiplication but this would require $Q=kP=lP$).

**Idea**: Does it make sense to talk about equivalence: "DCLP and DCP are equivalent iff.." and if so, does it hold?


<!-- #endregion -->

```sage

```