Paper 2018/756

Obfuscation Using Tensor Products

Craig Gentry, Charanjit S. Jutla, and Daniel Kane

Abstract

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix groups 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. We also provide cryptanalysis based on computing tangent spaces of the underlying algebraic sets.

Note: Brought back a lemma on rank one matrices from an earlier version and fixed some typos.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
csjutla @ us ibm com
History
2019-02-22: last of 5 revisions
2018-08-20: received
See all versions
Short URL
https://ia.cr/2018/756
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/756,
      author = {Craig Gentry and Charanjit S.  Jutla and Daniel Kane},
      title = {Obfuscation Using Tensor Products},
      howpublished = {Cryptology ePrint Archive, Paper 2018/756},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/756}},
      url = {https://eprint.iacr.org/2018/756}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.