Paper 2017/1159

Cryptanalysis of indistinguishability obfuscation using GGH13 without ideals

Gu Chunsheng

Abstract

Recently, Albrecht, Davidson and Larraia described a variant of the GGH13 without ideals and presented the distinguishing attacks in simplified branching program security model. Their result partially demonstrates that there seems to be a structural defect in the GGH13 encoding that is not related to the ideal $\langle g \rangle$. However, it is not clear whether a variant of the CGH attack described by Chen, Gentry and Halevi can be used to break a branching program obfuscator instantiated by GGH13 without ideals. Consequently this is left as an open problem by Albrecht, Davidson and Larraia. In this paper, we describe a variant of the CGH attack which breaks the branching program obfuscator using GGH13 without ideals. To achieve this goal, we introduce matrix approximate eigenvalues and build a relationship between the determinant and the rank of a matrix with noise. Our result further strengthens the work of Albrecht, Davidson and Larraia that there is a structural weakness in `GGH13-type' encodings beyond the presence of $\langle g \rangle$.

Note: Added some details.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Cryptanalysisobfuscationmultilinear mapsapproximate eigenvaluedeterminant estimate
Contact author(s)
chunsheng_gu @ 163 com
History
2017-12-23: revised
2017-11-29: received
See all versions
Short URL
https://ia.cr/2017/1159
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1159,
      author = {Gu Chunsheng},
      title = {Cryptanalysis of indistinguishability obfuscation using GGH13 without ideals},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1159},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1159}},
      url = {https://eprint.iacr.org/2017/1159}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.