nach oben

Journal of Cryptology

Erschienen in:

12.02.2018

Probabilistic Termination and Composability of Cryptographic Protocols

verfasst von: Ran Cohen, Sandro Coretti, Juan Garay, Vassilis Zikas

Erschienen in: Journal of Cryptology | Ausgabe 3/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

When analyzing the round complexity of multi-party protocols, one often overlooks the fact that underlying resources, such as a broadcast channel, can by themselves be expensive to implement. For example, it is well known that it is impossible to implement a broadcast channel by a (deterministic) protocol in a sublinear (in the number of corrupted parties) number of rounds. The seminal works of Rabin and Ben-Or from the early 1980s demonstrated that limitations as the above can be overcome by using randomization and allowing parties to terminate at different rounds, igniting the study of protocols over point-to-point channels with probabilistic termination and expected constant round complexity. However, absent a rigorous simulation-based definition, the suggested protocols are proven secure in a property-based manner or via ad hoc simulation-based frameworks, therefore guaranteeing limited, if any, composability. In this work, we put forth the first simulation-based treatment of multi-party cryptographic protocols with probabilistic termination. We define secure multi-party computation (MPC) with probabilistic termination in the UC framework and prove a universal composition theorem for probabilistic termination protocols. Our theorem allows to compile a protocol using deterministic termination hybrids into a protocol that uses expected constant round protocols for emulating these hybrids, preserving the expected round complexity of the calling protocol. We showcase our definitions and compiler by providing the first composable protocols (with simulation-based security proofs) for the following primitives, relying on point-to-point channels: (1) expected constant round perfect Byzantine agreement, (2) expected constant round perfect parallel broadcast, and (3) perfectly secure MPC with round complexity independent of the number of parties.

Vorheriger Artikel On Black-Box Complexity of Universally Composable Security in the CRS Model

Nächster Artikel Leakage Resilience from Program Obfuscation

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

More precisely, in the number of corruptions a protocol can tolerate, which is a constant fraction of n.

Throughout this work we will consider protocols in which all parties receive their output. If one relaxes this requirement (i.e., allows that some parties may not receive their outputs and give up on fairness), then the techniques of Goldwasser and Lindell [35] allow for replacing broadcast with a constant round multi-cast primitive. In fact, we note that even security with identifiable abort [38] cannot be achieved in general without the ability to compute broadcast [19, 20].

We remark that even though those protocols are for the computational setting, the lower bound on broadcast round complexity also applies.

Note that this includes even FHE-based protocols, as they also assume a broadcast channel and their security fails if multi-cast over point-to-point channels is used instead.

Essentially, the value of the coin can be adopted by the honest parties in case disagreement at any given round is detected, a process that is repeated multiple times.

Throughout this paper we use running time and round complexity interchangeably.

It should be noted, however, that in many of these protocols there is a known (constant) “slack” of c rounds, such that if a party terminates in round r, then it can be sure that every honest party will have terminated by round \(r+c\).

As we discuss below, the protocol of Katz and Koo has an additional issue with adaptive security in the rushing adversary model, as defined in the UC framework, similar to the issue exploited in [37].

BA is a deterministic output primitive and it should be clear that the term “randomized" can only refer to the actual number of rounds; however, to avoid confusion we will abstain from using this term for functionalities other than BA whose output might also be probabilistic.

As we show, the protocol in [28] does not satisfy input independence, and therefore is not adaptively secure in a simulation-based manner (cf. [37]).

All entities in UC, and in particular ideal functionalities, are strict interactive PPT Turing machines, and the UC composition theorem is proved for such PPT ITMs.

Although security against a “dynamic” adversary is also claimed in [5], the protocol does not implement the natural parallel broadcast functionality in the presence of an adaptive adversary (see Sect. 5).

Note that even a single round of broadcast is enough to create the issues with parallel composition and non-simultaneous termination discussed above.

In contrast, a static adversary chooses the set of corrupted parties at the onset of the computation.

Following the simplifying approach of [43], we assume that communication channels are single use; thus, each message transmission uses an independent instance of the channel (cf. “Appendix B”).

In fact, for simplicity we assume that they deliver output on the first “fetch”.

Looking ahead, this adversarial influence will allow us to describe BA-like functionalities as simple and intuitive CSFs.

This is, in fact, also the case for the standard UC SFE functionality.

In particular, this means that most CSFs are not realizable, since they always guarantee output after two rounds.

In this work, atomic functionalities are always parallel SMT CSFs \(\mathcal {F}_{\textsc {psmt}} \), defined in Sect. 4.3.

Note that the root node of the trace sampled from \(D_{\mathcal {F}_{\textsc {}}}\) is merely labeled by \(\mathcal {W}_{\mathrm {flex}} ^{D_{\mathcal {F}_{\textsc {}}}}(\mathcal {F}_{\textsc {}} ')\), i.e., this is not a circular definition.

We note that the insufficiency of the blowup factor \(2c+1\) rounds does not correspond to any particular attack, but it is merely a technicality of the wrapped CSF definition, see Sect. 4.3.

The distributions \(D_i\) depend on the protocols realizing the strictly wrapped functionalities \(\mathcal {W}_{\text {sl-strict}} ^{D_i,c}(\mathcal {F}_{\textsc {}} {}_i)\). Note, however, that the composition theorems in Sects. 4.1 and 4.2 actually work for arbitrary distributions \(D_i\).

Of course, the root of the trace \(T \) sampled from D is a flexibly wrapped functionality \(\mathcal {W}_{\mathrm {flex}} ^{D} (\mathcal {F}_{\textsc {}})\) in the probabilistic termination case.

Recall that proving security with respect to the dummy adversary is sufficient (cf. [10, Claim 10]).

In [5] the problem is referred to as “interactive consistency.”

In [37] verifiable secret sharing (VSS) is used; however, as we argue, this is not necessary.

A full simulation proof of the protocol with a black-box straight-line simulation was recently given by [2] and [23].

As argued in [43], bounded-delay channels are essential as they allow parties to detect whether or not a message was sent within a round.

As pointed out in [43], an alternative approach would be to have a multi-use communication channel; as modeling the actual communication network is out of the scope of the current work, we will use the more standard and formally treated model of single-use channels from [43].

In fact, in Sect. 3 we introduce a more liberal variant of the UC SFE functionality that we call canonical synchronous functionality (in short, CSF) that allows us to abstract several (even more complicated) tasks such as Byzantine agreement.

In the simple case where the parties only use point-to-point channels, \(\mu =2(n-1)\), since each party uses \(n-1\) channels as sender and \(n-1\) as receiver to exchange his messages for each round with all other n parties.

The wrappers presented in this work generalize the notion of guaranteed termination to capture randomized number of rounds. Concretely, one can view the functionality for SFE with guarantee termination from [43] as a wrapped version of the standard SFE functionality with our wrapper with a deterministic round distribution.

To make sure that the simulator can keep track of the round index, \(\mathcal {F}_{\textsc {}}\) notifies \(\mathcal {S}\) about each received input, unless it has reached its delivery state defined below.

Recall that proving security with respect to the dummy adversary is sufficient (cf. [10, Claim 10]).

Recall that the children at each node in a trace are ordered.

\(\mathcal {S} \) can be advanced by suitably sending it \((\texttt {fetch-output},\mathsf {sid},\cdot )\) messages.

The execution \(\mathcal {Z} \) interacts with can be advanced by suitably sending \((\texttt {fetch-output},\mathsf {sid},\cdot )\) messages to the parties.

Recall that proving security with respect to the dummy adversary is sufficient [10, Claim 10].

\(\mathcal {S} \) can be advanced by suitably sending it \((\texttt {fetch-output},\mathsf {sid},\cdot )\) messages.

The execution \(\mathcal {Z} \) interacts with can be advanced by suitably sending \((\texttt {fetch-output},\mathsf {sid})\) messages to the parties.

Note that although the hybrids are CSFs, and all honest parties terminate at the same round, the protocol has probabilistic termination.

G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, D. Wichs, Multiparty computation with low communication, computation and interaction via threshold FHE, in David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012. LNCS, vol. 7237 (Springer, April, 2012), pp. 483–501

G. Asharov, Y. Lindell, A full proof of the BGW protocol for perfectly-secure multiparty computation. Electronic Colloquium on Computational Complexity (ECCC), 18:36, (2011)

D. Beaver, S. Micali, P. Rogaway, The round complexity of secure protocols (extended abstract), in 22nd ACM STOC. (ACM Press, May 1990), pp. 503–513

M. Ben-Or, Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract), in Robert L. Probert, Nancy A. Lynch, and Nicola Santoro, editors, 2nd ACM PODC. (ACM Press, August 1983), pp. 27–30

M. Ben-Or, R. El-Yaniv, Resilient-optimal interactive consistency in constant time. Distributed Computing, 16(4):249–262, (2003)CrossRef

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

G. Bracha, An asynchronous [(n-1)/3]-resilient consensus protocol, in Robert L. Probert, Nancy A. Lynch, and Nicola Santoro, editors, 3rd ACM PODC. (ACM Press, August 1984), pp. 154–162

C. Cachin, K. Kursawe, F. Petzold, V. Shoup, Secure and efficient asynchronous broadcast protocols, in Joe Kilian, editor, CRYPTO 2001. LNCS, vol. 2139 (Springer, August 2001), pp. 524–541

R. Canetti, Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, (2000)MathSciNetCrossRefMATH

10.

R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in 42nd FOCS. (IEEE Computer Society Press, October 2001), pp. 136–145

11.

R. Canetti, Universally composable signature, certification, and authentication, in 17th IEEE Computer Security Foundations Workshop, (CSFW-17). (2004), pp. 219–235

12.

R. Canetti, A. Cohen, Y. Lindell, A simpler variant of universally composable security for standard multiparty computation, in Rosario Gennaro and Matthew Robshaw, editors, CRYPTO 2015, Part II. LNCS, vol. 9216 (Springer, August 2015), pp. 3–22

13.

R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation, in 34th ACM STOC, (ACM Press, May 2002), pp. 494–503

14.

R. Canetti, T. Rabin, Universal composition with joint state, in Dan Boneh, editor, CRYPTO 2003. LNCS, vol. 2729 (Springer, August 2003), pp. 265–281

15.

D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols (extended abstract), in 20th ACM STOC, (ACM Press, May 1988), pp. 11–19

16.

S.G. Choi, J. Katz, A.J. Malozemoff, V. Zikas, Efficient three-party computation from cut-and-choose, in Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II. LNCS, vol. 8617 (Springer, August 2014), pp. 513–530

17.

R. Cohen, S. Coretti, J.A. Garay, V. Zikas, Probabilistic termination and composability of cryptographic protocols, in Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III. LNCS, vol. 9816 (Springer, August 2016), pp. 240–269

18.

R. Cohen, S. Coretti, J.A. Garay, V. Zikas, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, in ICALP 2017. LIPIcs, vol. 80 (July 2017), pp. 37:1–37:15

19.

R. Cohen, I. Haitner, E. Omri, L. Rotem, Characterization of secure multiparty computation without broadcast, in Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I. LNCS, vol. 9562 (Springer, January 2016), pp. 596–616

20.

R. Cohen, Y. Lindell, Fairness versus guaranteed output delivery in secure multiparty computation, in ASIACRYPT 2014, Part II. LNCS, vol. 8874 (Springer, December 2014), pp. 466–485

21.

I. Damgård, Y. Ishai, Constant-round multiparty computation using a black-box pseudorandom generator, in Victor Shoup, editor, CRYPTO 2005, LNCS, vol. 3621 (Springer, August 2005), pp. 378–394

22.

I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, N.P. Smart, Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits, in Jason Crampton, Sushil Jajodia, and Keith Mayes, editors, ESORICS 2013. LNCS, vol. 8134 (Springer, September 2013), pp. 1–18

23.

I. Damgård, J.B. Nielsen, Adaptive versus static security in the UC model, in ProvSec 2014, (2014), pp. 10–28MathSciNetMATH

24.

I. Damgård, V. Pastro, N.P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012. LNCS, vol. 7417 (Springer, August 2012), pp. 643–662

25.

D. Dolev, R. Reischuk, H.R. Strong, Early stopping in byzantine agreement. J. ACM, 37(4):720–741, (1990)MathSciNetCrossRefMATH

26.

D. Dolev, H. Raymond Strong, Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, (1983)MathSciNetCrossRefMATH

27.

B. Eisenberg, On the expectation of the maximum of IID geometric random variables. Statistics & Probability Letters, 78(2):135–143, (2008)MathSciNetCrossRefMATH

28.

P. Feldman, S. Micali, An optimal probabilistic protocol for synchronous byzantine agreement. SIAM Journal on Computing, 26(4):873–933, (1997)MathSciNetCrossRefMATH

29.

M.J. Fischer, N.A. Lynch, A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183–186, (1982)MathSciNetCrossRefMATH

30.

M. Fitzi, J.A. Garay, Efficient player-optimal protocols for strong and differential consensus, in Elizabeth Borowsky and Sergio Rajsbaum, editors, 22nd ACM PODC, (ACM Press, July 2003), pp. 211–220

31.

S. Garg, C. Gentry, S. Halevi, M. Raykova, Two-round secure MPC from indistinguishability obfuscation, in Yehuda Lindell, editor, TCC 2014. LNCS, vol. 8349 (Springer, February 2014), pp. 74–94

32.

O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract), in 27th FOCS. (IEEE Computer Society Press, October 1986), pp. 174–187

33.

O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or A completeness theorem for protocols with honest majority, in Alfred Aho, editor, 19th ACM STOC. (ACM Press, May 1987), pp. 218–229

34.

O. Goldreich, E. Petrank, The best of both worlds: Guaranteeing termination in fast randomized byzantine agreement protocols. Information Processing Letters, 36(1):45–49, (1990)MathSciNetCrossRefMATH

35.

S. Goldwasser, Y. Lindell, Secure multi-party computation without agreement. Journal of Cryptology, 18(3):247–287, (2005)MathSciNetCrossRefMATH

36.

S.D. Gordon, F.-H. Liu, E. Shi, Constant-round MPC with fairness and guarantee of output delivery, in Rosario Gennaro and Matthew Robshaw, editors, CRYPTO 2015, Part II. LNCS, vol. 9216 (Springer, August 2015), pp. 63–82

37.

M. Hirt, V. Zikas, Adaptively secure broadcast, in Henri Gilbert, editor, EUROCRYPT 2010. LNCS, vol. 6110 (Springer, May 2010), pp. 466–485

38.

Y. Ishai, R. Ostrovsky, V. Zikas, Secure multi-party computation with identifiable abort, in Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II. LNCS, vol. 8617 (Springer, August 2014), pp. 369–386

39.

Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer - efficiently, in David Wagner, editor, CRYPTO 2008. LNCS, vol. 5157 (Springer, August 2008), pp. 572–591

40.

J. Katz, C.-Y. Koo, On expected constant-round protocols for byzantine agreement, in Cynthia Dwork, editor, CRYPTO 2006. LNCS, vol. 4117 (Springer, August 2006), pp. 445–462

41.

J. Katz, C.-Y. Koo, Round-efficient secure computation in point-to-point networks, in Moni Naor, editor, EUROCRYPT 2007. LNCS, vol. 4515. (Springer, May 2007), pp. 311–328

42.

J. Katz, Y. Lindell, Handling expected polynomial-time strategies in simulation-based security proofs, in Joe Kilian, editor, TCC 2005. LNCS, vol. 3378 (Springer, February 2005), pp. 128–149

43.

J. Katz, U. Maurer, B. Tackmann, V. Zikas, Universally composable synchronous computation, in Amit Sahai, editor, TCC 2013. LNCS, vol. 7785 (Springer, March 2013), pp. 477–498

44.

M. Keller, P. Scholl, N.P. Smart, An architecture for practical actively secure MPC with dishonest majority, in Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 13. (ACM Press, November 2013), pp. 549–560

45.

J. Kilian, Founding cryptography on oblivious transfer, in 20th ACM STOC. (ACM Press, May 1988), pp. 20–31

46.

E. Kushilevitz, Y. Lindell, T. Rabin, Information-theoretically secure protocols and security under composition, in Jon M. Kleinberg, editor, 38th ACM STOC. (ACM Press, May 2006), pp. 109–118

47.

L. Lamport, R.E. Shostak, M.C. Pease, The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, (1982)CrossRefMATH

48.

Y. Lindell, A. Lysyanskaya, T. Rabin, On the composition of authenticated byzantine agreement, in 34th ACM STOC. (ACM Press, May 2002), pp. 514–523

49.

Y. Lindell, A. Lysyanskaya, T. Rabin, Sequential composition of protocols without simultaneous termination, in Aleta Ricciardi, editor, 21st ACM PODC. (ACM Press, July 2002), pp. 203–212

50.

Y. Lindell, B. Pinkas, N.P. Smart, A. Yanai, Efficient constant round multi-party computation combining BMR and SPDZ, in Rosario Gennaro and Matthew Robshaw, editors, CRYPTO 2015, Part II. LNCS, vol. 9216 (Springer, August 2015), pp. 319–338

51.

P. Mukherjee, D. Wichs, Two round multiparty computation via multi-key FHE, in Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, LNCS, vol. 9666 (Springer, May 2016), pp. 735–763

52.

M.C. Pease, R.E. Shostak, L. Lamport, Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228–234, (1980)MathSciNetCrossRefMATH

53.

M.O. Rabin, Randomized byzantine generals, in 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983. (IEEE Computer Society, 1983), pp. 403–409

54.

T. Rabin, M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority (extended abstract), in 21st ACM STOC. (ACM Press, May 1989), pp. 73–85

55.

R. Turpin, B.A. Coan, Extending binary byzantine agreement to multivalued byzantine agreement. Information Processing Letters, 18(2):73–76, (1984)CrossRef

56.

A.C.-C. Yao, Protocols for secure computations (extended abstract), in 23rd FOCS. (IEEE Computer Society Press, November 1982), pp. 160–164.

Titel: Probabilistic Termination and Composability of Cryptographic Protocols
verfasst von: Ran Cohen
Sandro Coretti
Juan Garay
Vassilis Zikas
Publikationsdatum: 12.02.2018
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-018-9279-y

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 3/2019

The Magic of ELFs

Key Establishment à la Merkle in a Quantum World

Leakage Resilience from Program Obfuscation

On Black-Box Complexity of Universally Composable Security in the CRS Model

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes