Faster Verification of Faster Implementations: Combining Deductive and Circuit-Based Reasoning in EasyCrypt
José Bacelar Almeida, Gustavo Xavier Delerue Marinho Alves, Manuel Barbosa, Gilles Barthe, Luís Esquível, Vincent Hwang, Tiago Oliveira, Hugo Pacheco, Peter Schwabe, Pierre-Yves Strub
Abstract
We propose a hybrid formal verification approach that combines high-level deductive reasoning and circuit-based reasoning and apply it to highly optimized cryptographic assembly code. Our approach permits scaling up formal verification in two complementary directions: 1) it reduces the proof effort required for low-level functions where the computation logics are obfuscated by the intricate use of architecturespecific instructions and 2) it permits amortizing the effort of proving one implementation by using equivalence checking to propagate the guarantees to other implementations of the same computation using different optimizations or targeting different architectures. We demonstrate our approach via an extension to the EasyCrypt proof assistant and by revisiting formally verified implementations of ML-KEM in Jasmin. As a result, we obtain the first formally verified implementation of ML-KEM that offers performance comparable to the fastest non-verified implementation in x86-64 architectures. 1. https://github.com/EasyCrypt/easycrypt 2. https://github.com/formosa-crypto/ 1 b h 1 b l 1 b h 0 b l 0 0 b h 5 b l 5 b h 4 0 b l 4 b h 3 b l 3 0 b h 2 b l 2 b h 1 0 b l 1 b h 0 b l 0
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- SoK: Computer-Aided Cryptography cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
- SoK: Computer-Aided Cryptography cites HACL: A Verified Modern Cryptographic Library
- SoK: Computer-Aided Cryptography cites Jasmin: High-Assurance and High-Speed Cryptography
- Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises cites HACL: A Verified Modern Cryptographic Library
- Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises cites Jasmin: High-Assurance and High-Speed Cryptography
- Jasmin: High-Assurance and High-Speed Cryptography cites HACL: A Verified Modern Cryptographic Library
Builds on11
- Post-quantum Key Exchange - A New HopeErdem Alkim, Léo Ducas, Thomas Pöppelmann, Peter SchwabeUSENIX Security 2016 · 972 citations
- HACL*: A Verified Modern Cryptographic LibraryJean Karim Zinzindohoué, Karthikeyan Bhargavan, Jonathan Protzenko, Benjamin BeurdoucheCCS 2017 · 258 citations
- SoK: Computer-Aided CryptographyManuel Barbosa, Gilles Barthe, Karthik Bhargavan, Bruno Blanchet et al.S&P 2021 · 169 citations
- Jasmin: High-Assurance and High-Speed CryptographyJosé Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Arthur Blot et al.CCS 2017 · 157 citations
- Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without CompromisesAndres Erbsen, Jade Philipoom, Jason Gross, Robert Sloan et al.S&P 2019 · 147 citations
Related papers
- The Last Mile: High-Assurance and High-Speed Cryptographic ImplementationsJosé Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Benjamin Grégoire et al.S&P 2020 · 67 citations
- Jazzline: Composable CryptoLine Functional Correctness Proofs for Jasmin ProgramsJosé Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Lionel Blatter et al.CCS 2025
- Formally Verifying Kyber - Episode V: Machine-Checked IND-CCA Security and Correctness of ML-KEM in EasyCryptJosé Bacelar Almeida, Santiago Arranz-Olmos, Manuel Barbosa, Gilles Barthe et al.CRYPTO 2024 · 16 citations
- CryptOpt: Verified Compilation with Randomized Program Search for Cryptographic PrimitivesJoel Kuepper, Andres Erbsen, Jason Gross, Owen Conoly et al.PLDI 2023 · 12 citations
- Boosting the Performance of High-Assurance Cryptography: Parallel Execution and Optimizing Memory Access in Formally-Verified Line-Point Zero-KnowledgeSamuel Dittmer, Karim Eldefrawy, Stéphane Graham-Lengrand, Steve Lu et al.CCS 2023 · 5 citations
