On the round complexity of fully secure solitary MPC with honest majority. (English) Zbl 07891013
Rothblum, Guy (ed.) et al., Theory of cryptography. 21st international conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14370, 124-155 (2023).
Summary: We study the problem of secure multiparty computation for functionalities where only one party receives the output, to which we refer as solitary MPC. Recently, S. Halevi et al. [Lect. Notes Comput. Sci. 11891, 312–340 (2019; Zbl 1455.94163)] studied fully secure (i.e., with guaranteed output delivery) solitary MPC and showed impossibility of such protocols for certain functionalities when there is no honest majority among the parties.
In this work, we study the round complexity of fully secure solitary MPC in the honest majority setting and with computational security. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an \(n\)-party protocol against malicious adversaries corrupting up to \(t\) parties where \(n/3 \le t < n/2\). Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output?
For the entire collection see [Zbl 1542.94006].
In this work, we study the round complexity of fully secure solitary MPC in the honest majority setting and with computational security. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an \(n\)-party protocol against malicious adversaries corrupting up to \(t\) parties where \(n/3 \le t < n/2\). Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output?
- ●
- When there is a broadcast channel and no PKI:
- ●
- We start with a negative answer to the above question. In particular, we show that the exact round complexity of fully secure solitary MPC is 3, which is the same as fully secure standard MPC.
- ●
- We then study the minimal number of broadcast rounds needed to design round-optimal fully secure solitary MPC. We show that both the first and second rounds of broadcast are necessary when \(2 \lceil n/5 \rceil \le t < n/2\), whereas pairwise-private channels suffice in the last round. Notably, this result also applies to fully secure standard MPC in which all parties receive the output.
- ●
- When there is a PKI and no broadcast channel, nevertheless, we show more positive results:
- ●
- We show an upper bound of 5 rounds for any honest majority. This is superior to the super-constant lower bound for fully secure standard MPC in the exact same setting.
- ●
- We complement this by showing a lower bound of 4 rounds when \(3\lceil n/7 \rceil \le t < n/2\).
- ●
- For the special case of \(t=1\), \(n=3\), when the output receiving party does not have an input to the function, we show an upper bound of 2 rounds, which is optimal. When the output receiving party has an input to the function, we show a lower bound of 3, which matches an upper bound from prior work.
- ●
- For the special case of \(t=2,n=5\), we show a lower bound of 3 rounds (an upper bound of 4 follows from prior work).
For the entire collection see [Zbl 1542.94006].
MSC:
| 94A60 | Cryptography |
| 68P25 | Data encryption (aspects in computer science) |
| 94A62 | Authentication, digital signatures and secret sharing |
| 68N25 | Theory of operating systems |
Citations:
Zbl 1455.94163References:
| [1] | Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Synchronous byzantine agreement with expected O(1) rounds, expected o(n \({}^{\text{2}} )\) communication, and optimal resilience. In: FC (2019) · Zbl 1460.94033 |
| [2] | Alon, B., Cohen, R., Omri, E., Suad, T.: On the power of an honest majority in three-party computation without broadcast. In: TCC (2020) · Zbl 07496594 |
| [3] | Ananth, P.; Choudhuri, AR; Goel, A.; Jain, A.; Shacham, H.; Boldyreva, A., Round-optimal secure multiparty computation with honest majority, Advances in Cryptology - CRYPTO 2018, 395-424, 2018, Cham: Springer, Cham · Zbl 1436.94029 · doi:10.1007/978-3-319-96881-0_14 |
| [4] | Asharov, G.; Beimel, A.; Makriyannis, N.; Omri, E.; Dodis, Y.; Nielsen, JB, Complete characterization of fairness in secure two-party computation of Boolean functions, Theory of Cryptography, 199-228, 2015, Heidelberg: Springer, Heidelberg · Zbl 1354.94020 · doi:10.1007/978-3-662-46494-6_10 |
| [5] | Asharov, G.; Jain, A.; López-Alt, A.; Tromer, E.; Vaikuntanathan, V.; Wichs, D.; Pointcheval, D.; Johansson, T., Multiparty computation with low communication, computation and interaction via threshold FHE, Advances in Cryptology - EUROCRYPT 2012, 483-501, 2012, Heidelberg: Springer, Heidelberg · Zbl 1297.94042 · doi:10.1007/978-3-642-29011-4_29 |
| [6] | Badrinarayanan, S., Jain, A., Manohar, N., Sahai, A.: Threshold multi-key FHE and applications to round-optimal MPC. In: ASIACRYPT (2020) |
| [7] | Badrinarayanan, S., Miao, P., Mukherjee, P., Ravi, D.: On the round complexity of fully secure solitary mpc with honest majority. Cryptology ePrint Archive, Paper 2021/241 (2021). https://eprint.iacr.org/2021/241 |
| [8] | Bell, J.H., Bonawitz, K.A., Gascón, A., Lepoint, T., Raykova, M.: Secure single-server aggregation with (poly)logarithmic overhead. In: CCS, pp. 1253-1269. ACM (2020) |
| [9] | Bonawitz, K., et al. Practical secure aggregation for privacy-preserving machine learning. In: CCS (2017) |
| [10] | Boneh, D.; Gennaro, R.; Goldfeder, S.; Jain, A.; Kim, S.; Rasmussen, PMR; Sahai, A.; Shacham, H.; Boldyreva, A., Threshold cryptosystems from threshold fully homomorphic encryption, Advances in Cryptology - CRYPTO 2018, 565-596, 2018, Cham: Springer, Cham · Zbl 1444.94047 · doi:10.1007/978-3-319-96884-1_19 |
| [11] | Canetti, R., et al.: Fiat-shamir: from practice to theory. In: STOC (2019) · Zbl 1434.94060 |
| [12] | Chor, B.; Merritt, M.; Shmoys, DB, Simple constant-time consensus protocols in realistic failure models, J. ACM (JACM), 36, 3, 591-614, 1989 · Zbl 0675.90038 · doi:10.1145/65950.65956 |
| [13] | Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC (1986) |
| [14] | Cohen, R.; Garay, J.; Zikas, V.; Canteaut, A.; Ishai, Y., Broadcast-optimal two-round MPC, Advances in Cryptology - EUROCRYPT 2020, 828-858, 2020, Cham: Springer, Cham · Zbl 1492.94083 · doi:10.1007/978-3-030-45724-2_28 |
| [15] | Damgård, I.; Magri, B.; Ravi, D.; Siniscalchi, L.; Yakoubov, S.; Malkin, T.; Peikert, C., Broadcast-optimal two round MPC with an honest majority, Advances in Cryptology - CRYPTO 2021, 155-184, 2021, Cham: Springer, Cham · Zbl 1486.94147 · doi:10.1007/978-3-030-84245-1_6 |
| [16] | Damgård, I.; Ravi, D.; Siniscalchi, L.; Yakoubov, S.; Hazay, C.; Stam, M., Minimizing setup in broadcast-optimal two round MPC, Advances in Cryptology - EUROCRYPT 2023, 129-158, 2023, Heidelberg: Springer, Heidelberg · Zbl 1535.94049 · doi:10.1007/978-3-031-30617-4_5 |
| [17] | Dolev, D.; Strong, HR, Authenticated algorithms for Byzantine agreement, SIAM J. Comput., 12, 4, 656-666, 1983 · Zbl 0524.68021 · doi:10.1137/0212045 |
| [18] | Feldman, P.; Micali, S.; Ausiello, G.; Dezani-Ciancaglini, M.; Della Rocca, SR, An optimal probabilistic algorithm for synchronous Byzantine agreement, Automata, Languages and Programming, 341-378, 1989, Heidelberg: Springer, Heidelberg · Zbl 0684.68018 · doi:10.1007/BFb0035770 |
| [19] | Fischer, MJ; Lynch, NA, A lower bound for the time to assure interactive consistency, Inf. Process. Lett., 14, 4, 183-186, 1982 · Zbl 0493.68026 · doi:10.1016/0020-0190(82)90033-3 |
| [20] | Fitzi, M., Garay, J.A.: Efficient player-optimal protocols for strong and differential consensus. In: Borowsky, E., Rajsbaum, S. (eds.) 22nd ACM PODC, pp. 211-220. ACM (2003) · Zbl 1321.68043 |
| [21] | Fitzi, M.; Garay, JA; Maurer, U.; Ostrovsky, R.; Kilian, J., Minimal complete primitives for secure multi-party computation, Advances in Cryptology — CRYPTO 2001, 80-100, 2001, Heidelberg: Springer, Heidelberg · Zbl 1015.94541 · doi:10.1007/3-540-44647-8_5 |
| [22] | Garg, S.; Goel, A.; Jain, A.; Galbraith, SD; Moriai, S., The broadcast message complexity of secure multiparty computation, Advances in Cryptology - ASIACRYPT 2019, 426-455, 2019, Cham: Springer, Cham · Zbl 1456.94077 · doi:10.1007/978-3-030-34578-5_16 |
| [23] | Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The round complexity of verifiable secret sharing and secure multicast. In: STOC (2001) · Zbl 1317.68072 |
| [24] | Gennaro, R.; Ishai, Y.; Kushilevitz, E.; Rabin, T.; Yung, M., On 2-round secure multiparty computation, Advances in Cryptology — CRYPTO 2002, 178-193, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94527 · doi:10.1007/3-540-45708-9_12 |
| [25] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987) |
| [26] | Goldwasser, S.; Lindell, Y., Secure multi-party computation without agreement, J. Cryptol., 18, 247-287, 2005 · Zbl 1102.68472 · doi:10.1007/s00145-005-0319-z |
| [27] | 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) · Zbl 1281.94081 |
| [28] | Dov Gordon, S.; Liu, F-H; Shi, E.; Gennaro, R.; Robshaw, M., Constant-round MPC with fairness and guarantee of output delivery, Advances in Cryptology - CRYPTO 2015, 63-82, 2015, Heidelberg: Springer, Heidelberg · Zbl 1351.94047 · doi:10.1007/978-3-662-48000-7_4 |
| [29] | Halevi, S.; Ishai, Y.; Kushilevitz, E.; Makriyannis, N.; Rabin, T.; Hofheinz, D.; Rosen, A., On fully secure MPC with solitary output, Theory of Cryptography, 312-340, 2019, Cham: Springer, Cham · Zbl 1455.94163 · doi:10.1007/978-3-030-36030-6_13 |
| [30] | Halevi, S.; Lindell, Y.; Pinkas, B.; Rogaway, P., Secure computation on the web: computing without simultaneous interaction, Advances in Cryptology - CRYPTO 2011, 132-150, 2011, Heidelberg: Springer, Heidelberg · Zbl 1287.94070 · doi:10.1007/978-3-642-22792-9_8 |
| [31] | Karlin, A., Yao, A.: Probabilistic lower bounds for byzantine agreement. Unpublished document (1986) |
| [32] | Katz, J.; Koo, CY, On expected constant-round protocols for byzantine agreement, J. Comput. Syst. Sci., 75, 2, 91-112, 2009 · Zbl 1162.68431 · doi:10.1016/j.jcss.2008.08.001 |
| [33] | Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. (1982) · Zbl 0483.68021 |
| [34] | Lynch, NA, Distributed Algorithms, 1996, Burlington: Morgan Kaufmann, Burlington · Zbl 0877.68061 |
| [35] | Mohassel, A., Zhang, Y.: Secureml: a system for scalable privacy-preserving machine learning. In: IEEE S & P (2017) |
| [36] | Patra, A.; Ravi, D.; Shacham, H.; Boldyreva, A., On the exact round complexity of secure three-party computation, Advances in Cryptology - CRYPTO 2018, 425-458, 2018, Cham: Springer, Cham · Zbl 1436.94086 · doi:10.1007/978-3-319-96881-0_15 |
| [37] | Pease, M.; Shostak, R.; Lamport, L., Reaching agreement in the presence of faults, J. ACM, 27, 2, 228-234, 1980 · Zbl 0434.68031 · doi:10.1145/322186.322188 |
| [38] | Peikert, C.; Shiehian, S.; Boldyreva, A.; Micciancio, D., Noninteractive zero knowledge for NP from (plain) learning with errors, Advances in Cryptology - CRYPTO 2019, 89-114, 2019, Cham: Springer, Cham · Zbl 1456.94106 · doi:10.1007/978-3-030-26948-7_4 |
| [39] | Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986) |
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.
