How to Circumvent the Two Ciphertext Lower Bound for Linear Garbling Schemes

Explore a cryptographic talk from Asiacrypt 2016 that delves into circumventing the two ciphertext lower bound for linear garbling schemes. Learn about the innovative approach presented by Carmen Kempka, Ryo Kikuchi, and Koutarou Suzuki as they introduce garbling schemes, evaluate garbled AND gates, and propose a Free-XOR-like definition. Discover how they handle multiple gates, address security concerns, and compare their method in a plain setting. Gain insights into this advanced cryptographic topic through a comprehensive 23-minute presentation that covers key concepts such as observation techniques, idea implementation, and the garbling algorithm for single AND gates.

Intro
Garbling scheme
Observation
Evaluation on garbled AND gate
Idea 1: Free-XOR-like definition
Use + instead of
Use G with probability 1/2
Garbling algorithm for single AND gate
Handling multiple gates
Garbling other types of gate
Security
Comparison (in plain setting)
Summary