Do we need elliptic curve point compression?

GnuTLS has recently added support for elliptic curves (ECDSA and Elliptic curve Diffie-Hellman). Elliptic curves are an improvement on public key technologies, mostly in efficiency because they require operations with much smaller integers for equivalent security parameters to RSA or DH. For example a 1248-bit RSA key corresponds to an 160-bit ECDSA key, saving both in space required to store parameters and in time spent for calculations.

However elliptic curve technology is considered a patent minefield and quite some attempts have been made to clarify the status, e.g. IETF made an attempt with RFC6090 to describe only the fundamental algorithms on which all patents are known to have expired. The GnuTLS implementation of ECC is based on this document.

One of the interesting "improvements" that is not included in the fundamental algorithms, and is still patented is point compression. To describe it we need a small (but not detailed) introduction to elliptic curves. An elliptic curve (at least for the needs of TLS protocol) is a set of points (x,y) that satisfy the following relation modulo a large prime p.

y² = x³ + ax + b

This set of points has some properties, i.e., a group law allowing point addition, scalar multiplication etc. Without getting into details those points need to be exchanged during a protocol run and given that the points usually belong to a "large" prime field (e.g. 256-bits), reducing the exchanged bytes is an improvement. Point compression achieves that goal, so let's see how.

Say we have a point (x₀,y₀) satisfying y₀² = x₀³ + ax₀ + b. If x₀ is known, then the previous relation becomes a second degree polynomial, that has two solutions.


y_1,2 = ±√ x³ + ax + b 


And surprisingly that's all about point compression. Instead of sending the tuple (x₀,y₀), only x₀ and a bit identifying the sign of y is sent. The receiver only needs to calculate y_1,2 and then select the appropriate using the sign bit. Of course calculating square roots modulo a prime isn't as simple as in our example, but the idea is similar.

So is this worthwhile? Are implementations like GnuTLS that don't infringe this patent in a disadvantage? While it is a clever idea, it doesn't really add much value in real-world protocols. A 256-bit curve has points of around 32 bytes. Thus the bytes saved per TLS handshake are 64 bytes overall. Such handshake typically contains data of several kilobytes, and saving few bytes isn't going to make a dramatic difference. It wouldn't be a top priority addition even if it wasn't a patented method.