You are looking at a specific version 20170213:193938 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Graded encodingObfuscation
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.