Minimizing setup in broadcast-optimal two round MPC. (English) Zbl 1535.94049
Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14005, 129-158 (2023).
Summary: In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of R. Cohen et al. [Lect. Notes Comput. Sci. 12106, 828–858 (2020; Zbl 1492.94083)] and I. Damgård et al. [ibid. 12826, 155–184 (2021; Zbl 1486.94147)] give tight characterizations of which security guarantees are achievable for various thresholds in each communication structure.
In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority).
Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. [loc. cit.]. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round.
We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.
For the entire collection see [Zbl 1525.94002].
In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority).
Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. [loc. cit.]. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round.
We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.
For the entire collection see [Zbl 1525.94002].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ananth, P., Choudhuri, A.R., Goel, A., Jain, A.: Two round information-theoretic MPC with malicious security. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2019, Part II. Lecture Notes in Computer Science, vol. 11477, pp. 532-561. Springer, Heidelberg, Germany, Darmstadt, Germany (May 19-23, 2019). doi:10.1007/978-3-030-17656-3_19 · Zbl 1524.68142 |
| [2] | Badrinarayanan, S., Miao, P., Mukherjee, P., Ravi, D.: On the round complexity of fully secure solitary mpc with honest majority. Cryptology ePrint Archive, Report 2021/241 (2021), https://eprint.iacr.org/2021/241 |
| [3] | Bellare, M., Hoang, V.T., Rogaway, P.: Adaptively secure garbling with applications to one-time programs and secure outsourcing. In: Wang, X., Sako, K. (eds.) Advances in Cryptology - ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 134-153. Springer, Heidelberg, Germany, Beijing, China (Dec 2-6, 2012). doi:10.1007/978-3-642-34961-4_10 · Zbl 1292.94027 |
| [4] | Benhamouda, F., Lin, H.: k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018, Part II. Lecture Notes in Computer Science, vol. 10821, pp. 500-532. Springer, Heidelberg, Germany, Tel Aviv, Israel (Apr 29 - May 3, 2018). doi:10.1007/978-3-319-78375-8_17 · Zbl 1428.94060 |
| [5] | Chen, M., Cohen, R., Doerner, J., Kondi, Y., Lee, E., Rosefield, S., shelat, a.: Multiparty generation of an RSA modulus. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology - CRYPTO 2020, Part III. Lecture Notes in Computer Science, vol. 12172, pp. 64-93. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 17-21, 2020). doi:10.1007/978-3-030-56877-1_3 · Zbl 1504.94121 |
| [6] | Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th Annual ACM Symposium on Theory of Computing. pp. 364-369. ACM Press, Berkeley, CA, USA (May 28-30, 1986). doi:10.1145/12130.12168 |
| [7] | Cohen, R., Garay, J.A., Zikas, V.: Broadcast-optimal two-round MPC. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020, Part II. Lecture Notes in Computer Science, vol. 12106, pp. 828-858. Springer, Heidelberg, Germany, Zagreb, Croatia (May 10-14, 2020). doi:10.1007/978-3-030-45724-2_28 · Zbl 1492.94083 |
| [8] | Cohen, R., Lindell, Y.: Fairness versus guaranteed output delivery in secure multiparty computation. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014, Part II. Lecture Notes in Computer Science, vol. 8874, pp. 466-485. Springer, Heidelberg, Germany, Kaoshiung, Taiwan, R.O.C. (Dec 7-11, 2014). doi:10.1007/978-3-662-45608-8_25 · Zbl 1317.94099 |
| [9] | Damgård, I., Magri, B., Ravi, D., Siniscalchi, L., Yakoubov, S.: Broadcast-optimal two round MPC with an honest majority. In: Crypto. pp. 155-184. Lecture Notes in Computer Science, Springer, Heidelberg, Germany (2021). doi:10.1007/978-3-030-84245-1_6 · Zbl 1486.94147 |
| [10] | Damgård, I., Ravi, D., Siniscalchi, L., Yakoubov, S.: Minimizing setup in broadcast-optimal two round MPC. Cryptology ePrint Archive, Report 2021/241 (2022), https://eprint.iacr.org/2022/293 · Zbl 1486.94147 |
| [11] | Ganesh, C., Patra, A.: Broadcast extensions with optimal communication and round complexity. In: Giakkoupis, G. (ed.) 35th ACM Symposium Annual on Principles of Distributed Computing. pp. 371-380. Association for Computing Machinery, Chicago, IL, USA (Jul 25-28, 2016). doi:10.1145/2933057.2933082 · Zbl 1373.68045 |
| [12] | Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018, Part II. Lecture Notes in Computer Science, vol. 10821, pp. 468-499. Springer, Heidelberg, Germany, Tel Aviv, Israel (Apr 29 - May 3, 2018). doi:10.1007/978-3-319-78375-8_16 · Zbl 1428.94072 |
| [13] | Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: On 2-round secure multiparty computation. In: Yung, M. (ed.) Advances in Cryptology - CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442, pp. 178-193. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 18-22, 2002). doi:10.1007/3-540-45708-9_12 · Zbl 1026.94527 |
| [14] | Goel, A., Jain, A., Prabhakaran, M., Raghunath, R.: On communication models and best-achievable security in two-round MPC. TCC p. 690 (2021) · Zbl 1511.94103 |
| [15] | Gordon, S.D., Liu, F.H., Shi, E.: Constant-round MPC with fairness and guarantee of output delivery. In: Gennaro, R., Robshaw, M.J.B. (eds.) Advances in Cryptology - CRYPTO 2015, Part II. Lecture Notes in Computer Science, vol. 9216, pp. 63-82. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16-20, 2015). doi:10.1007/978-3-662-48000-7_4 · Zbl 1351.94047 |
| [16] | Hirt, M., Raykov, P.: Multi-valued byzantine broadcast: The \(t < n\) case. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014, Part II. Lecture Notes in Computer Science, vol. 8874, pp. 448-465. Springer, Heidelberg, Germany, Kaoshiung, Taiwan, R.O.C. (Dec 7-11, 2014). doi:10.1007/978-3-662-45608-8_24 · Zbl 1317.94112 |
| [17] | Ishai, Y., Kumaresan, R., Kushilevitz, E., Paskin-Cherniavsky, A.: Secure computation with minimal interaction, revisited. In: Gennaro, R., Robshaw, M.J.B. (eds.) Advances in Cryptology - CRYPTO 2015, Part II. Lecture Notes in Computer Science, vol. 9216, pp. 359-378. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16-20, 2015). doi:10.1007/978-3-662-48000-7_18 · Zbl 1352.94075 |
| [18] | Ishai, Y., Kushilevitz, E., Paskin, A.: Secure multiparty computation with minimal interaction. In: Rabin, T. (ed.) Advances in Cryptology - CRYPTO 2010. Lecture Notes in Computer Science, vol. 6223, pp. 577-594. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 15-19, 2010). doi:10.1007/978-3-642-14623-7_31 · Zbl 1283.94093 |
| [19] | Lamport, L.; Shostak, RE; Pease, MC, The byzantine generals problem, ACM Trans. Program. Lang. Syst., 4, 3, 382-401 (1982) · Zbl 0483.68021 · doi:10.1145/357172.357176 |
| [20] | Patra, A., Ravi, D.: On the exact round complexity of secure three-party computation. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology - CRYPTO 2018, Part II. Lecture Notes in Computer Science, vol. 10992, pp. 425-458. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 19-23, 2018). doi:10.1007/978-3-319-96881-0_15 · Zbl 1436.94086 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
