Cutting-Edge Innovations in Garbled Circuits and Cryptographic Schemes
Delve into the latest advancements in garbled circuits, encryption schemes, and cryptographic tools. Explore topics such as garbling schemes in Minicrypt, computational costs, and the state of the art in secure computation protocols. Discover the motivation behind intricate constructions and their practical applications in the world of cryptography.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
BitGC: Garbled Circuits with 1 Bit per Gate Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu
Garbled Circuit Garbled circuit Encoding info Garbled output Circuit Eval Garbled input Output Encode Garble Decode Input Decoding info Correctness : Output = Circuit(Input) Simulation-based privacy : (Garbled circuit, Garbled input, Decoding info) cSim(Circuit, Output)
Applications Constant-round secure two-party computation [Yao86, LP09] Garbler Evaluator (Garbled circuit, Decoding info) input Encoding info OT Garbled input (part 1) Garbled input (part 2) Other applications : ZK [JKO13], IBE [DG17]
Garbling Schemes in Minicrypt Size (bits per gate) XOR 4? 3? 0 2? GC scheme AND 4? 3? 3? 2? P&P [BMR90] GRR3 [NPS99] Free XOR [KS08] GRR2 [PSSW09] Half gates [ZRE15] 0 2? Three-halves [RR21] 0 1.5? ? bit-length of wire label (?)bits per gate seems unavoidable in Minicrypt!!
Garbling Schemes in Minicrypt Computational cost to garble an AES circuit Time Instantiation [NPS99] SHA256 6s [LPS08] SHA256 0.15s [PSSW09] AES256 0.12s [BHKR13] Fixed-key AES 0.0003? Practical in many real-world applications
Fancy GC constructions Succinct/reusable garbling schemes [LP14, CHJV15, BGL+15, KLW15, AL18, GKP+13, GGH+13b, BGG+14, Agr17] Computation-heavy cryptographic tools For example, iO and FHE Strong assumptions For example, multilinear maps Mostly theoretical (less practical)
Summary of the State of the Art Constructions in Minicrypt [KS08] : Garbling XOR gates for free [RR21] : Size per garbled AND gate: remains O( ) bits Large (linear) communication but small computation Fancy constructions Rely on computation-heavy tools (or even strong assumptions) Little communication but large computation Is there a middle ground?
Motivation for Our work Strong assumption e.g., multilinear maps Lattice assumption + circular security mitigate Heavy computation e.g., Bootstrapping Efficient computation without Bootstrapping simplify reduce Large communication O( ) bits per gate 1 bit per gate
Introducing Our Scheme: BitGC 1. Ring-LWE with circular security No multilinear maps O(1) homomorphic operations per gate 2. SWHE without bootstrapping C + ? ?2 3. Size: C + ? ?2bits 1 bit per gate |?|
Why classical GC is large? ?0,?1 (?0,?1) ?0,?1 ???,??? ?0,?1, ?0,?1,(?0,?1) Garbler Evaluator Encryptions of ? s under ?,? s Needs to contain information of ??? ???
A Different Way to Think about GC ?0,?1 (?0,?1) ?0,?1 [ ] : secret sharing Garbler Evaluator ?? , [?? ] ?? , [?? ] ????(true table) Homomorphic eval of ????(seed) 1 bit per gate ???? (PRG(seed)) differences: wire masks random bits of PRG(seed) Distributed Evaluation for SWHE (?? ??) (?? ??)
SWHE with Distributed Evaluation Somewhat homomorphic operations Special decryption: Dec , ? = ? Distributed evaluation: Eval ? + ? ,? + ? ,?1,?2,?3 Eval ?,?,?1,?2,?3 = ? Dec ,?1 + ? Dec ,?2 + ?? Dec( ,?3) Oddness: Eval ?,?, ?1, ?2, ?3 = Eval ?,?,?1,?2,?3
Using Polynomial Rings as Wire Labels Bit-string labels not compatible with SWHE! ?? /(??+ 1) Garbling based on ring elements Garbling based on bit-strings ? 1 = 1 ?? ?01 ?1 ?0 ? ??= ?0 ? ? ? 1 = 1 ?? ?01 mod 2 ?1 ?0+ 1?? ? ??= ?0+ 1?? ? ?
Overview of BitGC Garbler Evaluator ? ? ?? ?0,?1, ?0,?1 ? ? ?? ???,??? HE eval Encryptions of the true table ? ?1, ?2, ?3 ? ? Eval(???,???, ?) Oddness ?? ? = ?? ?? ? ?1,?2,?3 ??= 1d ?? ? ? Eval(???,???,?) Eval(???,???,?) Distributed evaluation ?0,?1 ? ??? ?
Cost of BitGC Garbler Evaluator ? ? ?? ?0,?1, ?0,?1 ? ? ?? ???,??? HE eval Transmitting ?? ischeap via Homomorphic PRG ? ? Eval(???,???, ?) oddness ?? ? = ?? ?? ? ? Eval (???,???,?) Eval(???,???,?) Distributed evaluation ?0,?1 ? ??? ?
Follow-up Work BitG C Authenticated BitGC Passively secure 2PC Semi-honest adversaries 1 bit per gate ?(?) homomorphic operations per gate Actively secure 2PC Malicious adversaries 2 communication overhead 2 computation overhead 150X smaller communication than SOTA [CWYY23, CWYY25] [LWYY25b] Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu. Authenticated BitGC for Actively Secure Rate-One 2PC. Accepted by Crypto 2025.
Thank you for your time ! E-mail: yyuu@sjtu.edu.cn
