Paper 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.