Cryptology ePrint Archive: Report 2018/360

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

Yilei Chen and Vinod Vaikuntanathan and Hoeteck Wee

Abstract: 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.

Category / Keywords: Graded encodings

Date: received 16 Apr 2018, last revised 17 Apr 2018

Contact author: chenyilei ra at gmail com, vinodv at csail mit edu, wee at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20180418:203509 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]