Three halves make a whole? Beating the half-gates lower bound for garbled circuits

DOI10.1007/978-3-030-84242-0_5zbMath1497.94203OpenAlexW3187028412MaRDI QIDQ2120069

Mike Rosulek, Lawrence Roy

Publication date: 31 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-84242-0_5

zbMATH Keywords

garbling scheme for Boolean circuits

Mathematics Subject Classification ID

Cryptography (94A60) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items

\textsc{EpiGRAM}: practical garbled RAM ⋮ Garbled circuits with sublinear evaluator ⋮ New ways to garble arithmetic circuits ⋮ Actively secure half-gates with minimum overhead under duplex networks ⋮ Authenticated garbling from simple correlations ⋮ NanoGRAM: garbled RAM with \(\widetilde{O}(\log N)\) overhead ⋮ One-time programs from commodity hardware ⋮ Breaking and fixing garbled circuits when a gate has duplicate input wires ⋮ Tri-state circuits. A circuit model that captures RAM

Uses Software

• FleXOR

Cites Work

• A proof of security of Yao's protocol for two-party computation
• Improvements for gate-hiding garbled circuits
• Fast garbling of circuits under standard assumptions
• Linicrypt: A Model for Practical Cryptography
• FleXOR: Flexible Garbling for XOR Gates That Beats Free-XOR
• On the Security of the “Free-XOR” Technique
• Privacy-Free Garbled Circuits with Applications to Efficient Zero-Knowledge
• Two Halves Make a Whole
• How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes
• Improved Garbled Circuit: Free XOR Gates and Applications
• Secure Two-Party Computation Is Practical