Paper 2021/549

High-assurance field inversion for curve-based cryptography

Benjamin Salling Hvass, Diego F. Aranha, and Bas Spitters


Modern cryptography must satisfy a myriad of security properties, ranging from sound hardness assumptions to correct and secure implementations that resist side-channel cryptanalysis. Curve-based cryptography is not different in this regard, and substantial progress in the last few decades has been achieved in both selecting parameters and devising secure implementation strategies. In this context, the security of implementations of field inversion is sometimes overlooked in the research literature, because (i) the approach based on Fermat's Little Theorem (FLT) suffices performance-wise for many parameters used in practice; (ii) it is typically invoked only at the very end of scalar multiplication or pairing computation, with a small impact in performance; (iii) it is challenging to implement securely for general parameters without a significant performance penalty. However, field inversion can process sensitive information and must be protected with side-channel countermeasures like any other cryptographic operation, as illustrated by recent attacks. In this work, we focus on timing attacks against field inversion for primes of cryptographic interest, both in the case when FLT-based inversion can be efficiently implemented or not. We extend the Fiat-Cryptography framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang constant-time inversion algorithm as a step toward this goal. This allows a correct implementation of prime field inversion to be conveniently synthesized for any prime. We benchmark the implementations across a range of primes for curve-based cryptography and they outperform traditional FLT-based approaches in most cases, with observed speedups up to 2.5 for the largest parameters.

Available format(s)
Publication info
Preprint. MINOR revision.
Field inversionConstant-time executionImplementation securityFormal verification.
Contact author(s)
bsh @ cs au dk
dfaranha @ cs au dk
spitters @ cs au dk
2021-04-27: revised
2021-04-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Salling Hvass and Diego F.  Aranha and Bas Spitters},
      title = {High-assurance field inversion for curve-based cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/549},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.