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)
- 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
-
CC BY