Constant-time decompression on an elliptic curve

Question

Let $E\!: y^2 = f(x)$ be an elliptic curve over a finite field $\mathbb{F}_{q}$ of odd characteristic. Consider an $\mathbb{F}_{q}$-point $P = (x,y)$ on $E$. Suppose that we only have the $x$-coordinate (with one auxiliary bit) and we want to recover $P$, that is, the value $y = \sqrt{f(x)}$.

Assume that the field $\mathbb{F}_{q}$ is highly $2$-adic, i.e., $q-1 = 2^\nu m$ for the large $2$-adicity $\nu \in \mathbb{N}$. Then, the only practical constant-time square root algorithm is Tonelli--Shanks's algorithm with a fixed quadratic non-residue in $\mathbb{F}_{q}$. Its arithmetic complexity amounts to $O(\log(q) + \nu^2)$. There is also non-constant time (Cipolla--Lehmer--)Muller's square root algorithm with the linear complexity $O(\log(q))$.

What if I know how to decompress the point $P$ in constant-time by Muller's algorithm ? Is it important in some cryptographic context ? In the literature, usually, only public points $P$ are decompressed rather than private ones.

Thank you in advance for a response.

Answer 1

In the literature, usually, only public points P are decompressed rather than private ones.

Yes, because points are usually public key or ciphertext, thus by standard assumptions non-secret, with the matching private key a secret integer/scalar.

One exception is when a public key is kept secret, shared between signer and verifier only, because it (or something derived from it) is used as a symmetric enryption key. One of few notable publications taking this unconventional approach is Pinstov and Vanstone's Postal Revenue Collection in the Digital Age, in proceedings of Financial Cryptography 2000‡:

Confidentiality of C is protected only if the postal verification public key B can not be easily obtained outside of the postal verification system. This is fortunately the case since there is no good reason to maintain access to B for anything other than verification applications. It is interesting to point out that in this scenario a public-key scheme is being used as if it were a private-key (or symmetric-key) scheme. The advantage gained, of course, is that even if confidentiality is lost, integrity is maintained.

This signature scheme is standardized as ECPVS in ANSI X9.92-1-2009‡, including with compressed public key. The standard also mentions the possibility of maintaining the public key secret, but does not endorse it:

(…) if the signer’s public key Q is only made available to the verifier, either of which would imply that third parties would not be able to verify the ECPVS signature, then it may appear that some confidentiality is obtained as a side effect. The effectiveness of this confidentiality has not be ascertained, so it would be unwise to rely on ECPVS to achieve confidentiality in this manner.

However, even in this example of ECPVS with secret public key in compressed form, I doubt that a constant-time point decompression is much useful, because timing attack of the decompression of the (fixed) public key can't leak enough information to appreciably compromise it's confidentiality.

---

Perhaps there are other more conventional tasks where constant-time construction of an Elliptic-Curve point would be useful, e.g. when mapping a secret quantity to an Elliptic Curve point. This occurs in textbook ElGamal encryption (but I don't know that it's practiced); and in applications of pairings.

---

‡ Paywalled.