Candidate Witness Encryption from Lattice Techniques

on YouTube ↗46m

" summary

Proposes a lattice-based candidate witness encryption built from GGH15 encodings that assigns an LWE secret to each edge and adds per-bit consistency memory cells so inconsistent transcripts are detected; correctness comes from summing output encodings to cancel when a valid witness exists. Security reduces to a new form of evasive LWE assumption (similar to Hotak) and an oracle experiment that limits queries, with a hybrid argument that nonetheless requires many hybrids to handle all evaluation transcripts.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:01Witness Encryption Garg, Gentry, Sahai, Waters, STOC13
3. 6:33Witness Encryption from Branching Programs
4. 10:10BP with Consistency Check [CHVW19]
5. 13:24Graph-Induced Lattice Encodings (GGH15) [Gentry, Gorbunov, Halevi, TCC15]
6. 16:42GGH15 Encodings for Branching Programs
7. 19:06Encoding the Consistency-Checking BP
8. 23:11Decryption
9. 24:05Security - Intuition
10. 27:45Security Analysis - GGH15 Example
11. 28:31Security Analysis - BP Encoding
12. 32:12Security Analysis Define a designated We experiment
13. 42:14Security Analysis - Summary

" related talks

• 51mObfuscation via GGH15 Encodings, 10 Years LaterHoeteck Wee · Obfuscation
• 01h 05mSuccinct Randomized Encodings from LatticesGiulio Malavolta · Obfuscation
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 31mIdentity-Based EncryptionParhat Abla, Huiwen Jia · RSA Conference 2024
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015