CrypFormBench: Benchmarking Formal Analysis Capability of Large Language Models for Cryptographic Schemes DOI: 10.1145/3808184 Journal: PACMSE Volume: 3 FSE FSE177 7 fse26mainb-p1639-p CCS: Software and its engineering Formal language definitions CCS: Theory of computation Formal languages and automata theory CCS: Security and privacy Formal security models
Zhaoxuan Li, Qionglu Zhang, Hengyuan Liu, Xiaoyan Gu, Xianhui Lu, Hongbo Liu, Bingzheng Wang, Haihui Fan, Ziming Zhao, Rui Zhang, Li Zhou · 2026
Read CrypFormBench: Benchmarking Formal Analysis Capability of Large Language Models for Cryptographic Schemes DOI: 10.1145/3808184 Journal: PACMSE Volume: 3 FSE FSE177 7 fse26mainb-p1639-p CCS: Software and its engineering Formal language definitions CCS: Theory of computation Formal languages and automata theory CCS: Security and privacy Formal security models by Zhaoxuan Li, Qionglu Zhang, Hengyuan Liu, Xiaoyan Gu, Xianhui Lu, Hongbo Liu, Bingzheng Wang, Haihui Fan, Ziming Zhao, Rui Zhang, Li Zhou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25561.txt.
Introduction
Proving a cryptographic scheme secure with formal tools takes experts who can translate the scheme into a verifier's private language. Zhaoxuan Li and colleagues benchmark whether language models can do that translation in 2026. Their test set holds seven hundred instances drawn from over six hundred schemes, seven formal verifier languages, and one hundred sixty security properties. Five skills are probed separately: interpreting, generating, completing, transforming, and correcting formal descriptions.
Nine leading models were evaluated, and a split pattern emerged. Interpretation and completion went well, helped by the models' general code fluency. Generation, transformation, and correction lagged badly, with the best model scoring under half marks overall. The authors add practical remedies, from few shot prompting to light fine tuning, aimed at the executability bottleneck where outputs look plausible but no verifier will accept them.
Catalog record
| CREATOR | Zhaoxuan Li, Qionglu Zhang, Hengyuan Liu, Xiaoyan Gu, Xianhui Lu, Hongbo Liu, Bingzheng Wang, Haihui Fan, Ziming Zhao, Rui Zhang, Li Zhou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CrypFormBench: Benchmarking Formal Analysis Capability of Large Language Models for Cryptographic Schemes DOI: 10.1145/3808184 Journal: PACMSE Volume: 3 FSE FSE177 7 fse26mainb-p1639-p CCS: Software and its engineering Formal language definitions CCS: Theory of computation Formal languages and automata theory CCS: Security and privacy Formal security models Zhaoxuan Li, Qionglu Zhang, Hengyuan Liu, Xiaoyan Gu, Xianhui Lu, Hongbo Liu, Bingzheng Wang, Haihui Fan, Ziming Zhao, Rui Zhang, Li Zhou Abstract . Manual formal analysis of cryptographic schemes is labor-intensive and requires substantial expertise. While model-checking tools ( e.g., Scyther and Tamarin) and computational-security tools ( e.g., CryptoVerif and EasyCrypt) improve the automation of security proofs, they still rely on experts to abstract schemes and write tool-specific formal descriptions. Large language models (LLMs) are a promising alternative, but their effectiveness in this domain remains unexplored due to the absence of standardized evaluation methodologies. To fill this gap, we introduce CrypFormBench (C.F.B for short), a comprehensive benchmark jointly covering symbolic and computational security to evaluate five core LLM capabilities: interpretation, generation, completion, transformation, and correction. It comprises 700 instances spanning 677 schemes, 7 mainstream formal verifier languages, and 160 security properties. The evaluation of 9 state-of-the-art LLMs reveals that most of them perform well on interpretation and completion, given their code-awareness advantages, but struggle with generation, transformation, and correction. Overall, their performance remains limited, with Claude-3.5 achieving the highest score at 48.7 out of 100. We further provide practical guidance, e.g., few-shot prompting, Pass@K sampling, and lightweight fine-tuning, to mitigate the executability bottleneck and improve tool-usable outputs. Taken together, our benchmark and analyses offer a grounded view of current progress and concrete directions toward reliable LLM-assisted formal cryptographic analysis. † † cc-license: by 1. Introduction Verifying the security of cryptographic schemes and primitives is a long-standing but challenging task in formal methods ( 5 ; 47 ; 48 ) . Even widely deployed schemes such as TLS ( 22 ) , 5G-AKA ( 9 ) , SSH ( 67 ) , and OAuth 2.0 ( 35 ) have exhibited subtle flaws discovered years after deployment ( 53 ; 46 ) . Automated formal methods provide a rigorous way to uncover such vulnerabilities before deployment. Existing approaches fall into two categories: (i) model-checking tools ( e.g., Scyther ( 21 ) , AVISPA ( 4 ) , ProVerif ( 11 ) , and Tamarin ( 51 ) ) for symbolic verification, and (ii) computational frameworks ( e.g., CryptoVerif ( 12 ) and EasyCrypt ( 8 ) ) for cryptographic proof-level assurance. Nevertheless, these methods require substantial manual effort: abstracting scheme logic into specialized, error-prone, and tool-compatible languages ( e.g., HLPSL and applied \pi -calculus) demands expertise in both cryptography and formal specification. This bottleneck motivates exploring large language models (LLMs) ( 40 ; 68 ) to assist in formal analysis by automatically deriving formal specifications from natural-language descriptions, as depicted in Fig. 1 . The current LLMs, particularly code-oriented variants, have shown promising capabilities in code generation ( 15 ) , symbolic reasoning ( 14 ) , and even guiding proof assistants like Coq ( 10 ) and Lean ( 65 ; 6 ; 66 ) . Yet cryptographic scheme specifications remain a uniquely challenging domain due to their combination of strict syntax, security-critical semantics, and long contextual dependencies, where small errors can break verification. Prior studies indicate that LLMs often struggle with such highly structured, domain-specific languages ( 5 ; 30 ) , and may miss critical information in long inputs ( 45 ) . Thus, their end-to-end formal capability for formal cryptographic analysis remains unclear. Figure 1. Motivation for benchmarking LLM-assisted Cryptographic Scheme analysis. Recently, a preliminary benchmark ( 49 ) was proposed to evaluate automatic modeling tasks that support only symbolic security, with 18 real-world protocols and excluding computational security, advanced primitives, and diverse threat models. Unlike general-purpose code benchmarks ( 15 ; 36 ) , constructing a benchmark for cryptographic scheme analysis poses unique challenges: complex semantics, multiple formal languages, and various adversarial assumptions. These gaps call for a more comprehensive and systematic evaluation framework. To address these challenges, we design CrypFormBench (C.F.B for short), the first benchmark that jointly covers symbolic and computational security, providing a unified platform for evaluating LLMs in cryptographic scheme analysis. It spans five core tasks, namely interpretation , generation , completion , transformation , and correction , reflecting the essential capabilities required for tool-usable formal specification. It includes 700 curated instances (filtered from 4549 projects on GitHub or web sources) across seven verifiers’ languages, covering 677 schemes and 160 security properties, from classical authentication scenarios to modern MPC, ZK, and post-quantum designs. Furthermore, we built an automated evaluation pipeline that standardizes model interactions, integrates cross-tool verification, and applies a multidimensional scoring framework that combines task-level metrics with overall rankings. This enables scalable and fine-grained assessment of LLM performance. In summary, we make the following main contributions. • We introduce C.F.B, a large-scale benchmark across seven verifier languages, enabling systematic evaluation of LLMs in cryptographic scheme analysis ( c.f., § 3 ). • We propose a unified evaluation methodology that integrates automated model interaction, multi-tool verification, and a weighted scoring framework ( c.f., § 4 ). • We conduct the first comprehensive evaluation of nine state-of-the-art LLMs ( e.g., GPT-4o , Claude-3.5 , and DeepSeek-Coder ), revealing strengths in interpretation/completion and weaknesses in generation/transformation/correction ( c.f., § 5 ), highlighting the challenges of domain-specific language generation. Also, we present robustness/optimization analyses and fine-grained property-level evaluation ( c.f., § 6 ), demonstrating the stability of our findings. 2. Preliminaries 2.1. Formal Language of Cryptographic Scheme Analysis Tools Automatic cryptographic-scheme analysis is driven by the formal languages of verification tools, whose assumptions range from symbolic (Dolev-Yao) models to computational proofs under standard assumptions ( 7 ) . Table 1 lists representative, widely adopted tools and languages spanning diverse techniques. Scyther ( 21 ) and AVISPA ( 4 ) offer efficient and accessible analysis of classical authentication schemes. ProVerif ( 11 ) and Tamarin ( 51 ) enable deep reasoning about equivalence and unbounded behaviors. Maude-NPA ( 23 ) supports algebraic reasoning. CryptoVerif ( 12 ) and EasyCrypt ( 8 ) provide computational guarantees aligned with security properties. As surveyed in ( 19 ) , these tools constitute the SOTAs for the formal analysis of cryptographic schemes. Table 1. Representative formal tools and their specification languages. Tool Language Key Characteristics / Advantages Scyther ( 21 ) SPDL Lightweight and efficient symbolic model for secrecy/authentication claims. Tamarin ( 51 ) SPTHY Support stateful protocols and observational equivalence. AVISPA ( 4 ) HLPSL Supports multiple parallelized back-end engines (OFMC, CL-AtSe, SATMC). ProVerif ( 11 ) PV/HORN/… Handle unbounded sessions, and support for secrecy/equivalence properties. Maude-NPA ( 23 ) MAUDE Analyze algebraic properties, and handle timeouts and internal errors. CryptoVerif ( 12 ) CV/OCV Computational soundness under both classical and random oracle models. EasyCrypt ( 8 ) EC Higher-order logic for computational proofs, and has machine-checked rigor. 2.2. A Generative Example for Automatic Formal Analysis Natural-language scheme descriptions can be mapped into formal languages required by analysis tools ( 59 ) . For example, “the client sends a hash value of n to the server” can be expressed as: SPDL (Scyther): send_1(C,