nach oben

Journal of Cryptology

Erschienen in:

28.09.2015

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

Erschienen in: Journal of Cryptology | Ausgabe 1/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser, and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest, this holds as long as \(t<n/2\) parties are corrupted, and when the adversary is malicious, this holds as long as \(t<n/3\) parties are corrupted. Unfortunately, a full proof of these results was never published. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. This includes a full description of the protocol for the malicious setting, including the construction of a new subprotocol for the perfect multiplication protocol that seems necessary for the case of \(n/4\le t<n/3\).

Vorheriger Artikel Dynamic Proofs of Retrievability Via Oblivious RAM

Nächster Artikel Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

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

In previous versions of this paper [1] and in [2], we mistakenly stated that using [10] it is possible to obtain full adaptive security with efficient simulation. However, this is actually not known, and [10] only proves that perfect security under [16] implies adaptive security with inefficient simulation, which is significantly weaker.

Throughout, when we refer to a polynomial of degree t, we mean of degree at most t.

This definition of the functionality assumes that all of the inputs lie on the polynomials \(f_a(x),f_b(x)\) and ignores the case that this does not hold. However, since we are dealing with the semi-honest case here, the inputs are always guaranteed to be correct. This can be formalized using the notion of a partial functionality [20, Sec. 7.2].

This is a specific VSS definition that is suited for the BGW protocol. We remark that it is possible to define VSS in a more general and abstract way (like a multiparty “commitment”). However, since we will need to compute on the shares \(q(\alpha _1),\ldots ,q(\alpha _n)\), these values need to be explicitly given in the output.

We remark that in the case of \(t<n/4\) (i.e., \(n\ge 4t+1\)), the parties can correct errors directly on degree-2t polynomials. Therefore, the parties can distribute subshares of the products \(a_i \cdot b_i\), and correct errors on these shares using (a variant of) the \(F_{VSS}^{subshare}\) functionality directly. Thus, overall, the case of \(t<n/4\) is significantly simpler, since there is no need for the \(F_{VSS}^{mult}\) subprotocol that was mentioned in the second step described above. A full specification of this simplification is described in “Appendix”; the description assumes familiarity with the material appearing in Sects. 6.2, 6.3, 6.4 and 6.7, and therefore should be read after these sections.

It actually suffices to send the shares \((q_1(\alpha _j),\ldots ,q_n(\alpha _j))\) only to parties \(P_j\) for \(j\notin I\) since all other parties have already received these values. Nevertheless, we present it in this way for the sake of clarity.

In the UC framework, the adversary can communicate directly with the ideal functionality and it is mandated that the adversary notifies the ideal functionality (i.e., trusted party) of the identities of all corrupted parties. Furthermore, ideal functionalities often utilize this information (i.e., they are corruption aware) since the way that the universal composability framework is defined typically requires functionalities to treat the inputs of honest and corrupted parties differently. See Section 6 of the full version of [9] for details.

This is needed because in \(F_{VSS}^{subshare}\) the parties need to output \(g_i(x)\) and so need to know it. It would be possible to have the functionality choose \(g_i(x)\) and provide it in the output, but then exactly the same issue would arise. This is explained in more detail in the next paragraph.

If all of the points sent by the honest parties lie on a single degree-t polynomial, then this guarantees that f(x) is the unique degree-t polynomial for which \(f(\alpha _j)=\beta _j\) for all \(j\notin I\). If not all the points lie on a single degree-t polynomial, then no security guarantees are obtained. However, since the honest parties all send their prescribed input, in our applications, f(x) will always be as desired. This can be formalized using the notion of a partial functionality [20, Sec. 7.2]. Alternatively, it can be formalized by as follows: In the case that the condition does not hold, the ideal functionality gives all of the honest parties’ inputs to the adversary and lets the adversary single-handedly determine all of the outputs of the honest parties. This makes any protocol vacuously secure (since anything can be simulated).

The corrupted parties also receive the vector of polynomials \((g_1(x),\ldots ,g_n(x))\cdot H^T\) as output from \(F_{mat}^H\). However, in the protocol, we only specify the honest parties’ instructions.

An alternative strategy could be to run the verification strategy of Protocol 5.6 for VSS on the shares \(C(\alpha _j)\) that the parties computed in order to verify that \(\{C(\alpha _j)\}_{j=1}^n\) define a degree-t polynomial. The problem with this strategy is that if C(x) is not a degree-t polynomial, then the protocol for \(F_{VSS}\) changes the points that the parties receive so that it is a degree-t polynomial. However, in this process, the constant term of the resulting polynomial may also change. Thus, there will no longer be any guarantee that the honest parties hold shares of a polynomial with the correct constant term.

The naming convention for the \(r_{i,j}\) values is as follows. In the first \(t-1\) coefficients, the first index in every \(r_{i,j}\) value is the index of the polynomial and the second is the place of the coefficient. That is, \(r_{i,j}\) is the jth coefficient of polynomial \(D_i(x)\). The values for the \(t^\mathrm{th}\) coefficient are used in the other polynomials as well, and are chosen to cancel out; see below.

As with \(F_{eval}\) and \(F_{VSS}^{mult}\), the simulator needs to receive the correct shares of the corrupted parties in order to simulate, and so this is also received as output. Since this information is anyway given to the corrupted parties, this makes no difference to the use of the functionality for secure computation.

We remark that the original \(\mathcal{S}\) could not work in this way since our proof that the simulations by \(\mathcal{S}\) and \(\mathcal{S}_1\) are identical uses the fact that the points \(\{A'_j(\alpha _i),B'_j(\alpha _i)_{i\in I; j\notin I},\{C'_j(\alpha _i)\}_{i\in I; j\notin I}\) alone suffice for simulation. This is true when computing \(\vec Y_A(x)\) and \(\vec Y_B(x)\) via the error vectors, but not when computing them from the actual polynomials as \(\mathcal{S}_2\) does.

G. Asharov, Y. Lindell, A full proof of the BGW protocol for perfectly-secure multiparty computation. Cryptology ePrint Archive, Report 2011/136 (2011)

G. Asharov, Y. Lindell, T. Rabin, Perfectly-secure multiplication for any \(t<n/3\), in CRYPTO 2011. LNCS 6841 (Springer, 2011), pp. 240–258

D. Beaver, Multiparty protocols tolerating half faulty processors, in CRYPTO’89. LNCS 435 (Springer, 1990), pp. 560–572

D. Beaver, Foundations of secure interactive computing, in CRYPTO’91. LNCS 576 (Springer, 1991), pp. 377–391

Z. Beerliová-Trubíniová, M. Hirt, Perfectly-secure MPC with linear communication complexity, in 5th TCC. LNCS 4948 (Springer, 2008), pp. 213–230

M. Ben-Or, R. El-Yaniv, Resilient-Optimal Interactive Consistency in Constant Time, in Distributed Computing, 16(4):249–262, (2003)CrossRef

M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in The 20th STOC (1988), pp. 1–10

R. Canetti, Security and Composition of Multiparty Cryptographic Protocols. In the Journal of Cryptology, 13(1):143–202, (2000)MathSciNetCrossRefMATH

R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in The 42nd FOCS (2001), pp. 136–145. See Cryptology ePrint Archive: Report 2000/067 for the full version

10.

R. Canetti, I. Damgård, S. Dziembowski, Y. Ishai, T. Malkin, Adaptive versus Non-Adaptive Security of Multi-Party Protocols. In the Journal of Cryptology 17(3):153–207, (2004)MathSciNetCrossRefMATH

11.

R. Canetti, U. Feige, O. Goldreich, M. Naor, Adaptively secure multi-party computation, in The 28th STOC (1996), pp. 639–648

12.

R. Canetti, H. Krawczyk, Universally composable notions of key-exchange and secure channels, in EUROCRYPT 2002. LNCS 2332 (Springer, 2002), pp. 337–351

13.

R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party computation. In The 34th STOC (2002), pp. 494–503

14.

D. Chaum, C. Crépeau, I. Damgård, Multi-party unconditionally secure protocols, in 20th STOC (1988), pp. 11–19

15.

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

16.

Y. Dodis, S. Micali, Parallel reducibility for information-theoretically secure computation, in CRYPTO 2000. LNCS 1880 (Springer, 2000), pp. 74–92

17.

P. Feldman, Optimal algorithms for byzantine agreement. Ph.D. thesis, Massachusetts Institute of Technology (1988)

18.

P. Feldman, S. Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. In the SIAM Journal on Computing, 26(4):873–933, (1997)MathSciNetCrossRefMATH

19.

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

20.

O. Goldreich, Foundations of Cryptography: Volume 2—Basic Applications (2004, Cambridge University Press, Cambridge)

21.

O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th STOC (1987), pp. 218–229. For details see [20]

22.

S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO’90. LNCS 537 (Springer, 1990), pp. 77–93

23.

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

24.

E. Kushilevitz, Y. Lindell, T. Rabin, Information-Theoretically Secure Protocols and Security Under Composition. In the SIAM Journal on Computing, 39(5):2090–2112, (2010)MathSciNetCrossRefMATH

25.

L. Lamport, R. Shostack, M. Pease, The Byzantine Generals Problem. In the ACM Transactions on Programming Languages and Systems, 4(3):382–401, (1982)CrossRefMATH

26.

Y. Lindell, General composition and universal composability in secure multi-party computation, in The 44th FOCS (2003), pp. 394–403

27.

Y. Lindell, A. Lysyanskaya, T. Rabin, Sequential composition of protocols without simultaneous termination, in The 21st PODC (2002), pp. 203–212

28.

R.J. McEliece, D.V. Sarwate, On Sharing Secrets and Reed-Solomon Codes. Communications of the ACM, 9(24):583–584, (1981)MathSciNetCrossRef

29.

S. Micali, P. Rogaway, Secure computation. Unpublished manuscript, 1992. Preliminary version, in CRYPTO’91. LNCS 576 (Springer, 1991), pp. 392–404

30.

M. Pease, R. Shostak, L. Lamport, Reaching Agreement in the Presence of Faults. In the Journal of the ACM, 27(2):228–234, (1980)MathSciNetCrossRefMATH

31.

T. Rabin, M. Ben-Or, Verifiable secret sharing and multi-party protocols with honest majority, in 21st STOC (1989), pp. 73–85

32.

A. Shamir, How to Share a Secret. In the Communications of the ACM, 22(11):612–613, (1979)MathSciNetCrossRefMATH

33.

A.C. Yao, Theory and application of trapdoor functions, in 23rd FOCS (1982), pp. 80–91

34.

A. Yao, How to generate and exchange secrets, in 27th FOCS (1986), pp. 162–167

Titel: A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation
Publikationsdatum: 28.09.2015
Erschienen in: Journal of Cryptology / Ausgabe 1/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9214-4

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/2017

Efficient One-Sided Adaptively Secure Computation

Dynamic Proofs of Retrievability Via Oblivious RAM

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

Weak Locking Capacity of Quantum Channels Can be Much Larger Than Private Capacity

Obfuscating Conjunctions

Premium Partner