nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Synchronizable Fair Exchange

verfasst von : Ranjit Kumaresan, Srinivasan Raghuraman, Adam Sealfon

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality \(n - 1\) is complete for realizing an arbitrary n-party functionality with guaranteed output delivery. In this work, we introduce a new 2-party primitive \(\mathcal {F}_{\textsf{SyX}}\) (“synchronizable fair exchange”) and show that it is complete for realizing any n-party functionality with fairness in a setting where all parties are pairwise connected by instances of \(\mathcal {F}_{\textsf{SyX}}\).

In the \(\mathcal {F}_{\textsf{SyX}}\)-hybrid model, the two parties load \(\mathcal {F}_{\textsf{SyX}}\) with some input, and following this, either party can trigger \(\mathcal {F}_{\textsf{SyX}}\) with a “witness” at a later time to receive the output from \(\mathcal {F}_{\textsf{SyX}}\). Crucially the other party also receives output from \(\mathcal {F}_{\textsf{SyX}}\) when \(\mathcal {F}_{\textsf{SyX}}\) is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of \(\mathcal {F}_{\textsf{SyX}}\), thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of \(\mathcal {F}_{\textsf{SyX}}\) in any number of multiparty protocols (involving different sets of parties). (The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/), (This work was done in part while all the authors were at MIT).

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 On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC

Nächstes Kapitel DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead

Fairness means that either all parties get the output or none do. Guaranteed output delivery means that all parties get the output.

Cardinality refers to the number of parties interacting with a single instance of the ideal primitive.

Although unstated in [18], we believe that their lower bound proof extends even for reactive functionalities. That is, no \((n-1)\)-wise reactive functionality is sufficient to realize broadcast (and consequently, secure computation with guaranteed output delivery).

In fact, some of their primitives are also complete for secure computation with guaranteed output delivery.

The primitive complexity of \(\mathcal {F}_{\textsf{SyX}}\) is independent of the function that is fairly computed. As mentioned before, this was the case with the primitives proposed by [24], but not [18].

While we introduce \(\mathcal {F}_{\textsf{SyX}}\) in terms of arbitrary functions \(f_1, f_2\), our (strongest) results can be obtained by, loosely speaking, setting \(f_1(x_1, x_2) = (v_1 \oplus x_1, v_2 \oplus x_2)\) for randomly chosen \(v_1, v_2\), and \(f_2(x_1, x_2, w; v_1, v_2) = \textsf{Hash}(v_1\oplus v_2\Vert w)\) (see Sect. 5).

Preprocessing for a bounded number of executions may be achieved by assuming only receiver non-committing encryption [11].

Here we have assumed that the domains of the inputs of all parties is \(\mathcal {X}\) for simplicity of notation. This can be easily adapted to consider setting where the domains are different.

Note that when \(t = n\), there is nothing to prove.

We may assume without loss of generality that the lengths of the outputs of each party are known beforehand.

This does not entail actually setting \(r = 0\), but rather viewing the current round as round zero and henceforth referencing rounds with respect to it, that is, viewing r as the round number relative to the round number when this statement was executed.

We may assume without loss of generality that the lengths of the outputs of each party are known beforehand.

Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Fair two-party computations via bitcoin deposits. In: Böhme, R., Brenner, M., Moore, T., Smith, M. (eds.) Financial Cryptography and Data Security - FC 2014 Workshops, BITCOIN and WAHC 2014, Christ Church, Barbados, 7 March 2014, Revised Selected Papers. LNCS, vol. 8438, pp. 105–121. Springer, Cham (2014). https://doi.org/10.1007/978-3-662-44774-1_8

Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. Commun. ACM 59(4), 76–84 (2016)CrossRef

Asharov, G.: Towards characterizing complete fairness in secure two-party computation. In: Lindell, Y. (ed.) Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, 24–26 February 2014, Proceedings. LNCS, vol. 8349, pp. 291–316. Springer, Cham (2014). https://doi.org/10.1007/978-3-642-54242-8_13

Asharov, G., Beimel, A., Makriyannis, N., Omri, E.: Complete characterization of fairness in secure two-party computation of boolean functions. In: Dodis, Y., Nielsen, J.B. (eds.) Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, 23–25 March 2015, Proceedings, Part I. LNCS, vol. 9014, pp. 199–228. Springer, Cham (2015). https://doi.org/10.1007/978-3-662-46494-6_10

Asokan, N., Schunter, M., Waidner, M.: Optimistic protocols for fair exchange. In: CCS 1997, Proceedings of the 4th ACM Conference on Computer and Communications Security, Zurich, Switzerland, 1–4 April 1997, pp. 7–17 (1997)

Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. IEEE J. Sel. Areas Commun. 18(4), 593–610 (2000)CrossRefMATH

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

Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology - CRYPTO 2014–34th Annual Cryptology Conference, Santa Barbara, CA, USA, 17–21 August 2014, Proceedings, Part II. LNCS, vol. 8617, pp. 421–439. Springer, Cham (2014). https://doi.org/10.1007/978-3-662-44381-1_24

Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) Advances in Cryptology - CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, 20–24 August 2000, Proceedings. LNCS, vol. 1880, pp. 236–254. Springer, Cham (2000). https://doi.org/10.1007/3-540-44598-6_15

10.

Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, 19–23 August 2001, Proceedings. LNCS, vol. 2139, pp. 19–40. Springer, Cham (2001). https://doi.org/10.1007/3-540-44647-8_2

11.

Canetti, R., Halevi, S., Katz, J.: Adaptively-secure, non-interactive public-key encryption. In: Kilian, J. (ed.) Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 10–12 February 2005, Proceedings. LNCS, vol. 3378, pp. 150–168. Springer, Cham (2005). https://doi.org/10.1007/978-3-540-30576-7_9

12.

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

13.

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

14.

Choudhuri, A.R., Green, M., Jain, A., Kaptchuk, G., Miers, I.: Fairness in an unfair world: fair multiparty computation from public bulletin boards. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, 30 October–3 November 2017, pp. 719–728 (2017)

15.

Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 28–30 May 1986, Berkeley, California, USA, pp. 364–369 (1986)

16.

Cohen, R., Lindell, Y.: Fairness versus guaranteed output delivery in secure multiparty computation. J. Cryptology 30(4), 1157–1186 (2017)MathSciNetCrossRefMATH

17.

Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983)MathSciNetCrossRefMATH

18.

Fitzi, M., Garay, J.A., Maurer, U.M., Ostrovsky, R.: Minimal complete primitives for secure multi-party computation. J. Cryptology 18(1), 37–61 (2005)MathSciNetCrossRefMATH

19.

Garay, J.A., Jakobsson, M.: Timed release of standard digital signatures. In: Blaze, M. (ed.) Financial Cryptography, 6th International Conference, FC 2002, Southampton, Bermuda, 11–14 March 2002, Revised Papers. LNCS, vol. 2357, pp. 168–182. Springer, Cham (2002). https://doi.org/10.1007/3-540-36504-4_13

20.

Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. J. Cryptology 24(4), 615–658 (2011)MathSciNetCrossRefMATH

21.

Garay, J.A., Pomerance, C.: Timed fair exchange of standard signatures: (extended abstract). In: Wright, R.N. (ed.) Financial Cryptography, 7th International Conference, FC 2003, Guadeloupe, French West Indies, 27–30 January 2003, Revised Papers. LNCS, vol. 2742, pp. 190–207. Springer, Cham (2003). https://doi.org/10.1007/978-3-540-45126-6_14

22.

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

23.

Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6), 24:1–24:37 (2011)

24.

Gordon, S.D., Ishai, Y., Moran, T., Ostrovsky, R., Sahai, A.: On complete primitives for fairness. In: Micciancio, D. (ed.) Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, 9–11 February 2010, Proceedings. LNCS, vol. 5978, pp. 91–108. Springer, Cham (2010). https://doi.org/10.1007/978-3-642-11799-2_7

25.

Gordon, S.D., Katz, J.: Complete fairness in multi-party computation without an honest majority. In: Reingold, O. (ed.) Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, 15–17 March 2009, Proceedings. LNCS, vol. 5444, pp. 19–35. Springer, Cham (2009). https://doi.org/10.1007/978-3-642-00457-5_2

26.

Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. In: Gilbert, H. (ed.) Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco/French Riviera, 30 May–3 June 2010, Proceedings. LNCS, vol. 6110, pp. 157–176. Springer, Cham (2010). https://doi.org/10.1007/978-3-642-13190-5_8

27.

Katz, J.: On achieving the “best of both worlds” in secure multiparty computation. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11–13 June 2007, pp. 11–20 (2007)

28.

Kumaresan, R., Raghuraman, S., Sealfon, A.: Synchronizable exchange. IACR Cryptol. ePrint Arch. 976 (2020)

29.

Kumaresan, R., Vaikuntanathan, V., Vasudevan, P.N.: Improvements to secure computation with penalties. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 406–417 (2016)

30.

Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely fair SFE and coalition-safe cheap talk. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, 25–28 July 2004, pp. 1–10 (2004)

31.

Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: Yung, M. (ed.) Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, 18–22 August 2002, Proceedings. LNCS, vol. 2442, pp. 111–126. Springer, Cham (2002). https://doi.org/10.1007/3-540-45708-9_8

32.

Pass, R., Shi, E., Tramèr, F.: Formal abstractions for attested execution secure processors. In: Coron, J.S., Nielsen, J. (eds.) Advances in Cryptology - EUROCRYPT 2017–36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 30 April–4 May 2017, Proceedings, Part I. LNCS, vol. 10210, pp. 260–289. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_10

33.

Pinkas, B.: Fair secure two-party computation. In: Biham, E. (ed.) Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 4–8 May 2003, Proceedings. LNCS, vol. 2656, pp. 87–105. Springer, Cham (2003). https://doi.org/10.1007/3-540-39200-9_6

34.

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

35.

Raghuraman, S., Yang, Y.: Just how fair is an unreactive world. IACR Cryptol. ePrint Arch. 2022, 1655 (2022)

36.

Sinha, R., Gaddam, S., Kumaresan, R.: LucidiTEE: policy-based fair computing at scale. IACR Cryptol. ePrint Arch. 2019, 178 (2019)

37.

Yao, A.C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, pp. 162–167 (1986)

Titel: Synchronizable Fair Exchange
verfasst von: Ranjit Kumaresan
Srinivasan Raghuraman
Adam Sealfon
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48614-2

Electronic ISBN: 978-3-031-48615-9

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48615-9_15

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