Cryptanalysis of Candidate Program Obfuscators

on YouTube ↗01h 04m

" summary

Candidate obfuscators built from branching programs and multilinear encodings yield two concrete breaks: a left-kernel linear algebra attack that collects many zero-evaluations, arranges them into a matrix W, recovers boundary-scalar ratios and then requires a quantum or subexponential final step; and a much simpler rank-extraction attack that computes rank(W) to distinguish two functionally equivalent programs and recovers program structure (breaking certain matrix-PRFs in time about 2^c for c repetitions). Two open problems remain: the “integer entry problem without mod q” and improving the rank test with quantum algorithms.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 15:25Common Strategies
3. 22:13Fix a Representation of the Plaintext Program
4. 22:52Crypt Oracle Proof of How To Represent a Nand Gate
5. 24:36Branching Program
6. 25:17Adding Safeguards
7. 27:31Azan Safeguard
8. 33:29Subset Product Encoding
9. 53:34Limitations of the First Attack
10. 54:09Rock Attack
11. 56:41Matrix Product Switching Trick

" related talks

• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 51mObfuscation via GGH15 Encodings, 10 Years LaterHoeteck Wee · Obfuscation
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 51mMultilinear Maps and Attacks IISanjam Garg · Cryptography Boot Camp 2015
• 01h 15mThe Journey Towards Program ObfuscationYael Tauman Kalai · Simons Institute Workshop: New Developments in Obfuscation
• 01h 03mFrom Program Obfuscation to Unclonable CryptographyPrabhanjan Ananth · Obfuscation