nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Non-Interactive Verifiable Secret Sharing for Monotone Circuits

verfasst von : Ge Bai, Ivan Damgård, Claudio Orlandi, Yu Xia

Erschienen in: Progress in Cryptology – AFRICACRYPT 2016

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 propose a computationally secure and non-interactive verifiable secret sharing scheme that can be efficiently constructed from any monotone Boolean circuit. By non-interactive we mean that the dealer needs to be active only once, where he posts a public message as well as a private message to each shareholder. In the random oracle model, we can even avoid interaction between shareholders. By efficient, we mean that we avoid generic zero-knowledge techniques. Such efficient constructions were previously only known from linear secret sharing schemes (LSSS). It is believed that the class of access structures that can be handled with polynomial size LSSS is incomparable to the class that can be recognized by polynomial size monotone circuits, so in this sense we extend the class of access structures with efficient and non-interactive VSS.

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 On the Security of the (F)HMQV Protocol

Nächstes Kapitel Fast Oblivious AES A Dedicated Application of the MiniMac Protocol

However, since there are doubly exponentially many (families of) access structures, an easy counting argument shows that we cannot hope to handle all access structures with polynomial time sharing algorithms.

On the way to our result, as a secondary contribution, we also prove that the construction of [VNS+03] satisfies a strong, simulation based notion of privacy, while the original paper only argues for a weaker, “one-way” definition of privacy.

In case where no trusted party exists to run this setup, a secure computation protocol can be used instead. We note that our setup algorithm will output an RSA modulus, and that several efficient protocols for this task exist, depending on the desired security guarantees and threshold.

(Note that the scheme would not be secure if the adversary could make 2 CPA queries, since in that case it could recover k in the same way as the reduction does.).

[ACGS88]

Alexi, W., Chor, B., Goldreich, O., Schnorr, C.P.: RSA and rabin functions: Certain parts are as hard as the whole. SIAM J. Comput. 17(2), 194–209 (1988)MathSciNetCrossRefMATH

[BL90]

Benaloh, J.C., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, Heidelberg (1990)CrossRef

[Bla79]

Blakley, G.R.: Safeguarding cryptographic keys. In: National Computer Conference, pp. 313–317. IEEE Computer Society (1979)

[CDD00]

Cramer, R., Damgård, I., Dziembowski, S.: On the complexity of verifiable secret sharing and multiparty computation. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 325–334. ACM (2000)

[CDM00]

Cramer, R., Damgård, I.B., Maurer, U.M.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)CrossRef

[DHKT08]

Damgård, I., Hofheinz, D., Kiltz, E., Thorbek, R.: Public-key encryption with non-interactive opening. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 239–255. Springer, Heidelberg (2008)CrossRef

[DT07]

Damgård, I.B., Thorbek, R.: Non-interactive proofs for integer multiplication. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 412–429. Springer, Heidelberg (2007)CrossRef

[HL10]

Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols. Springer, Heidelberg (2010)CrossRefMATH

[ISN89]

Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electron. Commun. Jpn. (Part III: Fundam. Electron. Sci.) 72(9), 56–64 (1989)MathSciNetCrossRef

[KW93]

Karchmer, M., Wigderson, A.: On span programs. In: Structure in Complexity Theory Conference, pp. 102–111 (1993)

[Ped92]

Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)

[Sha79]

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

[Sta96]

Stadler, M.A.: Publicly verifiable secret sharing. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 190–199. Springer, Heidelberg (1996)CrossRef

[VNS+03]

Vinod, V., Narayanan, A., Srinathan, K., Pandu Rangan, C., Kim, K.: On the power of computational secret sharing. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 162–176. Springer, Heidelberg (2003)CrossRef

[Yao89]

Yao, A.C.: Unpublished manuscript. Presented at Oberwolfach and DIMACS workshops (1989)

Titel: Non-Interactive Verifiable Secret Sharing for Monotone Circuits
verfasst von: Ge Bai
Ivan Damgård
Claudio Orlandi
Yu Xia
Verlag: Springer International Publishing
Buch: Progress in Cryptology – AFRICACRYPT 2016
Print ISBN: 978-3-319-31516-4

Electronic ISBN: 978-3-319-31517-1

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-31517-1_12

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