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
-
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},
url = {https://eprint.iacr.org/2017/1159}
}
