Paper 2017/104

Implementing BP-Obfuscation Using Graph-Induced Encoding

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ACM-CCS 2017
Keywords
ImplementationMultilinear MapsObfuscationTrapdoor Lattice Sampling
Contact author(s)
shaih @ alum mit edu
History
2017-09-23: last of 2 revisions
2017-02-13: received
See all versions
Short URL
https://ia.cr/2017/104
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/104,
      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{https://eprint.iacr.org/2017/104}},
      url = {https://eprint.iacr.org/2017/104}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.