Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Depth-Robust Graphs and Their Cumulative Memory Complexity Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Cryptanalyses of Candidate Branching Program Obfuscators

Authors : Yilei Chen, Craig Gentry, Shai Halevi

Published in: Advances in Cryptology – EUROCRYPT 2017

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
next chapter Quantum Authentication and Encryption with Key Recycling
Footnotes
1
The scalar \(\eta \) is denoted h in [21], but we are already using h for the length of the branching program.
 
2
Having \(\mathsf {rank}( \mathbf {A} )>\mathsf {rank}( \mathbf {B} ) \pmod {g}\) does not always mean that \(\det ( \mathbf {B} )\) is divisible by a higher power of g than \(\det ( \mathbf {A} )\), since \( \mathbf {A} \) could have one eigenvalue which is divisible by a high power of g, e.g., consider \( \mathbf {A} =\left[ \begin{array}{cc}g^5&{}0\\ 0&{}1\end{array}\right] \) and \( \mathbf {B} =\left[ \begin{array}{cc}g&{}0\\ 0&{}g\end{array}\right] \). For our “random matrices”, however, this is unlikely, as confirmed by our experiments.
 
3
We remark that this step of finding (the multiplicity of) an eigenvalue does not seem to fit in the “Weak Multilinear Map” model of Garg et al. [24].
 
4
With typical parameters it is sufficient to use only four different \(z^{(j)}\)’s for that purpose.
 
5
This heuristic argument is similar to the one used for the multi-variate Coppersmith attack [15].
 
6
While the PIP solver will succeed in finding the prime \(\zeta _k\)’s, it will likely fail when applied to factors of the non-prime \(\zeta _k\)’s (since those are unlikely to be principal and/or very small).
 
Literature
1.
Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48523-6_​1
2.
Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 153–178. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53018-4_​6 CrossRef
3.
Ananth, P., Gupta, D., Ishai, Y., Sahai, A.: Optimizing obfuscation: avoiding Barrington’s theorem. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pp. 646–658. ACM (2014)
4.
Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 308–326. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​15 CrossRef
5.
Apon, D., Döttling, N., Garg, S., Mukherjee, P.: Cryptanalysis of indistinguishability obfuscations of circuits over GGH13. Cryptology ePrint Archive, report 2016/1003 (2016)
6.
7.
Badrinarayanan, S., Miles, E., Sahai, A., Zhandry, M.: Post-zeroizing obfuscation: new mathematical tools, and the case of evasive circuits. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 764–791. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​27 CrossRef
8.
Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 221–238. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​13 CrossRef
9.
Biasse, J.-F., Fieker, C.: Subexponential class group, unit group computation in large degree number fields. LMS J. Comput. Math. 17(A), 385–403 (2014)MathSciNetCrossRefMATH
10.
Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 893–902. SIAM (2016)
11.
Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: FOCS, pp. 171–190. IEEE Computer Society (2015)
12.
Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 1–25. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​1 CrossRef
13.
Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​1
14.
Cheon, J.H., Jeong, J., Lee, C.: An algorithm for CSPR problems and cryptanalysis of the GGH multilinear map without an encoding of zero. To be appear at ANTS (2016)
15.
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH
16.
Coron, J.-S., et al.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 247–266. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​12 CrossRef
17.
Coron, J.-S., Lee, M.S., Lepoint, T., Tibouchi, M.: Cryptanalysis of GGH15 multilinear maps. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 607–628. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53008-5_​21 CrossRef
18.
Coron, J.-S., Lee, M.S., Lepoint, T., Tibouchi, M.: Zeroizing attacks on indistinguishability obfuscation over CLT13. To be appear at PKC 2017. Cryptology ePrint Archive, report 2016/1011 (2016)
19.
20.
Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​20 CrossRef
21.
22.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013)
23.
Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Functional encryption without obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 480–511. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​18 CrossRef
24.
Garg, S., Miles, E., Mukherjee, P., Sahai, A., Srinivasan, A., Zhandry, M.: Secure obfuscation in a weak multilinear map model. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 241–268. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53644-5_​10 CrossRef
25.
Garg, S., Mukherjee, P., Srinivasan, A.: Obfuscation without the vulnerabilities of multilinear maps. Technical report (2016)
26.
27.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In: IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 151–170. IEEE (2015)
28.
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
29.
Halevi, S.: Graded encoding, variations on a scheme. Cryptology ePrint Archive, report 2015/866 (2015)
30.
Lenstra, A.K., Lenstra, H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: STOC, pp. 564–572. ACM (1990)
31.
Lin, H.: Indistinguishability obfuscation from constant-degree graded encoding schemes. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 28–57. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​2 CrossRef
32.
Lin, H., Vaikuntanathan, V.: Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In: FOCS, pp. 11–20. IEEE Computer Society (2016)
33.
Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​41 CrossRef
34.
Miles, E., Sahai, A., Weiss, M.: Protecting obfuscation against arithmetic attacks. IACR Cryptology ePrint Archive 2014:878 (2014)
35.
Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 629–658. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53008-5_​22 CrossRef
36.
Miles, E., Sahai, A., Zhandry, M.: Secure obfuscation in a weak multilinear map model: a simple construction secure against all known attacks. IACR Cryptology ePrint Archive 2016, 588 (2016)
37.
Pass, R., Seth, K., Telang, S.: Indistinguishability obfuscation from semantically-secure multilinear encodings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 500–517. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44371-2_​28 CrossRef
38.
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)MathSciNetCrossRefMATH
39.
Metadata
Title
Cryptanalyses of Candidate Branching Program Obfuscators
Authors
Yilei Chen
Craig Gentry
Shai Halevi
Copyright Year
2017
Book
Advances in Cryptology – EUROCRYPT 2017

Print ISBN: 978-3-319-56616-0

Electronic ISBN: 978-3-319-56617-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-56617-7_10

Premium Partner

    Image Credits