Cryptology ePrint Archive: Report 2018/756

Obfuscation Using Tensor Products

Craig Gentry and Charanjit S. Jutla

Abstract: 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. In a generic colored matrix model our construction leads to a virtual-black-box obfuscator for NC$^1$ circuits.

Category / Keywords:

Date: received 16 Aug 2018, last revised 23 Aug 2018

Contact author: csjutla at us ibm com

Available format(s): PDF | BibTeX Citation

Note: Fixed minor typos.

Version: 20180823:143551 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]