Answers are grounded in this paper and cite their sources.
This article addresses the issue of efficient and safe (de)compression of F\!q-points on an elliptic curve E over a highly $ 2 $-adic finite field F\!q of characteristic $ 5 $ 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 F\!q-root. However, recently, fields with large $ 2 $-adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that √· ∈ F\!q should be computed via more sophisticated square-root algorithms, such as (Cipolla–Lehmer–)Müller's one. This article explains why the classical x-coordinate (de)compression method based on Müller's algorithm often contains an 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, this article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve E/F\!q 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 F\!q. 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 x-coordinate method.
No takes yet. Share an insight, caveat, or question.
Dmitrii Koshelev (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: