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

Abstract

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.

OriginalsprogEngelsk
Titel 2023 IEEE 36th Computer Security Foundations Symposium (CSF)
Antal sider16
ForlagIEEE
Publikationsdato2023
Sider552-567
ISBN (Trykt)979-8-3503-2192-0
DOI
StatusUdgivet - 2023
Begivenhed36th IEEE Computer Security Foundations Symposium - Dubrovnik, Kroatien
Varighed: 10 jul. 202314 jul. 2023
https://www.ieee-security.org/TC/CSF2023/

Konference

Konference36th IEEE Computer Security Foundations Symposium
Land/OmrådeKroatien
ByDubrovnik
Periode10/07/202314/07/2023
Internetadresse
NavnProceedings of the IEEE Computer Security Foundations Symposium
ISSN1940-1434

Fingeraftryk

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

Citationsformater