EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical at- tackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post- quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.
Zero-knowledge proofs are just the basic concept in proof technology. Many other sophisticated formulations of proofs and related quantum-secure technology are proposed. Earlier forms of zero-knowledge proof technology are not quantum-resistant. Proofs based on generic hash functions as opposed to classical PKI cryptography are thought to be post-quantum secure because the cryptography can be upgraded, whereas classical PKI cryptography is known not to be quantum-secure. STARKs are a new form of zero-knowledge proofs for blockchains with a sophisticated architecture based on error correction codes, random queries, and inconsistency checks. The two main approaches to post-quantum cryptography are lattice-based cryptography and hash function-based cryptography. Lattice-based cryptography is currently the main method being promulgated in next-generation US NIST algorithm development. Keeping public digital infrastructure safe is a key concern. Post-quantum cryptography suggests various approaches to prepare cryptographic infrastructure for a potential future of quantum computing.
In this work we revisit the post-quantum security of KEM-based password-authenticated key exchange (PAKE), specifically that of (O)CAKE. So far, these schemes evaded a security proof considering quantum adversaries. We give a detailed analysis of why this is the case, determining the missing proof techniques. To this end, we first provide a proof of security in the post-quantum setting, up to a single gap. This proof already turns out to be technically involved, requiring advanced techniques to reason in the QROM, including the compressed oracle and the extractable QROM. To pave the way towards closing the gap, we then further identify an efficient simulator for the ideal cipher. This provides certain programming abilities as a necessary and sufficient condition to close the gap in the proof: we demonstrate that we can close the gap using the simulator, and give a meta-reduction based on KEM-anonymity that shows the impossibility of a non-programming reduction that covers a class of KEMs that includes Kyber / ML-KEM.