The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Formal certification of code-based cryptographic proofs
Abstract
As cryptographic proofs have become essentially unverifiable, cryptographers have argued in favor of developing techniques that help tame the complexity of their proofs. Game-based techniques provide a popular approach in which proofs are structured as sequences of games and in which proof steps establish the validity of transitions between successive games. Code-based techniques form an instance of this approach that takes a code-centric view of games, and that relies on programming language theory to justify proof steps. While code-based techniques contribute to formalize the security statements precisely and to carry out proofs systematically, typical proofs are so long and involved that formal verification is necessary to achieve a high degree of confidence. We present Certicrypt, a framework that enables the machine-checked construction and verification of code-based proofs. Certicrypt is built upon the general-purpose proof assistant Coq, and draws on many areas, including probability, complexity, algebra, and semantics of programming languages. Certicrypt provides certified tools to reason about the equivalence of probabilistic programs, including a relational Hoare logic, a theory of observational equivalence, verified program transformations, and game-based techniques such as reasoning about failure events. The usefulness of Certicrypt is demonstrated through various examples, including a proof of semantic security of OAEP (with a bound that improves upon existing published results), and a proof of existential unforgeability of FDH signatures. Our work provides a first yet significant step towards Halevi's ambitious programme of providing tool support for cryptographic proofs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Efficient signature generation by smart cards
Schnorr, C. P. (1991) · Journal of Cryptology · doi:10.1007/bf00196725 · Cited by 2,787
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Klein, G., Elphinstone, K., Heiser, G., Andronick, J., Cock, D., Derrin, P., Elkaduwe, D., Engelhardt, K., Kolanski, R., Norrish, M., et al. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629596 · Cited by 1,633
Zero-knowledge proofs of identity
Feige, U., Fiat, A., & Shamir, A. (1988) · Journal of Cryptology · doi:10.1007/bf02351717 · Cited by 1,029
Foundations of Cryptography: Basic Tools
Goldreich, O. (2000) · Cambridge University Press eBooks · Cited by 1,019
The random oracle methodology, revisited
Canetti, R., Goldreich, O., & Halevi, S. (2004) · Journal of the ACM · doi:10.1145/1008731.1008734 · Cited by 978
The Exact Security of Digital Signatures-How to Sign with RSA and Rabin
Bellare, M., & Rogaway, P. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_34 · Cited by 945
How to Construct Pseudorandom Permutations from Pseudorandom Functions
Luby, M., & Rackoff, C. (1988) · SIAM Journal on Computing · doi:10.1137/0217022 · Cited by 938
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
The Inductive Approach to Verifying Cryptographic Protocols
Paulson, L. C. (1998) · Cited by 836
Selecting Cryptographic Key Sizes
Lenstra, A. K., & Verheul, E. R. (2001) · Journal of Cryptology · doi:10.1007/s00145-001-0009-4 · Cited by 784
Sequences of games: a tool for taming complexity in security proofs.
Shoup, V. (2004) · Cited by 760
The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
Bellare, M., & Rogaway, P. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_25 · Cited by 672
Formal certification of a compiler back-end or: programming a compiler with a proof assistant
Leroy, X. (2006) · Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1111037.1111042 · Cited by 661
Definitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)*
Abadi, M., & Rogaway, P. (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0014-7 · Cited by 613
Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes
Okamoto, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_3 · Cited by 581
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73012 · Cited by 575
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
Semantics of probabilistic programs
Kozen, D. (1981) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(81)90036-2 · Cited by 497
The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes
Okamoto, T., & Pointcheval, D. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44586-2_8 · Cited by 477
Factorization of a 768-Bit RSA Modulus
Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., et al. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_18 · Cited by 423
Optimal Asymmetric Encryption-How to Encrypt with RSA
Bellare, M. (1995) · Cited by 382
Simple relational correctness proofs for static analyses and program transformations
Benton, N. (2004) · Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/964001.964003 · Cited by 356
On the Exact Security of Full Domain Hash
Coron, J.-S. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44598-6_14 · Cited by 347
How to Enhance the Security of Public-Key Encryption at Minimum Cost
Fujisaki, E., & Okamoto, T. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49162-7_5 · Cited by 342
Shoup, V. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_15 · Cited by 300
Efficiency improvements for signature schemes with tight security reductions
Katz, J., & Wang, N. (2003) · Proceedings of the 10th ACM conference on Computer and communications security · doi:10.1145/948109.948132 · Cited by 285
A machine-checked model for a Java-like language, virtual machine, and compiler
Klein, G., & Nipkow, T. (2006) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1146809.1146811 · Cited by 246
A computationally sound mechanized prover for security protocols
Blanchet, B. (2006) · 2006 IEEE Symposium on Security and Privacy (S&P'06) · doi:10.1109/sp.2006.1 · Cited by 221
RSA-OAEP Is Secure under the RSA Assumption
Fujisaki, E., Okamoto, T., Pointcheval, D., & Stern, J. (2004) · Journal of Cryptology · doi:10.1007/s00145-002-0204-y · Cited by 200
A Per Model of Secure Information Flow in Sequential Programs
Sabelfeld, A., & Sands, D. (2001) · Higher-Order and Symbolic Computation · doi:10.1023/a:1011553200337 · Cited by 172
Jönsson, B., Wang, Y., & Larsen, K. G. (2001) · Elsevier eBooks · doi:10.1016/b978-044482830-9/50029-1 · Cited by 150
Semantics and Program Analysis of Computationally Secure Information Flow
Laud, P. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45309-1_6 · Cited by 132
A logic for information flow in object-oriented programs
Amtoft, T., Bandhakavi, S., & Banerjee, A. (2006) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/1111037.1111046 · Cited by 128
A Revision of the Proof of the Kepler Conjecture
Hales, T., Harrison, J., McLaughlin, S., Nipkow, T., Obua, S., & Zumkeller, R. (2009) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9148-4 · Cited by 123
Strengthening Zero-Knowledge Protocols Using Signatures
Garay, J. A., MACKENZIE, P. D., & Yang, K. (2005) · Journal of Cryptology · doi:10.1007/s00145-005-0307-3 · Cited by 103
A plausible approach to computer-aided cryptographic proofs.
Halevi, S. (2005) · Cited by 93
Hall, C., Wagner, D. A., Kelsey, J. M., et al. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055742 · Cited by 90
Unifying Zero-Knowledge Proofs of Knowledge
Maurer, U. M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02384-2_17 · Cited by 73
Factoring Estimates for a 1024-Bit RSA Modulus
Lenstra, A. K., Tromer, E., Adi Shamir, Z., Kortsmit, W., Dodson, B., Hughes, J., & Leyland, P. C. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-40061-5_4 · Cited by 48
A Machine-Checked Formalization of the Generic Model and the Random Oracle Model
Barthe, G., Cederquist, J., & Tarento, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25984-8_29 · Cited by 39
Self-citationA Structured Approach to Proving Compiler Optimizations Based on Dataflow Analysis
Bertot, Y., Grégoire, B., & Leroy, X. (2006) · Lecture notes in computer science · doi:10.1007/11617990_5 · Cited by 37
Self-citationInductive Proofs of Computational Secrecy
Roy, A., Datta, A., Đerek, A., & Mitchell, J. C. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74835-9_15 · Cited by 18
Cited by
Gordon, A. D., Henzinger, T. A., Nori, A. V., & Rajamani, S. K. (2014) · Future of Software Engineering Proceedings · doi:10.1145/2593882.2593900 · Cited by 357
Modeling and Verifying Security Protocols with the Applied Pi Calculus and ProVerif
Blanchet, B. (2016) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000004 · Cited by 321
Computer-Aided Security Proofs for the Working Cryptographer
Barthe, G., Grégoire, B., Heraud, S., & Béguelin, S. Z. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_5 · Cited by 256
Self-citationSoK: Computer-Aided Cryptography
Barbosa, M., Barthe, G., Bhargavan, K., Blanchet, B., Cremers, C., Liao, K., & Parno, B. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00008 · Cited by 143
Self-citationMAC-in-the-Box: Verifying a Minimalistic Hardware Design for MAC Computation
Küennemann, R., & Nemati, H. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-59013-0_26
Metadata
- Authors
- Barthe, G., Grégoire, B., & Zanella Béguelin, S.
- Venue
- Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- Publisher
- ACM
- Published
- 2009-01-21
- Pages
- 90-101
- OpenAlex
- W2011086847
- Cited by
- 268
- References
- 50
- FWCI
- 15.28
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.