nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

VSS Made Simpler

verfasst von : Yvo Desmedt, Kirill Morozov

Erschienen in: Advances in Information and Computer 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

Verifiable secret sharing (VSS) allows honest parties to ensure consistency of their shares even if a dealer and/or a subset of parties are corrupt. We focus on perfect VSS, i.e., those providing perfect privacy, correctness and commitment with zero error, in the unconditional (information-theoretic) security setting where no assumption on the computational power of the participants is imposed.

Our study is motivated by both practical and theoretical considerations. For the practical side, MPC with perfect security is now being implemented. Multi-cloud storage has been implemented by IBM. Modern users rely on smartphones with limited internet connectivity, limited battery power, etc. We focus on such a user outsourcing her data to multi-clouds with the capability to have these multi-clouds participate on her behalf in MPC protocols. We show that in the case of VSS based on the replicated secret sharing scheme, there is no need for that user to be involved in any interaction. In addition, this scheme has an optimal number of rounds. This construction is derived from Maurer’s VSS based on the replicated secret sharing scheme.

A disadvantage of the replicated scheme is that it generally requires a considerable amount of randomness. We address this issue by showing a VSS scheme based on Shamir’s secret sharing, where the dealer does not need any randomness at all.

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 Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods

Nächstes Kapitel Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity

In fact, \(Q^3\) is also necessary for perfect VSS [22].

In the current literature on VSS and MPC, it is common to allow the dealer to be one of the parties that later takes part in the protocol.

In asynchronous network, the global clocking is present so that the protocol execution can be divided into rounds, and hereby, a failure to send a message is easy to detect, for every player. Note that to prevent malleability type of attacks, parties should not be able to see data sent by others before they sent theirs. A strict synchronization enforces this in an obvious way.

Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly-secure multiparty computation. Cryptology ePrint Archive: Report 2011/136. https://eprint.iacr.org/2011/136.pdf

Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: STOC, pp. 52–61 (1993)

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

Berlekamp, E.R., Welch, L.R.: Error correction of algebraic block codes. U.S. Patent Number 4.633.470 (1986)

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

Beerliová-Trubíniová, Z., Hirt, M.: Perfectly-secure MPC with linear communication complexity. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 213–230. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_13CrossRef

Canetti, R., Kushilevitz, E., Ostrovsky, R., Rosen, A.: Randomness vs. fault-tolerance. J. Cryptol. 13(1), 107–142 (2000). Conference version in PODC 1997CrossRef

Blundo, C., De Santis, A., Persiano, G., Vaccaro, U.: Randomness complexity of private computation. Comput. Complex. 8(2), 145–168 (1999)MathSciNetCrossRef

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

10.

Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: FOCS, pp. 383–395 (1985)

11.

Cramer, R., Damgård, I., Maurer, U.: 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). https://doi.org/10.1007/3-540-45539-6_22CrossRef

12.

Choudhury, A., Kurosawa, K., Patra, A.: The round complexity of perfectly secure general VSS. In: Fehr, S. (ed.) ICITS 2011. LNCS, vol. 6673, pp. 143–162. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20728-0_14CrossRef

13.

Damgård, I., Ishai, Y., Krøigaard, M., Nielsen, J.B., Smith, A.: Scalable multiparty computation with nearly optimal work and resilience. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 241–261. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_14CrossRef

14.

Desmedt, Y., Morozov, K.: Parity Check based redistribution of secret shares. In: ISIT, pp. 959–963 (2015)

15.

Schoenmakers, B.: Verifiable secret sharing. In: van Tilborg, H.C.A., Jajodia, S. (eds.) Encyclopedia of Cryptography and Security, vol. 1357. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-5906-5_14CrossRef

16.

Serge, F., Ueli, M.: Linear VSS and distributed commitments based on secret sharing and pairwise checks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 565–580. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_36CrossRef

17.

Fitzi, M., Garay, J., Gollakota, S., Rangan, C.P., Srinathan, K.: Round-optimal and efficient verifiable secret sharing. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 329–342. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_17CrossRef

18.

Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The round complexity of verifiable secret sharing and secure multicast. In: STOC, pp. 580–589 (2001)

19.

Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fact-track multiparty computations with applications to threshold cryptography. In: PODC, pp. 101–111 (1998)

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.

Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: detection of widespread weak keys in network devices. In: 21st USENIX Conference on Security symposium (Security 2012), vol. 35 (2012)

22.

Hirt, M., Maurer, U.: Player simulation and general adversary structures in perfect multi-party computation. J. Cryptol. 13(1), 31–60 (2000). (Preliminary version in PODC 1997: 25–34.)CrossRef

23.

Hirt, M., Maurer, U., Przydatek, B.: Efficient secure multi-party computation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 143–161. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_12CrossRef

24.

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

25.

Katz, J., Koo, C.-Y., Kumaresan, R.: Improving the round complexity of VSS in point-to-point networks. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 499–510. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_41CrossRef

26.

Kushilevitz, E., Mansour, Y.: Randomness in private computations. SIAM J. Discret. Math. 10(4), 647–661 (1997)MathSciNetCrossRef

27.

Kushilevitz, E., Ostrovsky, R., Rosen, A.: Amortizing randomness in private multiparty computations. In: PODC, pp. 81–90 (1998)

28.

Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Public keys. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 626–642. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_37CrossRef

29.

Ling, S., Wang, H., Xing, C.: Algebraic Curves in Cryptography. CRC Press, Boca Raton (2013)CrossRef

30.

Maurer, U.M.: Secure multi-party computation made simple. Discret. Appl. Math. 154(2), 370–381 (2006). Journal version of Ueli M. Maurer: Secure Multi-party Computation Made Simple. SCN 2002, 14–28MathSciNetCrossRef

31.

McEliece, R.J., Sarwate, D.V.: On sharing secrets and Reed-Solomon codes. Commun. ACM 24(9), 583–584 (1981)MathSciNetCrossRef

32.

Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: STOC, pp. 73–85 (1989)

33.

Roth, R.: Introduction to Coding Theory. Cambridge University Press, Cambridge (2006)CrossRef

34.

Patra, A., Choudhary, A., Rabin, T., Rangan, C.P.: The round complexity of verifiable secret sharing revisited. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 487–504. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_29CrossRef

35.

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

36.

Stinson, D.R., Wei, R.: Unconditionally secure proactive secret sharing scheme with combinatorial structures. In: Heys, H., Adams, C. (eds.) SAC 1999. LNCS, vol. 1758, pp. 200–214. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46513-8_15CrossRef

Titel: VSS Made Simpler
verfasst von: Yvo Desmedt
Kirill Morozov
Verlag: Springer International Publishing
Buch: Advances in Information and Computer Security
Print ISBN: 978-3-030-26833-6

Electronic ISBN: 978-3-030-26834-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26834-3_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"

Premium Partner