Cryptology ePrint Archive: Report 2017/1159

Cryptanalysis of indistinguishability obfuscation using GGH13 without ideals

Gu Chunsheng

Abstract: Recently, Albrecht, Davidson, Larraia, and Pellet-Mary constructed a variant of the GGH13 without ideals and presented the distinguishing attacks in simplified branching program and obfuscation security models. However, it is not clear whether a variant of the CGH annihilation attack can be used to break an IO candidate using this new variant. This paper adaptively extends the CGH attack into the branch program obfuscator based on GGH13 without ideals. To achieve this goal, we introduce approximate eigenvalue of matrix and build a relationship between the determinant and the rank of a matrix with perturbation. Our result shows that the structural vulnerability of GGH13 encodings are beyond the presence of ideal.

Category / Keywords:

Date: received 28 Nov 2017

Contact author: chunsheng_gu at 163 com

Available format(s): PDF | BibTeX Citation

Version: 20171129:155546 (All versions of this report)

Short URL: ia.cr/2017/1159

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]