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

(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$$.

• Mar 19, 2022 at 15:10
• Thank you. Indeed you only need to know if $y$ is odd or even to fully recover the $(x, y)$ pair. Mar 20, 2022 at 0:26
• For future searches, put this into your list SEC 2: Recommended Elliptic Curve Domain Parameters Mar 21, 2022 at 10:32

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.

• Wow. This is really helpful, thank you. Looks like the $y$ value really only adds 1 bit of entropy to the hash. Mar 19, 2022 at 10:19