Paper 2017/321
How Fast Can We Obfuscate Using Ideal Graded Encoding Schemes
Dingfeng Ye, Peng Liu, and Jun Xu
Abstract
In this work, we present a new obfuscator using a Graded Encoding Scheme (GES) with a binary slot. We characterize a class of circuits taking locally keyed input (each input bit of the circuit is a keyed function over c>1 bits of a binaryvariable vector X of length n, where c is called the locality), called ideal functions, such that any function of algebraic degree d (called dfunction) over them, can be obfuscated with multilinearity \mu=(d+1)n/c. Next we show that obfuscation of a general circuit C can be bootstrapped by O(n)functions (the circuit (called RE) composing a garbled circuit (GC) with a pseudorandom function (PRF)), following an approach similar to that of Zimmerman and Applebaum et al., assuming PRF (or more precisely RE) exists among dfunctions with constant d. To instantiate the above scheme, we achieve the following: 1. A concrete GC of algebraic degree 3 over its random bits, which has output size no more than 20\lambdaC and random tape length about 10\lambdaC, where \lambda is the security parameter, C denotes the number of gates of the circuit C. 2. A candidate dfunction construction, where we argue that d=1 suffices to stop linear distinguishing attacks and d=2 seems enough for fully secure PRF. 3. Instantiation of the GES with a simplified version of the CLT multilinear map, and various techniques that further reduce \mu of the core obfuscator costequivalently to dn/(2c)+1 in cases of our interest. If we replace the PRF with dfunctions, then we get various heuristic obfuscationfriendly REs, and thus general obfuscators with explicit complexities. For the most optimistic choice, we have \mu=1.5n'/c +2.5, n'\approx n+\log C+\log \lambda, n is the number of input bits of C, and c is a selectable constant which result in a {2^c}/{c} times increase of the key size of the RE. Our general obfuscator is VBB secure assuming that our RE is secure and our simplified CLT map is a secure instantiation of our GES (defined relative to known attacks). We leave these assumptions with concrete parameter sets as open challenges. We illustrate the efficiency of our methods with some examples: 1. Our obfuscated AES (c=13, \mu=20.5) has code size <1.5\times 10^{17} bits, whereas no implementable solution is known prior to this work. 2. We can practically obfuscate conjunction functions for n=64, while the latest implementation can only handle n=32 with comparable resources. We also verify the security against algebraic attacks in this example.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Obfuscationgarbled circuitspseudorandom functionsgraded encoding schemeCLT map
 Contact author(s)

ydf @ is ac cn
pliu @ ist psu edu
xujun @ iie ac cn  History
 20180511: last of 2 revisions
 20170414: received
 See all versions
 Short URL
 https://ia.cr/2017/321
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/321, author = {Dingfeng Ye and Peng Liu and Jun Xu}, title = {How Fast Can We Obfuscate Using Ideal Graded Encoding Schemes}, howpublished = {Cryptology ePrint Archive, Paper 2017/321}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/321}}, url = {https://eprint.iacr.org/2017/321} }