For GGHRSW over GGH13, we show how to recover the ideal generating the plaintext space when the branching program has input partitioning. Combined with the information that we extract about the ``multiplicative bundling'' scalars, we get a distinguishing attack by an extension of the annihilation attack of Miles, Sahai and Zhandry. Alternatively, once we have the ideal we can solve the principle-ideal problem (PIP) in classical subexponential time or quantum polynomial time, hence obtaining a total break.
For the variant over GGH15, we show how to use the left-kernel technique of Coron, Lee, Lepoint and Tibouchi to recover ratios of the bundling scalars. Once we have the ratios of the scalar products, we can use factoring and PIP solvers (in classical subexponential time or quantum polynomial time) to find the scalars themselves, then run mixed-input attacks to break the obfuscation.Category / Keywords: Cryptanalysis, Graded-Encoding, Obfuscation Original Publication (in the same form): IACR-EUROCRYPT-2017 Date: received 17 Oct 2016, last revised 17 Feb 2017 Contact author: chenyl at bu edu, craigbgentry@gmail com, shaih@alum mit edu Available format(s): PDF | BibTeX Citation Version: 20170217:130725 (All versions of this report) Short URL: ia.cr/2016/998 Discussion forum: Show discussion | Start new discussion