Score:1

Can we solve the ECC DLP if we can distinguish whether the doubling of a public key is accompanied by reduction (modulo n) or not?

lu flag

Let $E$ be an elliptic curve over a prime or a binary extension field $GF(2^m)$, and let $G(x_g,y_g)$ be a generator point on the curve. Let $Q$ be an arbitrary point $Q = r*G$, with $r$ scalar, and $Q$ an element from the group of generator $G$ of order $n$.

I have read in some sources (e.g. here for curves over binary extension fields) that, if an actor can distinguish whether the doubling of $Q$ is accompanied by reduction (modulo $n$), then it mathematically follows that he/she can distiguish between utilizing the algorithm of division (0) or subtraction-division to reverse the sought-for number $2^l G$ or $(2^l + 1) G$, which requires no more than $log_2n$ divisions and thus reverse the elliptic curve multiplication and solve the DLP for binary elliptic curves.

Yet, I do not follow why knowledge of whether a doubling is reduced mod $n$ or not provides enough information to solve the DLP. Can someone elaborate?

kelalaka avatar
in flag
Similar to [first image of this answer](https://crypto.stackexchange.com/a/75419/18298). This is why we need a [completeness](https://safecurves.cr.yp.to/complete.html)
Aman Grewal avatar
gb flag
Is there a particular reason you're not including curves over other extension fields?
G. Stergiopoulos avatar
lu flag
@kelalaka both a point addition and a multiplication can result to reduction mod n, I do not see the connection to measuring the power usage and determine exponent bits to the question at hand.
G. Stergiopoulos avatar
lu flag
@AmanGrewal not particularly, just because of the cases I am working on, in case it makes a difference (although I can't think of any). Possibly I should generalise the question.
kelalaka avatar
in flag
It is not about the mod, it is about different formulas of double and add...
G. Stergiopoulos avatar
lu flag
Sorry but I do not understand your point. Please elaborate on an answer if you feel like it.
kelalaka avatar
in flag
To see [Look at the standard addition and doubling formulas](https://crypto.stackexchange.com/a/66296/18298)
G. Stergiopoulos avatar
lu flag
@kelaka I am fully aware of all these, your thoughts are either incomplete or out of context, so please be so kind as to either elaborate on an answer or simply let someone else do it. Thank you for your time.
bd flag
I cannot comment on the article you linked to because it is behind a paywall. My (probably very dated) understanding is that kelalaka is discussing the procedure of protecting multiplication by $r$ by blinding it by using $r+m*n$, $m$ random, instead. So when a side-channel attacker is trying to recover $r$ bit-by-bit (according to a choice of branch in double-and-add) they don't have the benefit of collecting statistical data from several runs as $m$ varies from one run to the next. The linked article may be discussing something else entirely.
G. Stergiopoulos avatar
lu flag
@JyrkiLahtonen indeed this is my understanding too but this is out of scope in terms of the question asked and yes the article discusses something else. My question doesn't have to do with leaking bits due to differential tests, but with utilizing the mod p as a discriminator in ECC equations when calculating doublings and additions. My initial understanding is that, if we know that a specific x-coordinate does/does not include a modular reduction, then we can distinguish situations to enforce a reverse binary search on the public key by following doublings/additions done. [continued]
G. Stergiopoulos avatar
lu flag
[continued] At least that's what I *think* the article is implying, but cannot put it down into math.
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.