Fast Garbling of Circuits Under Standard Assumptions
summary
Demonstrates that garbling can run fast under a plain PRF/AES assumption by translating per-wire keys to per-gate PRF labels, using AES-NI plus a hand-crafted pipelined key-schedule (pshufb) to avoid related-key or ideal-cipher assumptions. Results: a 7000 AND-gate AES circuit that fixed-key implementations garble in ~300 microseconds now costs only a few hundred microseconds under PRF-mode; XORs need one ciphertext per gate, garbling uses four key-schedules/four encryptions and evaluation two schedules/two encryptions, so practical protocols show small latency penalties except for very large XOR-heavy circuits.
AI-written summary · about
chapters (21)
- 0:00Intro
- 0:25The Garbled Circuit Revolution
- 2:18Speed versus Security
- 3:12AES as an Ideal Cipher/Related Key
- 7:00Necessity of Assumptions?
- 7:55This Paper
- 9:08AES-NI Background
- 10:57Double Encryption
- 13:13The AES Key Schedule
- 14:24Key Schedule Results
- 16:23Garbling Results
- 17:30Computation cost of garbling
- 20:48Efficient XOR Gates
- 21:26The Method (inexact)
- 23:44The Ciphertext
- 24:28Cost of Garbling and Computing XOR
- 26:114-2 Row Reduction
- 26:53Experiments
- 27:38Comparing Garbling Methods
- 29:18Compare to A-Priori Graph
- 30:07Conclusions - Fixed-Key AES
related talks
40mImplementation
01h 01mSecurity: from Transistors to Compilers
44mThe Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
14mUsing Proposed Vector And Crypto Extensions For Fast And Secure Boot
40mSymmetric Design
42mEverything I always wanted to know about crypto
54mAttribute-based Encryption for Circuits
30mMy code is being hacked!