[Resource Topic] 2018/360: GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates

Welcome to the resource topic for 2018/360

GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates

Authors: Yilei Chen, Vinod Vaikuntanathan, Hoeteck Wee


We carry out a systematic study of the GGH15 graded encoding scheme used with general branching programs. This is motivated by the fact that general branching programs are more efficient than permutation branching programs and also substantially more expressive in the read-once setting. Our main results are as follows: - Proofs. We present new constructions of private constrained PRFs and lockable obfuscation, for constraints (resp. functions to be obfuscated) that are computable by general branching programs. Our constructions are secure under LWE with subexponential approximation factors. Previous constructions of this kind crucially rely on the permutation structure of the underlying branching programs. Using general branching programs allows us to obtain more efficient constructions for certain classes of constraints (resp. functions), while posing new challenges in the proof, which we overcome using new proof techniques. - Attacks. We extend the previous attacks on indistinguishability obfuscation (iO) candidates that use GGH15 encodings. The new attack simply uses the rank of a matrix as the distinguisher, so we call it a “rank attack”. The rank attack breaks, among others, the iO candidate for general read-once branching programs by Halevi, Halevi, Shoup and Stephens-Davidowitz (CCS 2017). - Candidates. Drawing upon insights from our proofs and attacks, we present simple candidates for witness encryption and iO that resist the existing attacks, using GGH15 encodings. Our candidate for witness encryption crucially exploits the fact that formulas in conjunctive normal form (CNFs) can be represented by general, read-once branching programs.

ePrint: https://eprint.iacr.org/2018/360

Talk: https://www.youtube.com/watch?v=J4ISwRxeUGY

Slides: https://crypto.iacr.org/2018/slides/GGH15%20Beyond%20Permutation%20Branching%20Programs%20Proofs,%20Attacks,%20and%20Candidates.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .