Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-149 | 25th August 2018 05:45

Obfuscation using Tensor Products


Authors: Craig Gentry, Charanjit Jutla
Publication: 26th August 2018 07:35
Downloads: 206


We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove that there is no efficient attack on our scheme based on re-linearization techniques of Kipnis-Shamir (CRYPTO 99) and its generalization called XL-methodology (Courtois et al, EC2000). We also provide analysis to claim that general Grobner-basis computation attacks will be inefficient. For a polynomial ring R we formulate a notion of efficient R-linear computations suitable for Grobner-basis based elimination. We also formulate a new "one-more masked tensor" problem and analyze its arithmetic-circuit complexity.

In a generic colored matrix model our construction leads to a virtual-black-box obfuscator for NC$^1$ circuits.

ISSN 1433-8092 | Imprint