3
$\begingroup$

This is from Vitalik Buterin's post.

Here he says

Note that modulo (%) and comparison operators (<, >, ≤, ≥) are NOT supported, as there is no efficient way to do modulo or comparison directly in finite cyclic group arithmetic (be thankful for this; if there was a way to do either one, then elliptic curve cryptography would be broken faster than you can say “binary search” and “Chinese remainder theorem”).

  • I am not sure what comparison means in an Elliptic Curve group. What exactly would less than or greater mean in terms of points? Considering this why would having comparison break ECC?

  • Again I don't understand what modulo he is referring to in Elliptic Curve Groups? What modulo if possible efficiently could break would break ECC & how?

  • Next is considering these statements in general for Finite Cyclic Groups rather than Elliptic Curve Groups specifically. For e.g. if you take a Numerical cyclic groups, then their operations itself are based on modulo (i.e. addition modulo some number or multiplication modulo some number), so why is he saying that it's not supported?

$\endgroup$

1 Answer 1

2
$\begingroup$

Comparison in an Elliptic Curve group

If we specialize a generator $G$ of an Elliptic Curve group $(\mathbb G,+)$, we can define a function $f_G:[0,n)\to\mathbb G$ where $n$ is the group order, as (with $\infty$ the group neutral/point at infinity)$$f_G(a)=\begin{cases}\infty&\text{if }a=0\\f_G(a-1)+P&\text{otherwise}\end{cases}$$

In other words, we defined $f_G$ such that $f_G(a)=a\cdot G$ where $\cdot$ is "scalar multiplication". This $f_G$ is a bijection, which inverse function $f_G^{-1}$ is well defined, even if $f_G^{-1}(P)$ is hard to compute for random given $P$. Thus the natural comparison in $[0,n)$ yields one comparison $\mathbb G$ (dependent on $G$) for elements of the Elliptic Curve group, defined as $P\;<_GQ\iff f_G^{-1}(P)<f_G^{-1}(Q)$.

Considering this why would having comparison break ECC?

Having a computable comparison breaks ECC. Given $G$ and an oracle that given $P$ and $Q$ tells if $P\;<_GQ$, we can compute the Discrete Logarithm to base $G$ (which breaks ECC) with less than $\log_2 n$ queries, by finding $x$ such that $x=f_G^{-1}(P)$ by binary search.

Modulo in Elliptic Curve Groups

For any generator $G$, it holds $P+Q=f_G(f_G^{-1}(P)+f_G^{-1}(Q)\bmod n)$. We can similarly define $P\ *_G Q$ as $f_G(f_G^{-1}(P)*f_G^{-1}(Q)\bmod n)$. Now $(\mathbb G,+,*_G)$ is isomorphic to the finite ring $\mathbb Z/n\mathbb Z$ of integers modulo $n$. With a stretch of imagination, any (of a few) modulo operators we can define in $\mathbb Z/n\mathbb Z$ yields a modulo (dependent on $G$) for $\mathbb G$.

What modulo if (computable) efficiently would break ECC & how?

Define modulo in $[0,n)$ the usual way, that is$$u\bmod v=w\iff0\le w<v\text{ and }\exists k\in\mathbb Z\text{ such that }u=k\,v+w$$

For a fixed generator $G$, that defines a modulo $\bmod_G$ in $\mathbb G$ as above. For $Q\ne\infty$ and any $P\in\mathbb G$, it holds $(P\,\bmod_G Q)=P\,\iff\,P\;<_GQ$. Thus ability to compute $\bmod_G$ implies ability to evaluate $<_G$, and thus break ECC in the group as seen before. There are actually better methods (requiring considerably less queries to a $\bmod_G$ oracle) by using the $\bmod_G$ to compute a Greatest Common Divisor.

Generalization to Finite Cyclic Groups

By definition they have a generator. It can be used to construct an isomorphism to the ring $\mathbb Z/n\mathbb Z$, and the same reasoning holds.

$\endgroup$
1
  • $\begingroup$ Wonderful reply. Thank you $\endgroup$
    – user93353
    Jan 30, 2023 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.