nach oben

Journal of Cryptology

Erschienen in:

01.04.2021

Obfuscating Circuits Via Composite-Order Graded Encoding

verfasst von: Benny Applebaum, Zvika Brakerski

Erschienen in: Journal of Cryptology | Ausgabe 2/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We present a candidate obfuscator based on composite-order graded encoding schemes (GES), which are a generalization of multilinear maps. Our obfuscator operates on circuits directly without converting them into formulas or branching programs as was done in previous solutions. As a result, the time and size complexity of the obfuscated program, measured by the number of GES elements, is directly proportional to the circuit complexity of the program being obfuscated. This improves upon previous constructions whose complexity was related to the formula or branching program size. Known instantiations of Graded Encoding Schemes allow us to obfuscate circuit classes of polynomial degree, which include for example families of circuits of logarithmic depth. We prove that our obfuscator is secure against a class of generic algebraic attacks, formulated by a generic graded encoding model. We further consider a more robust model which provides more power to the adversary and extend our results to this setting as well. As a secondary contribution, we define a new simple notion of algebraic security (which was implicit in previous works) and show that it captures standard security relative to an ideal GES oracle.

Vorheriger Artikel Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

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

An alternative way to model a generic attack is to assume that the adversaries is given abstract handles to the encodings. We prefer the current model due to its simplicity and for the sake of consistency with previous works. We futrher note that security in the current (random string) model immediately implies security in the “handle model.” Since our model only gives more power to the adversary and not to the honest user (since correctness should hold even for non-random GES instantiations).

To test if \([g]_{\mathbf {v}}\) is an encoding of zero simply check if the string \([g]_{\mathbf {v}}+[g]_{\mathbf {v}}\) equals to \([g]_{\mathbf {v}}\).

It may be surprising that such tweaking could exist, since one can always increase the level from \(\mathbf {v}\) to \({\mathbf {v}}_{\text {zt}}\) by multiplying with a nonzero element of level \(({\mathbf {v}}_{\text {zt}}-\mathbf {v})\). However, in known instantiations, it is possible to generate public parameters that cannot be used for generating new encodings, thus restricting the adversary to only have access to those levels provided in the obfuscated program. Those, in turn, are designed so there is no way to obtain an encoding at level \(({\mathbf {v}}_{\text {zt}}-\mathbf {v})\) for “dangerous” values of \(\mathbf {v}\). (This is somewhat similar to the “straddling sets” technique [4].)

It is important to emphasize that the honest parties (the obfuscator and evaluator) do not exploit the fact that elements have unique encodings, as they are required to work with respect to any GES implementation. (See Sect. 3). Therefore, the \(\mathcal{URG}\) model is strictly better than the \(\mathcal{MRG}\) model in the sense that an obfuscation which is secure relatively to \(\mathcal{URG}\) is also secure relatively to \(\mathcal{MRG}\). The reverse direction does not necessarily hold as demonstrated by \({\mathsf {SimpleObf}}\) from Theorem 1.1.

The difference between \(\mathcal{URG}\) and \(\mathcal{MRG}\) will arise by putting different syntactic restrictions on the class of “legal” polynomials A. Furthermore, an efficient simulator corresponds to VBB security while inefficient simulator corresponds to indistinguishability obfuscation.

The above argument is somewhat inaccurate as one has to take into account the case where F is a multiple of \((\hat{\mathcal{U}}(\cdots )-V_0)\). A formal proof appears in Sect. 5.

We focus on the length of the obfuscated program. One could also consider the running time of the obfuscated program, but the two metrics are usually very strongly correlated.

This means that the length of each GES element in either construction scales with \(2^d\). This is quite undesirable and one could hope that future construction will be able to bring it down to \(\mathrm {poly}(d)\), but regardless, it is comparable between the two approaches.

We do not see an obstacle for proving VBB, but it seems more technically involved.

In our security model, we will require that each prime factor of N is chosen from a distribution with roughly \((\Omega ( \log {\Vert {\mathbf {v}}_{\text {zt}}\Vert _1}) + \omega (\log \lambda ))\) bits of entropy. See Sect. 5.

Let us emphasize that this procedure requires \({ p arams}\) and not \({ e vparams}\). This distinction will be important in order to be able to define a security notion that is plausibly achievable by existing candidates. See Remark 2.5.

Polynomial Identity Testing of arithmetic circuit can be done in randomized polynomial time (RP) using Schwartz–Zippel over a sufficiently large field.

We note that the family of all depth-d size-s circuits for some \(s(n)\in \mathrm {poly}(n)\) and \(d(n)\in O(\log n)\) admit a universal evaluation circuit in \({\mathcal {NC}}^1\) of size \(s(n)\cdot 2^{d(n)}\).

Recall that, by convention, we refer to ring elements via their CRT representation.

While this transformation may incur a significant increase in the degree, the depth remains unchanged up to a constant. Therefore, the total degree is at most exponential in the depth of the original Boolean circuit.

In the case of \({\mathsf {SimpleObf}}\) the circuit is actually strictly compatible, but this point will be only used later in Sect. 5.3.

This is the only place in the proof where the admissability of the ring is being used. Correspondingly, admissability can be replaced by any property that guarantees that the coefficient a is a unit in all subrings of \({\mathbb {Z}}_N\), and that the size of the smallest subring of \({\mathbb {Z}}_N\) is at least \({\Vert {\mathbf {v}}_{\text {zt}}\Vert _1}^2 \cdot \lambda ^{\omega (1)}\) (the latter is for the sake of applying Schwartz–Zippel).

P. Ananth, D. Gupta, Y. Ishai, A. Sahai, Optimizing obfuscation: avoiding Barrington’s theorem. Cryptology ePrint Archive, Report 2014/222, 2014. http://eprint.iacr.org/.

B. Applebaum, Bootstrapping obfuscators via fast pseudorandom functions, in Advances in Cryptology—ASIACRYPT 2014 (2014), pp. 162–172

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang. On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012). Preliminary version in CRYPTO 2001

B. Barak, S. Garg, Y.T. Kalai, O. Paneth, A. Sahai, Protecting obfuscation against algebraic attacks. in P.Q. Nguyen, E. Oswald, editors, Advances in Cryptology—EUROCRYPT 2014, vol. 8441 of Lecture Notes in Computer Science (Springer, 2014), pp. 221–238

Z. Brakerski, G.N. Rothblum. Obfuscating conjunctions, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part II, vol. 8043 of Lecture Notes in Computer Science (Springer, 2013), pp. 416–434

Z. Brakerski, G.N. Rothblum, Black-box obfuscation for D-CNFS, in M. Naor, editor, Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12–14, 2014 (ACM, 2014), pp. 235–250

Z. Brakerski, G.N. Rothblum, Virtual black-box obfuscation for all circuits via generic graded encoding, in Y. Lindell, editor, Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24–26, 2014. Proceedings, vol. 8349 of Lecture Notes in Computer Science (Springer, 2014), pp 1–25

J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers, in R. Canetti, J.A. Garay, editors Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I, vol. 8042 of Lecture Notes in Computer Science (Springer, 2013), pp. 476–493

J.A. Garay, R. Gennaro, editors. Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2014, Proceedings, Part I, vol. 8616 of Lecture Notes in Computer Science (Springer, 2014)

10.

S. Garg, C. Gentry, S. Halevi. Candidate multilinear maps from ideal lattices, in T. Johansson, P.Q. Nguyen, editors, Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26–30, 2013. Proceedings, vol. 7881 of Lecture Notes in Computer Science (Springer, 2013), pp. 1–17

11.

S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters. 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, CA, USA (IEEE Computer Society, 2013), pp. 40–49

12.

V. Goyal, Y. Ishai, A. Sahai, R. Venkatesan, A. Wadia. Founding cryptography on tamper-proof hardware tokens, in D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9–11, 2010. Proceedings, vol. 5978 of Lecture Notes in Computer Science (Springer, 2010), pp. 308–326

13.

C. Gentry, A.B. Lewko, A. Sahai, B. Waters. Indistinguishability obfuscation from the multilinear subgroup elimination assumption. IACR Cryptology ePrint Archive, 2014:309, 2014.

14.

C. Gentry, A.B. Lewko, B. Waters, Witness encryption from instance independent assumptions, in Garay and Gennaro [GG14], pp. 426–443. References are respective to the ePrint version: https://eprint.iacr.org/2014/273

15.

U. Maurer, Abstract models of computation in cryptography, in N.P. Smart, editor, IMA Int. Conf., vol. 3796 of Lecture Notes in Computer Science (Springer, 2005), pp. 1–12

16.

R. Pass, K. Seth, S. Telang, Indistinguishability obfuscation from semantically-secure multilinear encodings. In Garay and Gennaro [GG14], pp. 500–517

17.

J. Schwartz, Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(2):701–717, 1980

18.

V. Shoup. Lower bounds for discrete logarithms and related problems, in W. Fumy, editor, EUROCRYPT, vol. 1233 of Lecture Notes in Computer Science (Springer, 1997), pp. 256–266

19.

J. Zimmerman, How to obfuscate programs directly. Cryptology ePrint Archive, Report 2014/776, 2014. Appeared in Eurocrypt 2015 [?]

20.

R. Zippel, Probabilistic algorithms for sparse polynomials, in International Symposiumon on Symbolic and Algebraic Computation (1979), pp. 216–226

Titel: Obfuscating Circuits Via Composite-Order Graded Encoding
verfasst von: Benny Applebaum
Zvika Brakerski
Publikationsdatum: 01.04.2021
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2021
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-021-09378-z

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"

Weitere Artikel der Ausgabe 2/2021

Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

On the Local Leakage Resilience of Linear Secret Sharing Schemes

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

Tight Tradeoffs in Searchable Symmetric Encryption

Premium Partner