nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Sum-of-Squares Meets Program Obfuscation, Revisited

verfasst von : Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We develop attacks on the security of variants of pseudo-random generators computed by quadratic polynomials. In particular we give a general condition for breaking the one-way property of mappings where every output is a quadratic polynomial (over the reals) of the input. As a corollary, we break the degree-2 candidates for security assumptions recently proposed for constructing indistinguishability obfuscation by Ananth, Jain and Sahai (ePrint 2018) and Agrawal (ePrint 2018). We present conjectures that would imply our attacks extend to a wider variety of instances, and in particular offer experimental evidence that they break assumption of Lin-Matt (ePrint 2018).

Our algorithms use semidefinite programming, and in particular, results on low-rank recovery (Recht, Fazel, Parrilo 2007) and matrix completion (Gross 2009).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and Instantiation

Nächstes Kapitel How to Leverage Hardness of Constant-Degree Expanding Polynomials over to build

Nur mit Berechtigung zugänglich

The work of Ananth, Jain, and Sahai [2] also considered degree-3 polynomials. We do not have attacks on such degree-3 polynomials; we discuss this further below.

This cubic version of their assumption was made explicit in an update to [2].

Along the same lines, we note that if $\mathcal Q$ is nice and ${\mathbb {E}}_{q \sim \mathcal Q} q = 0$ (as we observe later, the latter can be enforced without loss of generality) then $\mathcal Q$ is also $\varLambda (n)$-bounded for $\varLambda (n) \leqslant O(n)$. The reason is that if $\mathcal Q$ is nice and has ${\mathbb {E}}\, q = 0$ then

$$ {\mathbb {E}}\Vert q\Vert ^2 = \sum _{i,j \leqslant n} {\mathbb {E}}\, Q_{ij}^2 = \sum _{i,j \leqslant n} Var(Q_{ij}) = n^2\,.$$

For every i, j and every q in the support of $\mathcal Q$, we have by niceness that $|q_{ij}| \leqslant \Vert q\Vert _2 \leqslant C n$. Hence $\mathcal Q$ is O(n)-bounded.

One implication is that $\mathcal Q$ cannot be a distribution on where the all-zero polynomial appears with probability, say, $1-1/n$, as otherwise its support would also have to contain polynomials with coefficients $\gg n$. Our main theorem could not apply to such a distribution, since clearly at least $\varOmega (n^2)$ independent samples would be needed to get enough information to recover x from $\{q_i,q_i(x)\}$, while we assume $m \leqslant n(\log n)^{O(1)} \ll n^2$.

For any $q(x) = \sum _{i,j}q_{i\leqslant j} x_i x_j$, we define $Q:\mathbb R^{n\times n}\rightarrow \mathbb R$ by $Q_{i,j} = Q_{j,i}= q_{i,j}/2$. Then,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17653-2_8/480582_1_En_8_IEq226_HTML.gif

is a linear map on $\mathbb R^{n \times n}$.

Agrawal, S.: New methods for indistinguishability obfuscation: Bootstrapping and instantiation. IACR Cryptology ePrint Archive 2018, 633 (2018). https://eprint.iacr.org/2018/633

Ananth, P., Jain, A., Sahai, A.: Indistinguishability obfuscation without multilinear maps: iO from LWE, bilinear maps, and weak pseudorandomness. IACR Cryptology ePrint Archive 2018, 615 (2018). https://eprint.iacr.org/2018/615

Ananth, P., Sahai, A.: Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 152–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_6CrossRef

Barak, B., Brakerski, Z., Komargodski, I., Kothari, P.K.: Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation). In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 649–679. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_21CrossRef

Boneh, D., Silverberg, A.: Applications of multilinear forms to cryptography. Contemp. Math. 324, 71–90 (2002)MathSciNetCrossRef

Boneh, D., Wu, D.J., Zimmerman, J.: Immunizing multilinear maps against zeroizing attacks. IACR Cryptology ePrint Archive 2014, 930 (2014). http://eprint.iacr.org/2014/930

Brakerski, Z., Gentry, C., Halevi, S., Lepoint, T., Sahai, A., Tibouchi, M.: Cryptanalysis of the quadratic zero-testing of GGH. Cryptology ePrint Archive, Report 2015/845 (2015). http://eprint.iacr.org/

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, Part I. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_1CrossRef

Cheon, J.H., Lee, C., Ryu, H.: Cryptanalysis of the new clt multilinear maps. Cryptology ePrint Archive, Report 2015/934 (2015). http://eprint.iacr.org/

10.

Coron, J.-S., et al.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 247–266. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_12CrossRef

11.

Daniely, A., Linial, N., Shalev-Shwartz, S.: From average case complexity to improper learning complexity. In: STOC, pp. 441–448. ACM (2014)

12.

Feige, U.: Relations between average case complexity and approximation complexity. In: STOC, pp. 534–543. ACM (2002)

13.

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_1CrossRef

14.

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October, 2013, Berkeley, pp. 40–49 (2013)

15.

Grigoriev, D.: Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259(1–2), 613–622 (2001)MathSciNetCrossRef

16.

Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theory 57(3), 1548–1566 (2011). https://doi.org/10.1109/TIT.2011.2104999MathSciNetCrossRefMATH

17.

Halevi, S.: Graded encoding, variations on a scheme. IACR Cryptol. ePrint Archive 2015, 866 (2015)

18.

Hu, Y., Jia, H.: Cryptanalysis of GGH map. IACR Cryptol. ePrint Archive 2015, 301 (2015)MATH

19.

Lin, H.: Indistinguishability obfuscation from constant-degree graded encoding schemes. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 28–57. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_2CrossRef

20.

Lin, H.: Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 599–629. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_20CrossRef

21.

Lin, H., Matt, C.: Pseudo flawed-smudging generators and their application to indistinguishability obfuscation. IACR Cryptology ePrint Archive 2018, 646 (2018). https://eprint.iacr.org/2018/646

22.

Lin, H., Tessaro, S.: Indistinguishability obfuscation from bilinear maps and block-wise local PRGs. Cryptology ePrint Archive, Report 2017/250 (2017). http://eprint.iacr.org/2017/250

23.

Lin, H., Vaikuntanathan, V.: Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9–11 October 2016, Hyatt Regency, New Brunswick, pp. 11–20 (2016)

24.

Lombardi, A., Vaikuntanathan, V.: On the non-existence of blockwise 2-local prgs with applications to indistinguishability obfuscation. IACR Cryptology ePrint Archive 2017, 301 (2017). http://eprint.iacr.org/2017/301

25.

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, Part II. LNCS, vol. 9815, pp. 629–658. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_22CrossRef

26.

Minaud, B., Fouque, P.A.: Cryptanalysis of the new multilinear map over the integers. Cryptology ePrint Archive, Report 2015/941 (2015). http://eprint.iacr.org/

27.

Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413–3430 (2011)MathSciNetMATH

28.

Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions oflinear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010). https://doi.org/10.1137/070697835MathSciNetCrossRefMATH

29.

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, New York, May 31 - June 03, 2014, pp. 475–484 (2014)

30.

Schoenebeck, G.: Linear level lasserre lower bounds for certain k-CSPs. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, 25–28 October 2008, Philadelphia, pp. 593–602 (2008)

Titel: Sum-of-Squares Meets Program Obfuscation, Revisited
verfasst von: Boaz Barak
Samuel B. Hopkins
Aayush Jain
Pravesh Kothari
Amit Sahai
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17652-5

Electronic ISBN: 978-3-030-17653-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17653-2_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner