Point (de)compression for elliptic curves over highly -adic finite fields
Dmitrii Koshelev, University of Lleida
Abstract
This article addresses the issue of efficient and safe (de)compression of -points on an elliptic curve over a highly -adic finite field of characteristic or greater. The given issue was overlooked by cryptography experts, probably because, until recently, such fields were not in trend. Therefore, there was no difficulty (with rare exceptions) in finding a square -root. However, in our days, fields with large -adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that should be computed via more sophisticated square-root algorithms such as (Cipolla-Lehmer-)Müller's one. The article explains why the classical -coordinate (de)compression method based on Müller's algorithm often contains Achilles' heel to successfully perform a novel fault attack, which also fits the definition of a (D)DoS attack. In a nutshell, the trouble stems from the non-deterministic initialization of Müller's algorithm.
Moreover, the article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve is of even order. In particular, all twisted Edwards (i.e., Montgomery) curves are relevant. The decompression stage of the new method equally suffers from one square-root extraction in . But the corresponding quadratic residue is inherently equipped with additional information, providing an opportunity to launch Müller's algorithm immediately from its main deterministic part. In turn, the compression stage of the new method remains (almost) free as well as for the -coordinate method.