Score:2

Elliptic Curve - Is it possible to know whether a particular value is the result of ECadd or ECdouble?

ug flag

As we know the public key is generated from the private key and the process is point addition and point double and so on. If we see a list, it would look like a list of values coming from ECadd and ECdouble.

My question is,

  • Is it possible to know whether this value is a result of ECadd or ECdouble? (by just looking at the value or in connection with any other parameter in secp256k1 like gx or gy etc) without knowing the private key? Thanks.
poncho avatar
my flag
There are a number of point multiplication algorithms in use (with various trade-offs between time, precomputation, size of precomputed tables, side channel resistance, etc); some of these algorithms always has 'ECadd' as the last step - obviously, with such an algorithm, you can always determine the last step :-)
dave_thompson_085 avatar
cn flag
There's an old saying (in English) "six of one, half a dozen of the other" meaning two alternatives are indistinguishable. If I give you a slip of paper on which is written the number 6, can you tell whether that 6 was computed as 2x3 or as 1+5? Or for that matter 12/2 or 10-4?
Score:3
ng flag

Is it possible to know whether a particular value is the result of ECadd or ECdouble?

No. I assume "value" is as expressed in a public key; and parameters with a generator of prime order, as is the case for secp256k1 of the question.

For a start, every valid public key $R$ can be obtained by adding two valid public keys $U=2R$ and $V=-R$, or doubling a valid public key $W=((n+1)/2)\,R$ where $n$ is the (odd prime) order of the generator.

And even if we change the question to: when computing public key $R$ from secret private key $r$ with $0<r<n$ as $R=r\,G$ by scanning the binary representation of secret key $r$ from most to least significant bit and using the double and (conditionally) add method, we can't tell from $R$ if it was obtained by doubling or adding, that is if $r$ is even or odd. Argument: if hypothetically we could do this, we could find $r_i=r\bmod2^i$ for incremental values of $i$ by constructing public keys $R_i$ derived from $R$ and earlier results that would ultimately reveal $r$. If the hypothetical method always work, $R_i=(2^{-i}\bmod n)(R-r_i\,G)$ does the trick, and this can be adapted for hypothetical method giving only a small advantage for random $R$.

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.