Cryptology ePrint Archive: Report 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$.

Category / Keywords: Cryptanalysis, obfuscation, multilinear maps, approximate eigenvalue, determinant estimate

Date: received 28 Nov 2017, last revised 22 Dec 2017

Contact author: chunsheng_gu at 163 com

Available format(s): PDF | BibTeX Citation

Note: Added some details.

Version: 20171223:014927 (All versions of this report)

Short URL: ia.cr/2017/1159


[ Cryptology ePrint archive ]