nach oben

Journal of Cryptology

Erschienen in:

01.01.2015

Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation

verfasst von: Arpita Patra, Ashish Choudhury, C. Pandu Rangan

Erschienen in: Journal of Cryptology | Ausgabe 1/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Secure Multi-Party Computation (MPC) providing information-theoretic security allows a set of n parties to securely compute an agreed function over a finite field, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if t<n/4, while statistical AMPC is possible if and only if t<n/3. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n=4t+1 parties. Our major contributions in this paper are as follows:

Asynchronous Verifiable Secret Sharing (AVSS) is one of the main building blocks for AMPC protocols. In this paper, we design two AVSS schemes with 4t+1 parties: the first one is statistically-secure and has non-optimal resilience, while the second one is perfectly-secure and has optimal resilience. Both these schemes achieve a common interesting property, which was not achieved by the previous schemes. Specifically, our AVSS schemes allow to share a secret with the degree of sharing at most d, where t≤d≤2t. In contrast, the existing AVSS schemes allow the degree of sharing to be at most t. The new property of our AVSS schemes simplifies the degree-reduction step for the evaluation of multiplication gates in an AMPC protocol.

Using our statistical AVSS scheme, we design a statistical AMPC protocol with n=4t+1 which requires an amortized communication of \(\mathcal {O}(n^{2})\) field elements per multiplication gate. Though this protocol has non-optimal resilience, it significantly improves the communication complexity of the existing statistical AMPC protocols.

We then present a perfect AMPC protocol with n=4t+1 (using our perfect AVSS scheme), which also incurs an amortized communication of \(\mathcal{O}(n^{2})\) field elements per multiplication gate. This protocol improves on our statistical AMPC protocol as it has optimal resilience. This is the most communication efficient, optimally-resilient, perfect AMPC protocol.

Vorheriger Artikel Subtleties in the Definition of IND-CCA: When and How Should Challenge Decryption Be Disallowed?

Nächster Artikel Cryptanalysis of SHA-0 and Reduced SHA-1

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

Nur mit Berechtigung zugänglich

A party is called corrupted if it is under the control of the adversary, otherwise it is called honest.

The amortized communication complexity is derived under the assumption that the circuit is large enough so that the terms that are independent of the circuit size can be ignored.

An advantage of these protocols is that they facilitate input provision; namely the inputs of all the honest parties are considered for the evaluation of the circuit, which, otherwise, is impossible to achieve in a completely asynchronous protocol.

We note that after the submission of this article, a more efficient statistical AMPC protocol with n=4t+1 and an amortized communication complexity of \(\mathcal{O}(n \log{|{\mathbb{F}}|})\) bits per multiplication gate was presented by Choudhury et al. in [18]; the techniques used in their protocol are different from ours and discussing their protocol is out of scope of this article.

See Definition 1 for the properties of AVSS.

Such shared triples are of the form ([x]_t,[y]_t,[z]_t), where x and y are random and unknown to the adversary, with z=x⋅y.

For the perfect scheme \(|{\mathbb{F}}| > n\), while for the statistical scheme \({\mathbb{F}} = GF(q)\), where q>max(n,2^κ), such that \(\kappa= \log{\frac{1}{\epsilon}}\).

In [5], this cost is actually reduced by a factor of n by using additional tricks.

This cost is further reduced by a factor of n by using the additional tricks as in [5]. The details will be presented later.

Giving the exact details of the common coin and ABA is out of scope of the current article and so we avoid discussing them.

A univariate polynomial f _i(x) is said to lie on a bivariate polynomial F(x,y) if f _i(x)=F(x,i).

We often say that D has committed/shared \(\overline{s}\) during Sh.

In the rest of the paper, all probabilities are taken over the random coins of the honest parties.

For example, if V=P _j, then the masking polynomials \(m_{(P_{j}, 1)}(y), \ldots, m_{(P_{j}, t+1)}(y)\) are deployed.

Recall that the best known broadcast protocol due to [13] incurs a communication of \(\mathcal{O}(n^{2})\) bits to broadcast a single bit.

As mentioned earlier, we can prove the secrecy in the framework of real-world/ideal-world paradigm of [7]. However, we avoid doing so, as it requires additional technicalities which will make the paper complicated.

In [26], the concept was introduced in a slightly different way but the essence was the same.

[1]

I. Abraham, D. Dolev, J.Y. Halpern, An almost-surely terminating polynomial protocol for asynchronous Byzantine agreement with optimal resilience, in Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing—PODC 2008, Toronto, Canada, August 18–21, 2008, ed. by R.A. Bazzi, B. Patt-Shamir (ACM, New York, 2008), pp. 405–414

[2]

D. Beaver, Efficient multiparty protocols using circuit randomization, in Advances in Cryptology—CRYPTO ’91, Proceedings of 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11–15, 1991, ed. by J. Feigenbaum. Lecture Notes in Computer Science, vol. 576 (Springer, Berlin, 1991), pp. 420–432

[3]

D. Beaver, Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. J. Cryptol. 4(4), 75–122 (1991) MATH

[4]

Z. Beerliová-Trubíniová, M. Hirt, Efficient multi-party computation with dispute control, in Theory of Cryptography, Proceedings of 3rd Theory of Cryptography Conference—TCC 2006, New York, NY, USA, March 4–7, 2006, ed. by S. Halevi, T. Rabin. Lecture Notes in Computer Science, vol. 3876 (Springer, Berlin, 2006), pp. 305–328

[5]

Z. Beerliová-Trubíniová, M. Hirt, Simple and efficient perfectly-secure asynchronous MPC, in Advances in Cryptology—ASIACRYPT 2007, Proceedings of 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2–6, 2007, ed. by K. Kurosawa. Lecture Notes in Computer Science, vol. 4833 (Springer, Berlin, 2007), pp. 376–392

[6]

Z. Beerliová-Trubíniová, M. Hirt, Perfectly-secure MPC with linear communication complexity, in Theory of Cryptography, 5th Theory of Cryptography Conference—TCC 2008, New York, USA, March 19–21, 2008, ed. by R. Canetti. Lecture Notes in Computer Science, vol. 4948 (Springer, Berlin, 2008), pp. 213–230

[7]

M. Ben-Or, R. Canetti, O. Goldreich, Asynchronous secure computation, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (ACM, New York, 1993), pp. 52–61

[8]

M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, May 2–4, 1988 (ACM, New York, 1988), pp. 1–10

[9]

M. Ben-Or, B. Kelmer, T. Rabin, Asynchronous secure computations with optimal resilience, in Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, California, USA, August 14–17 (ACM, New York, 1994), pp. 183–192

[10]

E. Ben-Sasson, S. Fehr, R. Ostrovsky, Near-linear unconditionally-secure multiparty computation with a dishonest minority, in Proceedings 32nd Annual Cryptology Conference of Advances in Cryptology—CRYPTO 2012, Santa Barbara, CA, USA, August 19–23, 2012, ed. by R. Safavi-Naini, R. Canetti. Lecture Notes in Computer Science, vol. 7417 (Springer, Berlin, 2012), pp. 663–680 CrossRef

[11]

C.H. Bennett, G. Brassard, C. Crépeau, U.M. Maurer, Generalized privacy amplification. IEEE Trans. Inf. Theory 41(6), 1915–1923 (1995) CrossRefMATH

[12]

C.H. Bennett, G. Brassard, J. Robert, Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988) CrossRefMathSciNet

[13]

G. Bracha, An asynchronous ⌊(n−1)/3⌋-resilient consensus protocol, in Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B.C., Canada, August 27–29, 1984 (ACM, New York, 1984), pp. 154–162 CrossRef

[14]

R. Canetti, Studies in secure multiparty computation and applications. Ph.D. thesis, Weizmann Institute, Israel, 1995

[15]

R. Canetti, T. Rabin, Fast asynchronous Byzantine agreement with optimal resilience, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (ACM, New York, 1993), pp. 42–51

[16]

D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing—ACM 1988, Chicago, Illinois, USA, May 2–4, 1988 (ACM Press, New York, 1988), pp. 11–19

[17]

B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract), in Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, USA, 6–8 May, 1985 (ACM, New York, 1985), pp. 383–395

[18]

A. Choudhury, M. Hirt, A. Patra, Asynchronous multiparty computation with linear communication complexity, in Distributed Computing—DISC 2013, Proceedings of 27th International Symposium, Jerusalem, Israel, October 14–18, 2013, ed. by Y. Afek. Lecture Notes in Computer Science, vol. 8205 (Springer, Berlin, 2013), pp. 388–402

[19]

R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, T. Rabin, Efficient multiparty computations secure against an adaptive adversary, in Advances in Cryptology—EUROCRYPT 99, Proceeding of International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2–6, 1999, ed. by J. Stern. Lecture Notes in Computer Science, vol. 1592 (Springer, Berlin, 1999), pp. 311–326

[20]

I. Damgård, M. Geisler, M. Krøigaard, J.B. Nielsen, Asynchronous multiparty computation: theory and implementation, in Public Key Cryptography—PKC 2009, Proceeding of 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18–20, 2009, ed. by S. Jarecki, G. Tsudik. Lecture Notes in Computer Science, vol. 5443 (Springer, Berlin, 2009), pp. 160–179

[21]

I. Damgård, Y. Ishai, Scalable secure multiparty computation, in Advances in Cryptology—CRYPTO 2006, Proceedings of 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20–24, 2006, ed. by C. Dwork. Lecture Notes in Computer Science, vol. 4117 (Springer, Berlin, 2006), pp. 501–520 CrossRef

[22]

I. Damgård, J.B. Nielsen, Scalable and unconditionally secure multiparty computation, in Advances in Cryptology—CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2007, Proceedings, ed. by A. Menezes. Lecture Notes in Computer Science, vol. 4622 (Springer, Berlin, 2007), pp. 572–590 CrossRef

[23]

D. Dolev, C. Dwork, O. Waarts, M. Yung, Perfectly secure message transmission. J. ACM 40(1), 17–47 (1993) CrossRefMATHMathSciNet

[24]

P. Feldman, S. Micali, An optimal algorithm for synchronous Byzantine agreement, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, May 2–4, 1988 (ACM, New York, 1988), pp. 639–648

[25]

M. Fitzi, J. Garay, S. Gollakota, C. Pandu Rangan, K. Srinathan, Round-optimal and efficient verifiable secret sharing, in Theory of Cryptography—TCC 2006, Proceedings of 3rd Theory of Cryptography Conference, New York, NY, USA, March 4–7, 2006, ed. by S. Halevi, T. Rabin. Lecture Notes in Computer Science, vol. 3876 (Springer, Berlin, 2006), pp. 329–342

[26]

M.K. Franklin, M. Yung, Communication complexity of secure computation (extended abstract), in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 4–6, 1992, ed. by S.R. Kosaraju, M. Fellows, A. Wigderson, J.A. Ellis (ACM, New York, 1992), pp. 699–710

[27]

R. Gennaro, Y. Ishai, E. Kushilevitz, T. Rabin, The round complexity of verifiable secret sharing and secure multicast, in Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, July 6–8, 2001 (ACM, New York, 2001), pp. 580–589

[28]

O. Golderich, S. Micali, A. Wigderson, How to play a mental game or a completeness theorem for protocols with honest majority, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY, USA (ACM, New York, 1987), pp. 218–229

[29]

M. Hirt, U. Maurer, B. Przydatek, Efficient secure multiparty computation, in Advances in Cryptology—ASIACRYPT 2000, Proceedings of 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3–7, 2000, ed. by T. Okamoto. Lecture Notes in Computer Science, vol. 1976 (Springer, Berlin, 2000), pp. 143–161

[30]

Z. Huang, W. Qiu, Q. Li, K. Chen, Efficient secure multiparty computation protocol in asynchronous network, in Proceedings of Advances in Information Security and Assurance—ISA 2009, 3rd International Conference and Workshops, Seoul, Korea, ed. by J.H. Park, H. Chen, M. Atiquzzaman, C. Lee, T. Kim, S. Yeo. Lecture Notes in Computer Science, vol. 5576 (Springer, Berlin, 2009), pp. 152–158

[31]

J. Katz, C. Koo, R. Kumaresan, Improving the round complexity of VSS in point-to-point networks, in Automata, Languages and Programming—ICALP 2008, Proceedings of 35th International Colloquium, Part II, Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, Reykjavik, Iceland, July 7–11, 2008, ed. by L. Aceto, I. Damgård, L.A. Goldberg, M.M. Halldórsson, A. Ingólfsdóttir, I. Walukiewicz. Lecture Notes in Computer Science, vol. 5126 (Springer, Berlin, 2008), pp. 499–510

[32]

J. Katz, C.Y. Koo, On expected constant-round protocols for Byzantine agreement, in Advances in Cryptology—CRYPTO 2006, Proceedings of 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20–24, 2006, Lecture Notes in Computer Science, ed. by C. Dwork (Springer, Berlin, 2006), pp. 445–462 CrossRef

[33]

F.J. MacWilliams, N.J.A. Sloane, The Theory of Error Correcting Codes (North-Holland, Amsterdam, 1978)

[34]

A. Patra, A. Choudhary, T. Rabin, C. Pandu Rangan, The round complexity of verifiable secret sharing revisited, in Advances in Cryptology—CRYPTO 2009, Proceedings of 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2009, ed. by S. Halevi. Lecture Notes in Computer Science, vol. 5677 (Springer, Berlin, 2009), pp. 487–504 CrossRef

[35]

A. Patra, A. Choudhary, C. Pandu Rangan, Round efficient unconditionally secure multiparty computation protocol, in Progress in Cryptology—INDOCRYPT 2008, Proceedings of 9th International Conference on Cryptology in India, Kharagpur, India, December 14–17, 2008, ed. by D.R. Chowdhury, V. Rijmen, A. Das. Lecture Notes in Computer Science, vol. 5365 (Springer, Berlin, 2008), pp. 185–199 CrossRef

[36]

A. Patra, A. Choudhary, C. Pandu Rangan, Efficient asynchronous Byzantine agreement with optimal resilience. (accepted for publication) Distr. Comput. J. A preliminary version of this article appeared in Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing—PODC 2009, Calgary, Alberta, Canada, 10–12 August, pp. 92–101 (2009)

[37]

A. Patra, A. Choudhary, C. Pandu Rangan, Efficient statistical asynchronous verifiable secret sharing and multiparty computation with optimal resilience. Cryptology ePrint Archive, Report 2009/492, 2009

[38]

A. Patra, A. Choudhary, C. Pandu Rangan, Communication efficient perfectly secure VSS and MPC in asynchronous networks with optimal resilience, in Advances in Cryptology—AFRICACRYPT’10, Proceedings of 3rd International Conference in Cryptology in Africa, Stellenbosch, South Africa, May 3–6, 2009, ed. by D.J. Bernstein, T. Lange. Lecture Notes in Computer Science, vol. 6055 (Springer, Berlin, 2010), pp. 184–202 CrossRef

[39]

B. Prabhu, K. Srinathan, C. Pandu Rangan, Trading players for efficiency in unconditional multiparty computation, in 3rd International Conference on Security in Communication Networks—SCN 2002, Amalfi, Italy, September 11–13, 2002, ed. by S. Cimato, C. Galdi, G. Persiano. Lecture Notes in Computer Science, vol. 2576 (Springer, Berlin, 2002), pp. 342–353. Revised papers

[40]

T. Rabin, Robust sharing of secrets when the dealer is honest or cheating. J. ACM 41(6), 1089–1109 (1994) CrossRefMathSciNet

[41]

T. Rabin, M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority (extended abstract), in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washigton, USA, May 14–17, 1989 (ACM, New York, 1989), pp. 73–85

[42]

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

[43]

K. Srinathan, C. Pandu Rangan, Efficient asynchronous secure multiparty distributed computation, in Progress in Cryptology—INDOCRYPT 2000, Proceedings of 1st International Conference in Cryptology in India, Calcutta, India, December 10–13, 2000, ed. by B.K. Roy, E. Okamoto. Lecture Notes in Computer Science, vol. 1977 (Springer, Berlin, 2000), pp. 117–129 CrossRef

[44]

A.C. Yao, Protocols for secure computations, in Proceedings of 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, 3–5 November 1982, IEEE Computer Society (1982), pp. 160–164

[45]

H. Zheng, G. Zheng, L. Qiang, Batch secret sharing for secure multi-party computation in asynchronous network. J. Shanghai Jiaotong Univ. 14(1), 112–116 (2009) CrossRefMATH

Titel: Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation
verfasst von: Arpita Patra
Ashish Choudhury
C. Pandu Rangan
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 1/2015
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-013-9172-7

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"

Weitere Artikel der Ausgabe 1/2015

Subtleties in the Definition of IND-CCA: When and How Should Challenge Decryption Be Disallowed?

Slidex Attacks on the Even–Mansour Encryption Scheme

Cryptanalysis of SHA-0 and Reduced SHA-1

Quantum Private Information Retrieval has Linear Communication Complexity

Confined Guessing: New Signatures From Standard Assumptions