Lower Bounds for Garbled Circuits from Shannon-Type Information Inequalities

Jake Januzelli, Mike Rosulek, Lawrence Roy
Crypto 2025
ia.cr/2025/876

---

In this paper we describe several computer-assisted lower bounds on the size of garbled circuits. This repository contains files and programs that can be used to replicate and extend our bounds.

• Citip links to our fork of the Citip prover for information theory inequalities. We added several new features, which are described in our paper.
• *.citip files are the inputs to Citip, the meaning of which is described described in our paper.
• *.proof files are the outputs of Citip
• check_proof.py can be used to verify the output proof