nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Homomorphic Secret Sharing from Paillier Encryption

verfasst von : Nelly Fazio, Rosario Gennaro, Tahereh Jafarikhah, William E. Skeith III

Erschienen in: Provable Security

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

A recent breakthrough by Boyle et al. [7] demonstrated secure function evaluation protocols for branching programs, where the communication complexity is sublinear in the size of the circuit (indeed just linear in the size of the inputs, and polynomial in the security parameter). Their result is based on the Decisional Diffie-Hellman assumption (DDH), using (variants of) the ElGamal cryptosystem. In this work, we extend their result to show a construction based on the circular security of the Paillier encryption scheme. We also offer a few optimizations to the scheme, including an alternative to the “Las Vegas”-style share conversion protocols of [7, 9] which directly checks the correctness of the computation. This allows us to reduce the number of required repetitions to achieve a desired overall error bound by a constant fraction for typical cases, and for large programs, reduces the total computation cost.

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 Public-Key Encryption with Simulation-Based Sender Selective-Opening Security

Nächstes Kapitel Fuzzy Public-Key Encryption Based on Biometric Data

There is no contradiction here with the hardness of discrete log, since this works only for small values of b.

For example in our DCRA-based construction, this would be equivalent to decryption.

Differently than in [7] we do not use \(\langle y \rangle \) in the multiplication step – The additive sharing of y however needs to be stored so that we can compute the output at the end.

\(\ell \le t\) since additive shares start of size \(\ell \) and then they can grow as the result of addition operations.

At least the test is efficient if the factorization of the order of the group is known, as is the case if \(n\) was a product of safe primes.

We note that naive polynomial evaluation could also be made reasonable by raising to \(\alpha ^i \bmod n\), since in any abelian group, if \(\prod h_i\in H<G\) with \(|H| = n\), then for any \(k\in \mathbb {Z}\), \((\prod h_i)^k = (\prod h_i)^{k\bmod n} = \prod (h_i^{k\bmod n})\).

Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic agility and its relation to circular encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_21 CrossRef

Alamati, N., Peikert, C.: Three’s compromised too: circular insecurity for any cycle length from (Ring-)LWE. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 659–680. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53008-5_23 CrossRef

Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115–162 (2006)MathSciNetCrossRefMATH

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

Bishop, A., Hohenberger, S., Waters, B.: New circular security counterexamples from decision linear and learning with errors. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 776–800. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48800-3_32 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). doi:10.1007/978-3-662-46803-6_12

Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53018-4_19 CrossRef

Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1292–1303. ACM (2016)

Boyle, E., Gilboa, N., Ishai, Y.: Group-based secure computation: optimizing rounds, communication, and computation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 163–193. Springer, Cham (2017). doi:10.1007/978-3-319-56614-6_6 CrossRef

10.

Cash, D., Green, M., Hohenberger, S.: New definitions and separations for circular security. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 540–557. Springer, Heidelberg (2012). doi:10.1007/978-3-642-30057-8_32 CrossRef

11.

Chaum, D., Crépeau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: Proceedings of the Twentieth Annual ACM symposium on Theory of Computing, pp. 11–19. ACM (1988)

12.

Chor, B., Gilboa, N.: Computationally private information retrieval. In: Proceedings of the Twenty-Ninth Annual ACM symposium on Theory of Computing, pp. 304–313. ACM (1997)

13.

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

14.

Cohen, J.D., Fischer, M.J.: A robust and verifiable cryptographically secure election scheme (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, pp. 372–382, 21–23 October 1985

15.

Damgård, I., Jurik, M.: A length-flexible threshold cryptosystem with applications. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 350–364. Springer, Heidelberg (2003). doi:10.1007/3-540-45067-X_30 CrossRef

16.

Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). doi:10.1007/3-540-44586-2_9 CrossRef

17.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM, New York (2009)

18.

Gentry, C., Halevi, S.: Implementing gentry’s fully-homomorphic encryption scheme. Cryptology ePrint Archive, Report 2010/520 (2010)

19.

Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29011-4_28 CrossRef

20.

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

21.

Goldwasser, S., Micali, S.: Probabilistic encryption. JCSS 28(2), 270–299 (1984)MathSciNetMATH

22.

Goyal, R., Koppula, V., Waters, B.: Separating IND-CPA and circular security for unbounded length key cycles. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 232–246. Springer, Heidelberg (2017). doi:10.1007/978-3-662-54365-8_10 CrossRef

23.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 294–304. IEEE (2000)

24.

Jurik, M.J.: Extensions to the Paillier cryptosystem with applications to cryptological protocols. In: BRICS (2003)

25.

Koppula, V., Waters, B.: Circular security separations for arbitrary length cycles from LWE. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 681–700. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53008-5_24 CrossRef

26.

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

27.

Marcedone, A., Orlandi, C.: Obfuscation \(\Rightarrow \) (IND-CPA security \(\nRightarrow \) circular security). In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 77–90. Springer, Cham (2014). doi:10.1007/978-3-319-10879-7_5

28.

Naccache, D., Stern, J.: A new public key cryptosystem based on higher residues. In: Proceedings of the 5th ACM Conference on Computer and Communications Security, pp. 59–66. ACM (1998)

29.

Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, pp. 113–124. ACM (2011)

30.

Okamoto, T., Uchiyama, S.: A new public-key cryptosystem as secure as factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998). doi:10.1007/BFb0054135

31.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi:10.1007/3-540-48910-X_16

32.

Rothblum, R.D.: On the circular security of bit-encryption. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 579–598. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36594-2_32 CrossRef

33.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRefMATH

34.

Wichs, D., Zirdelis, G.: Obfuscating compute-and-compare programs under LWE. Technical report, Cryptology ePrint Archive, Report 2017/276 (2017). http://eprint.iacr.org/2017/276

35.

Yao, A.C.C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160–164 (1982)

36.

Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167. IEEE (1986)

Titel: Homomorphic Secret Sharing from Paillier Encryption
verfasst von: Nelly Fazio
Rosario Gennaro
Tahereh Jafarikhah
William E. Skeith III
Verlag: Springer International Publishing
Buch: Provable Security
Print ISBN: 978-3-319-68636-3

Electronic ISBN: 978-3-319-68637-0

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-68637-0_23

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"