# Is it ever unsafe to compress an EC point?

I am working with a library that outputs EC points in uncompressed form. To save space, I'm considering modifying said library to use compressed EC points. Assuming that I keep track of the sign bit prior to compression, is there any risk in compressing said point?

I read this Q and related answer, but want to ensure that I may not be opening the door for other issues.

You will need a quadratic non-residue in order to decompress the points, and
there is no known deterministic algorithm that will provably find one efficiently.
Also, if you allow both sign bits for $\: y=0 \:$ or the point-at-infinity,
then you will lose non-malleability and strong unforgeability.

• Huh? To decompress a point, you need to compute a modular square-root. If $p \equiv 3 \pmod 4$, that's easy to do. If one were to work in a prime field with $p \equiv 1 \pmod 4$, then, yes, it's a bit more difficult, and you will need to find a quadratic nonresidue (which isn't that complicated -- pick random points until you find one works); however we generally work in fields with characteristic 3 mod 4. – poncho Apr 19 '15 at 2:12
• @poncho Curve25519 has $p \equiv 5 \pmod 8$. P-224 has $p \equiv 1 \pmod 4$. But there are efficient algorithms for computer square-roots in both of those fields. – CodesInChaos Apr 20 '15 at 18:42
• @CodesInChaos: actually, there's a deterministic solution in that case as well; it's a tad more complex than the 3 mod 4 solution, but still works. What's tougher is the 1 mod 8 case... – poncho Apr 20 '15 at 18:47
• Cipolla-Lehmer modular square root works for all prime moduli and is easier to implement compared to Shanks-Tonelli. en.wikipedia.org/wiki/Cipolla%27s_algorithm – Pierre Feb 18 '20 at 22:29

I would argue the opposite: it's safer to compress a point.

The reason is fairly simple. During decompression- whose most expensive operation is a modular square root - your are guaranteeing that the resulting point either is on the curve, zero or infinity.

One of the most frequent errors in elliptic curve operations is failing to properly validate a point before operating on it. The most public example of this is the Bluetooth pairing vulnerability - which, had it used compressed points, would not have been vulnerable to MITM attacks.

While validation is less expensive than decompression - it's one of those "seemingly optional" steps that people can forget to do. With compressed points there's no option.