Paper 2017/104

Implementing BP-Obfuscation Using Graph-Induced Encoding

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


We implemented (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. To be able to handle anything more than just toy problems, we developed a host of algorithmic and code-level optimizations. These include new variants of discrete Gaussian sampler and lattice trapdoor sampler, efficient matrix-manipulation routines, and many tradeoffs. We expect that these optimizations will find other uses in lattice-based cryptography beyond just obfuscation. Our implementation is the first obfuscation attempt using the GGH15 graded encoding scheme, offering performance advantages over other graded encoding methods when obfuscating finite-state machines with many states. In out most demanding setting, we were able to obfuscate programs with input length of 20 nibbles (80 bits) and over 100 states, which seems out of reach for prior implementations. Although further optimizations are surely possible, we do not expect any implementation of current schemes to be able to handle much larger parameters.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ACM-CCS 2017
ImplementationMultilinear MapsObfuscationTrapdoor Lattice Sampling
Contact author(s)
shaih @ alum mit edu
2017-09-23: last of 2 revisions
2017-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Tzipora Halevi and Victor Shoup and Noah Stephens-Davidowitz},
      title = {Implementing BP-Obfuscation Using Graph-Induced Encoding},
      howpublished = {Cryptology ePrint Archive, Paper 2017/104},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.