Score:0

Can you recover $y$ if you have $x$ in Pedersen hash?

nz flag

(this might be a silly question)

Pedersen hash works in the following way: $(x, y) = kG$ where $k$ is the pre-image and $(x, y)$ is the resulting hash.

Say we hide part of the hash to preserve privacy. Can an attacker derive $y$ if they only know $x$ given that they don't know the pre-image?

In other words, by knowing $x$ can an attacker find $y$ even if they don't know $y$ nor $k$.

kelalaka avatar
in flag
Might be a duplicate of [Roots in modulo field](https://crypto.stackexchange.com/q/20636/18298) and [Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate](https://crypto.stackexchange.com/q/82027/18298)
nz flag
Thank you. Indeed you only need to know if $y$ is odd or even to fully recover the $(x, y)$ pair.
kelalaka avatar
in flag
For future searches, put this into your list [SEC 2: Recommended Elliptic Curve Domain Parameters](https://www.secg.org/sec2-v2.pdf)
Score:1
ru flag

It's possible to narrow $y$ down to one of two possible values.

The numbers $x$ and $y$ represent the co-ordinates of an elliptic curve over a finite field. Depending on the curve selected for your commitment scheme, there will be an equation for the curve and usually a prime $p$ over which the curve is defined.

For example the widely used NIST P256 curve is defined using the prime $p=2^{256}-2^{224}+2^{192}+2^{96}-1$ and the equation $$y^2\equiv x^3-3x+b\pmod p$$ where $b$ is the number 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b.

Given $x$ we can compute $y^2\mod p$ using this equation. There should then be two possible square roots which we can compute as $$y=\pm (x^3-3x+b)^{(p+1)/4}\mod p.$$

Another common scheme uses the Ed25519 curve which uses the prime $p=2^{255}-19$ and the equation $$-x^2+y^2=1-\frac{121665}{121666}x^2y^2\pmod p.$$

Again, given $x$ one can rearrange and solve for two possible $y$ values (though the computation is not as short to write down as the one above).

In both cases, each of the 2 $y$ values is possible and there is no way to determine which is correct without further information.

nz flag
Wow. This is really helpful, thank you. Looks like the $y$ value really only adds 1 bit of entropy to the hash.
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.