High-assurance field inversion for curve-based cryptography

Benjamin Salling Hvass, Diego F. Aranha, Bas Spitters

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review


The security of modern cryptography depends on multiple factors, from sound hardness assumptions to correct 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 a cryptographic computation, with a small impact on 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 [1]-[3]. In this work, we focus on implementing field inversion for primes of cryptographic interest with security against timing attacks, irrespective of whether the FLT-based inversion can be efficiently implemented. We extend the Fiat-Crypto framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang inversion algorithm as a step towards this goal. This allows a correct implementation of prime field inversion to be 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 for the largest parameters.

Titel 2023 IEEE 36th Computer Security Foundations Symposium (CSF)
Antal sider16
ISBN (Trykt)979-8-3503-2192-0
StatusUdgivet - 2023
Begivenhed36th IEEE Computer Security Foundations Symposium - Dubrovnik, Kroatien
Varighed: 10 jul. 202314 jul. 2023


Konference36th IEEE Computer Security Foundations Symposium
NavnProceedings of the IEEE Computer Security Foundations Symposium


Dyk ned i forskningsemnerne om 'High-assurance field inversion for curve-based cryptography'. Sammen danner de et unikt fingeraftryk.