Score:3

How will the ability to do comparison or modulo efficiently in Finite Cyclic Groups break Elliptic Curve Cryptography?

et flag

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?

Score:2
ng flag

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.

et flag
Wonderful reply. Thank you
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.