nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Breaking the Circuit Size Barrier for Secure Computation Under DDH

verfasst von : Elette Boyle, Niv Gilboa, Yuval Ishai

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. More concretely, there is an evaluation algorithm \(\mathsf{Eval}\) with a single bit of output, such that if an input \(w\in \{0,1\}^n\) is shared into \((w^0,w^1)\), then for any deterministic branching program P of size S we have that \(\mathsf{Eval}(P,w^0)\oplus \mathsf{Eval}(P,w^1)=P(w)\) except with at most \(\delta \) failure probability. The running time of the sharing algorithm is polynomial in n and the security parameter \(\lambda \), and that of \(\mathsf{Eval}\) is polynomial in \(S,\lambda \), and \(1/\delta \). This applies as a special case to boolean formulas of size S or boolean circuits of depth \(\log S\). We also present a public-key variant that enables homomorphic computation on inputs contributed by multiple clients.

The above result implies the following DDH-based applications:

A secure 2-party computation protocol for evaluating any branching program or formula of size S, where the communication complexity is linear in the input size and only the running time grows with S.
A secure 2-party computation protocol for evaluating layered boolean circuits of size S with communication complexity \(O(S/\log S)\).
A 2-party function secret sharing scheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability).
A 1-round 2-server private information retrieval scheme supporting general searches expressed by branching programs.

Prior to our work, similar results could only be achieved using fully homomorphic encryption. We hope that our approach will lead to more practical alternatives to known fully homomorphic encryption schemes in the context of low-communication secure computation.

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 The Magic of ELFs

Nächstes Kapitel Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case

In the homomorphic encryption for branching programs from [25] (see also [26]), the size of the encrypted output must grow with the length of the branching program. When simulating a boolean formula by a branching program, the length of the branching program is typically comparable to the formula size.

While one can always switch between the notions by changing the definition of \(\mathcal F\), for classes \(\mathcal F\) that contain universal functions [13, 35] the switch can be done with polynomial overhead without changing \(\mathcal F\). This will be the case for all function classes considered in this work.

In fact, our construction can handle a larger class of arithmetic branching programs over the integers, but correctness only holds as long as all integers involved in intermediate computations are bounded by some fixed polynomial.

Ideally, such a sparse subset would include each \(g\in \mathbb {G}\) independently with probability \(\delta \). To emulate this efficiently we include each \(g\in \mathbb {G}\) in \(\mathbb {G}'\) if \(\phi (g)=0^{\lceil \log 1/\delta \rceil }\), where \(\phi \) is a pseudorandom function.

Here we assume that the events of error in different instances of \(\mathsf{Eval}\) are independent. This can be enforced by using a fresh set of pseudorandom values for each share conversion.

Using sketching or coding techniques (e.g., [18, 32]), this approach can be extended to recovery of data entries satisfying a hidden predicate.

Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)CrossRef

Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share conversion and private information retrieval. In: Proceedings of CCC, pp. 258–268 (2012)

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Proceedings of STOC, pp. 1–10 (1988)

Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)CrossRef

Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008)CrossRef

Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337–367. Springer, Heidelberg (2015)

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: Proceedigs of STOC, pp. 11–19 (1988)

Chor, B., Gilboa, N.: Computationally private information retrieval (extended abstract). In: Proceedings of 29th Annual ACM Symposium on the Theory of Computing, pp. 304–313 (1997)

10.

Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. IACR Cryptology ePrint Archive 1998:3 (1998)

11.

Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)MathSciNetCrossRefMATH

12.

Clear, M., McGoldrick, C.: Multi-identity and multi-key leveled fhe from learning with errors. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 630–656. Springer, Heidelberg (2015)CrossRef

13.

Cook, S.A., Hoover, H.J.: A depth-universal circuit. SIAM J. Comput. 14(4), 833–839 (1985)MathSciNetCrossRefMATH

14.

Cramer, R., Damgård, I.B., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005)CrossRef

15.

Dodis, Y., Halevi, S., Rothblum, R.D., Wichs, D.: Spooky encryption and its applications. IACR Cryptology ePrint Archive, 2016:272 (2016). To appear in Crypto 2016

16.

Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Proceedings of STOC, pp. 39–44 (2009)

17.

Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M.J., Wright, R.N.: Secure multiparty computation of approximations. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 927–938. Springer, Heidelberg (2001)CrossRef

18.

Finiasz, M., Ramchandran, K.: Private stream search at the same communication cost as a regularsearch: role of LDPC codes. In: Proceedings of ISIT, pp. 2556–2560 (2012)

19.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of STOC, pp. 169–178 (2009)

20.

Gentry, C., Groth, J., Ishai, Y., Peikert, C., Sahai, A., Smith, A.D.: Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs. J. Cryptol. 28(4), 820–843 (2015)MathSciNetCrossRefMATH

21.

Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013)CrossRef

22.

Gilboa, N., Ishai, Y.: Distributed point functions and their applications. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 640–658. Springer, Heidelberg (2014)CrossRef

23.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of STOC, pp. 218–229 (1987)

24.

Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 641–670. Springer, Heidelberg (2015)

25.

Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007)CrossRef

26.

Kiayias, A., Leonardos, N., Lipmaa, H., Pavlyk, K., Tang, Q.: Optimal rate private information retrieval from homomorphic encryption. PoPETs 2015(2), 222–243 (2015)MATH

27.

Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: Proceedings of FOCS 1997, pp. 364–373 (1997)

28.

López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of STOC 2012, pp. 1219–1234 (2012)

29.

Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 735–763. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_26 CrossRef

30.

Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: Proceedings of STOC, pp. 590–599 (2001)

31.

Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: Proceedings of FOCS, pp. 458–467 (997)

32.

Ostrovsky, R., Skeith III, W.E.: Private searching on streaming data. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 223–240. Springer, Heidelberg (2005)CrossRef

33.

Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–179. Academic, New York (1978)

34.

Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inf. Theory 42(6), 1723–1731 (1996)MathSciNetCrossRefMATH

35.

Valiant, L.G.: Universal circuits (preliminary report). In: Proceedings of STOC 1976, pp. 196–203 (1976)

36.

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)CrossRef

37.

van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)MathSciNetCrossRefMATH

38.

Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: Proceedings of FOCS, pp. 162–167 (1986)

39.

Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: Proceedings of STOC, pp. 266–274 (2007)

Titel: Breaking the Circuit Size Barrier for Secure Computation Under DDH
verfasst von: Elette Boyle
Niv Gilboa
Yuval Ishai
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – CRYPTO 2016
Print ISBN: 978-3-662-53017-7

Electronic ISBN: 978-3-662-53018-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53018-4_19

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"