14 What is not formalized
We list the gaps between the statements above and a complete security proof.
The real OT. Soundness and zero knowledge are proved with the PVW OT (Chapter 9); zero knowledge is reduced to DDH by explicit distinguishers. Lean has no notion of efficient computation, so the efficiency of these distinguishers, like the hardness of DDH itself, is outside the formalization. Soundness with the Chou–Orlandi OT is formalized as a reduction (Theorem 11.2): its bound contains the advantages of explicit square Diffie–Hellman solvers, whose efficiency, like the hardness of the problem, is outside Lean.
The hash. Authenticity is proved with the hash as a random oracle. Outside that model, correlation robustness alone is not enough to prove Free XOR secure, in the sense that a fully black-box reduction is ruled out [ CKKZ12 , Sect. 3 ] ; Choi, Katz, Kumaresan and Zhou show that a circular form of it suffices [ CKKZ12 , Sect. 4, Definition 4 and Theorem 1 ] .
Implementations. The formalization is about the abstract garbling scheme of Chapter 3; no implementation of it is verified.
Number of queries. The adversaries make a fixed number of queries, in a fixed pattern. Reducing an adversary that makes fewer queries, or interleaves them differently, to this form by padding with dummy queries is stated in the introduction but not formalized.
Adaptive corruptions and composition. All security statements concern a single execution. Security against adaptive corruptions and universal composition are discussed in Section 2.5 but not formalized; Chapter 12 proves only some protocol-specific ingredients (the equivocation condition for the receiver, the explanation of the prover, the equivocation of the commitment, soundness in decryption mode), not a simulation in a model of execution with corruptions.
Cut-and-choose. The consistency of the garbler’s own inputs across the evaluated copies is not modeled.
- ABB+17
J. B. Almeida, M. Barbosa, G. Barthe, F. Dupressoir, B. Grégoire, V. Laporte and V. Pereira, A fast and verified software stack for secure function evaluation, ACM CCS 2017, 1989–2006. IACR ePrint 2017/821.
- BAG17
D. Butler, D. Aspinall and A. Gascón, How to simulate it in Isabelle: towards formal proof for secure multi-party computation, ITP 2017, LNCS, Springer, 114–130.
- BDZ03
F. Bao, R. H. Deng and H. Zhu, Variations of Diffie–Hellman problem, ICICS 2003, LNCS 2836, Springer, 2003, 301–312.
- BHKO26
C. Barnum, D. Heath, V. Kolesnikov and R. Ostrovsky, Adaptive garbled circuits and garbled RAM from non-programmable random oracles, ITC 2026, LIPIcs 385, 11:1–11:21. Full version: IACR ePrint 2023/1527.
- BHR12
M. Bellare, V. T. Hoang and P. Rogaway, Adaptively secure garbling with applications to one-time programs and secure outsourcing, ASIACRYPT 2012, LNCS 7658, Springer, 2012, 134–153.
- BHR12b
M. Bellare, V. T. Hoang and P. Rogaway, Foundations of garbled circuits, ACM CCS 2012. Cited from the full version, IACR ePrint 2012/265.
- BLS20
D. A. Basin, A. Lochbihler and S. R. Sefidgar, CryptHOL: game-based proofs in higher-order logic, J. Cryptology 33 (2020), 494–566. Cited from IACR ePrint 2017/753.
- BPRS17
M. Byali, A. Patra, D. Ravi and P. Sarkar, Fast and universally-composable oblivious transfer and commitment scheme with adaptive security, IACR ePrint 2017/1165.
- BR06
M. Bellare and P. Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, EUROCRYPT 2006, LNCS 4004, Springer, 2006, 409–426. Cited from the full version, IACR ePrint 2004/331.
- BR93
M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, ACM CCS 1993, 62–73.
- Can20
R. Canetti, Universally composable security, J. ACM 67 (2020), no. 5, Article 28, 1–94.
- CCcore
CatCrypt Core, README of the public repository, https://github.com/spitters/CatCrypt-core, as of November 9, 2026.
- CKKZ12
S. G. Choi, J. Katz, R. Kumaresan and H.-S. Zhou, On the security of the “free-XOR” technique, TCC 2012, LNCS 7194, Springer, 2012, 39–53.
- CO15
T. Chou and C. Orlandi, The simplest protocol for oblivious transfer, LATINCRYPT 2015. Cited from the revised version, IACR ePrint 2015/267 (2018).
- CSV19
R. Canetti, A. Stoughton and M. Varia, EasyUC: using EasyCrypt to mechanize proofs of universally composable security, IEEE CSF 2019. Cited from the extended version, IACR ePrint 2019/582.
- DFMS26
S. Dziembowski, G. Fabiański, D. Micciancio and R. Stefański, Computationally sound symbolic cryptography in Lean, IEEE CSF 2026, 620–635. Cited from IACR ePrint 2025/1700.
- DKLs18
J. Doerner, Y. Kondi, E. Lee and a. shelat, Secure two-party threshold ECDSA from ECDSA assumptions, IEEE S&P 2018, 980–997. Cited from the full version, IACR ePrint 2018/499 (2023).
- FNO15
T. K. Frederiksen, J. B. Nielsen and C. Orlandi, Privacy-free garbled circuits with applications to efficient zero-knowledge, EUROCRYPT 2015, Part II, LNCS 9057, Springer, 2015, 191–219. Cited from the full version, IACR ePrint 2014/598.
- GIR
Z. A. Genç, V. Iovino and A. Rial, “The simplest protocol for oblivious transfer” revisited, IACR ePrint 2017/370; Information Processing Letters (2020).
- GKPS18
C. Ganesh, Y. Kondi, A. Patra and P. Sarkar, Efficient adaptively secure zero-knowledge from garbled circuits, PKC 2018, Part II, LNCS 10770, Springer, 2018, 499–529.
- GYWYL
X. Guo, K. Yang, X. Wang, Y. Yu and Z. Liu, Unmodified half-gates is adaptively secure — so is unmodified three-halves, IACR ePrint 2023/1528, version of July 29, 2025.
- HJO+16
B. Hemenway, Z. Jafargholi, R. Ostrovsky, A. Scafuro and D. Wichs, Adaptively secure garbled circuits from one-way functions, CRYPTO 2016, Part III, LNCS 9816, Springer, 2016, 149–178.
- HRV+23
P. G. Haselwarter, E. Rivas, A. Van Muylder, T. Winterhalter, C. Abate, N. Sidorenco, C. Hriţcu, K. Maillard and B. Spitters, SSProve: a foundational framework for modular cryptographic proofs in Coq, ACM Trans. Program. Lang. Syst. 45 (2023), no. 3, 1–61. Cited from IACR ePrint 2021/397.
- JKO13
M. Jawurek, F. Kerschbaum and C. Orlandi, Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently, ACM CCS 2013. Cited from the full version, IACR ePrint 2013/073.
- JW16
Z. Jafargholi and D. Wichs, Adaptive security of Yao’s garbled circuits, TCC 2016-B, Part I, LNCS 9985, Springer, 2016, 433–458.
- KS08
V. Kolesnikov and T. Schneider, Improved garbled circuit: free XOR gates and applications, ICALP 2008, Part II, LNCS 5126, Springer, 2008, 486–498.
- Lin13
Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, CRYPTO 2013; full version in J. Cryptology 29 (2016), 456–490. Locations are cited from the J. Cryptology version.
- Mas
P. Massot, leanblueprint, a plasTeX plugin to build formalization blueprints, https://github.com/PatrickMassot/leanblueprint.
- Mathlib20
The mathlib Community, The Lean mathematical library, CPP 2020, 367–381.
- MU21
L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, CADE-28, LNAI 12699, Springer, 2021, 625–635.
- PVW08
C. Peikert, V. Vaikuntanathan and B. Waters, A framework for efficient and composable oblivious transfer, CRYPTO 2008, LNCS 5157, Springer, 2008, 554–571. Cited from the full version, IACR ePrint 2007/348, revised January 23, 2019; we also compared the version of August 25, 2008.
- Sho04
V. Shoup, Sequences of games: a tool for taming complexity in security proofs, IACR ePrint 2004/332.
- Spi26
B. Spitters, CatCrypt: from Rust to cryptographic security in Lean, IACR ePrint 2026/604.
- TDW+26
D. Tuma, Q. Dao, J. Waters, A. Hicks and N. Hopper, VCVio: verified cryptography in Lean via oracle effects and handlers, IACR ePrint 2026/899.
- Yao86
A. C. Yao, How to generate and exchange secrets, FOCS 1986, 162–167.
- ZRE15
S. Zahur, M. Rosulek and D. Evans, Two halves make a whole: reducing data transfer in garbled circuits using half gates, EUROCRYPT 2015, Part II, LNCS 9057, Springer, 2015, 220–252.