Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Non-Interactive Verifiable Secret Sharing for Monotone Circuits

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

Published in: Progress in Cryptology – AFRICACRYPT 2016

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter On the Security of the (F)HMQV Protocol
next chapter Fast Oblivious AES A Dedicated Application of the MiniMac Protocol
Footnotes
1
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.
 
2
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.
 
3
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.
 
4
(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.).
 
Literature
[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]
[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]
[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)
Metadata
Title
Non-Interactive Verifiable Secret Sharing for Monotone Circuits
Authors
Ge Bai
Ivan Damgård
Claudio Orlandi
Yu Xia
Copyright Year
2016
Book
Progress in Cryptology – AFRICACRYPT 2016

Print ISBN: 978-3-319-31516-4

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

Copyright Year: 2016

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

Premium Partner

    Image Credits