In our work, we build the first core obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian’s statistical simulation theorem. Furthermore, our obfuscator achieves two other notable advances over previous work:
- Our construction allows for non-square matrices of arbitrary dimensions. We also show that this flexibility yields concrete efficiency gains. - Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit of output.
Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains even in applications not directly using obfuscation.Category / Keywords: foundations / obfuscation, branching programs, low rank Date: received 30 Sep 2014, last revised 30 Sep 2014 Contact author: mzhandry at stanford edu Available format(s): PDF | BibTeX Citation Version: 20141001:060633 (All versions of this report) Short URL: ia.cr/2014/773 Discussion forum: Show discussion | Start new discussion