Cryptology ePrint Archive: Report 2017/104

Implementing BP-Obfuscation Using Graph-Induced Encoding

Shai Halevi and Tzipora Halevi and Victor Shoup and Noah Stephens-Davidowitz

Abstract: We implementated (a simplified version of) the branching-program obfuscator due to Gentry et al.\@ (GGH15), which is itself a variation of the first obfuscation candidate by Garg et al. (GGHRSW13). To keep within the realm of feasibility, we had to give up on some aspects of the construction, specifically the ``multiplicative bundling'' factors that protect against mixed-input attacks. Hence our implementation can only support read-once branching programs.

Our implementation is the first obfuscation attempt using the GGH15 graded encoding scheme, and it may offer performance advantages over implementations that use GGH13 or CLT13, especially for obfuscating finite-state machines with many states. For example we were able to obfuscate programs with input length of 17 nibbles (68 bits) and over 100 states, which seems out of reach for prior implementations.

Being able to reach these parameters required a host of algorithmic and code-level optimizations, including new variants of a discrete Gaussian sampler, lattice trapdoor sampler, efficient matrix-manipulation routines, and many tradeoffs. Although further optimizations are of course possible, we do not expect any implementation of current schemes to be able to handle much larger parameters.

Category / Keywords: implementation / Graded encoding, Obfuscation

Date: received 9 Feb 2017

Contact author: shaih at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20170213:193938 (All versions of this report)

Short URL: ia.cr/2017/104

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]