Paper 2021/549

High-assurance field inversion for curve-based cryptography

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Field inversionConstant-time executionImplementation securityFormal verification.
Contact author(s)
bsh @ cs au dk
dfaranha @ cs au dk
spitters @ cs au dk
History
2021-04-27: revised
2021-04-27: received
See all versions
Short URL
https://ia.cr/2021/549
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/549,
      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{https://eprint.iacr.org/2021/549}},
      url = {https://eprint.iacr.org/2021/549}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.