Paper 2016/998

Cryptanalyses of Candidate Branching Program Obfuscators

Yilei Chen, Craig Gentry, and Shai Halevi

Abstract

We describe new cryptanalytic attacks on the candidate branching program obfuscator proposed by Garg, Gentry, Halevi, Raykova, Sahai and Waters (GGHRSW) using the GGH13 graded encoding, and its variant using the GGH15 graded encoding as specified by Gentry, Gorbunov and Halevi. All our attacks require very specific structure of the branching programs being obfuscated, which in particular must have some input-partitioning property. Common to all our attacks are techniques to extract information about the ``multiplicative bundling'' scalars that are used in the GGHRSW construction. 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in Eurocrypt 2017
Keywords
CryptanalysisGraded-EncodingObfuscation
Contact author(s)
chenyl @ bu edu
craigbgentry @ gmail com
shaih @ alum mit edu
History
2017-02-17: last of 2 revisions
2016-10-20: received
See all versions
Short URL
https://ia.cr/2016/998
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/998,
      author = {Yilei Chen and Craig Gentry and Shai Halevi},
      title = {Cryptanalyses of Candidate Branching Program Obfuscators},
      howpublished = {Cryptology ePrint Archive, Paper 2016/998},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/998}},
      url = {https://eprint.iacr.org/2016/998}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.