2023
Authors
Barbosa, M; Barthe, G; Gregoire, B; Koutsos, A; Strub, PY;
Publication
ACM TRANSACTIONS ON PRIVACY AND SECURITY
Abstract
In this work, we enhance the EasyCrypt proof assistant to reason about the computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs-we also provide full semantics for the EasyCrypt module system, which was lacking previously. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and present a new formalization of universal composability.
2022
Authors
Barbosa, M; Barthe, G; Doczkal, C; Don, J; Fehr, S; Grégoire, B; Huang, YH; Hülsing, A; Lee, Y; Wu, X;
Publication
Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V
Abstract
We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results. © 2023, International Association for Cryptologic Research.
2023
Authors
Barbosa, M; Cirne, A; Esquível, L;
Publication
Proceedings of the 18th International Conference on Availability, Reliability and Security
Abstract
2024
Authors
Barbosa, M; Gellert, K; Hesse, J; Jarecki, S;
Publication
IACR Cryptol. ePrint Arch.
Abstract
2024
Authors
Arriaga, A; Barbosa, M; Jarecki, S; Skrobot, M;
Publication
IACR Cryptol. ePrint Arch.
Abstract
2024
Authors
Barbosa, M; Connolly, D; Duarte, JD; Kaiser, A; Schwabe, P; Varner, K; Westerbaan, B;
Publication
IACR Cryptol. ePrint Arch.
Abstract
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.