On fully-secure honest majority MPC without \(n^2\) round overhead. (English) Zbl 07927366
Aly, Abdelrahaman (ed.) et al., Progress in cryptology – LATINCRYPT 2023. 8th international conference on cryptology and information security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3–6, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14168, 47-66 (2023).
Summary: Fully secure multiparty computation (or guaranteed output delivery) among \(n\) parties can be achieved with perfect security if the number of corruptions \(t\) is less than \(n/3\), or with statistical security with the help of a broadcast channel if \(t<n/2\). In the case of \(t<n/3\), it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of \(\varOmega (\mathsf{depth}(C) + n)\) in the worst case. The number of rounds can be reduced to \(O(\mathsf{depth}(C))\) by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For \(t<n/2\) it is also known that linear communication complexity is achievable, but at the cost of \(\varOmega (\mathsf{depth}(C) + n^2)\) rounds, due to the use of a technique called dispute control. However, in contrast to the \(t<n/3\) setting, it is not known how to reduce this round count for \(t<n/2\) to \(O(\mathsf{depth}(C))\), neither allowing for larger communication, or by using correlated randomness.
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for \(t<n/2\) in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only \(O(\mathsf{depth}(C))\), without the additive \(n^2\) term that appears from the use of dispute control. While on the \(t<n/3\) such result requires circuits of width \(\varOmega (n)\), in our case circuits must be of width \(\varOmega (n^2)\), leaving it as an interesting future problem to reduce this gap. Our \(O(\mathsf{depth}(C))\) round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the \(t<n/3\) setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the \(t<n/2\) case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to quadratic communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.
For the entire collection see [Zbl 07831456].
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for \(t<n/2\) in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only \(O(\mathsf{depth}(C))\), without the additive \(n^2\) term that appears from the use of dispute control. While on the \(t<n/3\) such result requires circuits of width \(\varOmega (n)\), in our case circuits must be of width \(\varOmega (n^2)\), leaving it as an interesting future problem to reduce this gap. Our \(O(\mathsf{depth}(C))\) round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the \(t<n/3\) setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the \(t<n/2\) case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to quadratic communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.
For the entire collection see [Zbl 07831456].
MSC:
| 94A60 | Cryptography |
| 68P25 | Data encryption (aspects in computer science) |
| 68M14 | Distributed systems |
References:
| [1] | Abraham, I., Asharov,G., Patil, S., Patra, A.: Asymptotically free broadcast in constant expected time via packed vss. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, 7-10 November 2022, Proceedings, Part I, pp. 384-414. Springer, Heidelberg (2022). doi:10.1007/978-3-031-22318-1_14 · Zbl 1521.94021 |
| [2] | Abraham, I., Asharov,G., Patil, S., Patra, A.: Detect, pack and batch: perfectly-secure mpc with linear communication and constant expected time. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology-EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23-27 April 2023, Proceedings, Part II, pp. 251-281. Springer, Heidelberg (2023). doi:10.1007/978-3-031-30617-4_9 |
| [3] | Abraham, I.; Asharov, G.; Yanai, A.; Nissim, K.; Waters, B., Efficient perfectly secure computation with optimal resilience, Theory of Cryptography, 66-96, 2021, Cham: Springer, Cham · Zbl 1511.94036 · doi:10.1007/978-3-030-90453-1_3 |
| [4] | Bendlin, R.; Damgård, I.; Orlandi, C.; Zakarias, S.; Paterson, KG, Semi-homomorphic encryption and multiparty computation, Advances in Cryptology - EUROCRYPT 2011, 169-188, 2011, Heidelberg: Springer, Heidelberg · Zbl 1281.94015 · doi:10.1007/978-3-642-20465-4_11 |
| [5] | Boyle, E.; Gilboa, N.; Ishai, Y.; Nof, A.; Moriai, S.; Wang, H., Efficient fully secure computation via distributed zero-knowledge proofs, Advances in Cryptology - ASIACRYPT 2020, 244-276, 2020, Cham: Springer, Cham · Zbl 1511.94062 · doi:10.1007/978-3-030-64840-4_9 |
| [6] | Ben-Or, M., Goldwasser, A., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1-10 (1988) |
| [7] | Bishop, A.; Pastro, V.; Rajaraman, R.; Wichs, D.; Fischlin, M.; Coron, J-S, Essentially optimal robust secret sharing with maximal corruptions, Advances in Cryptology - EUROCRYPT 2016, 58-86, 2016, Heidelberg: Springer, Heidelberg · Zbl 1347.94068 · doi:10.1007/978-3-662-49890-3_3 |
| [8] | Ben-Sasson, E.; Fehr, S.; Ostrovsky, R.; Safavi-Naini, R.; Canetti, R., Near-linear unconditionally-secure multiparty computation with a dishonest minority, Advances in Cryptology - CRYPTO 2012, 663-680, 2012, Heidelberg: Springer, Heidelberg · Zbl 1296.94082 · doi:10.1007/978-3-642-32009-5_39 |
| [9] | Beerliová-Trubíniová, Z.; Hirt, M.; Halevi, S.; Rabin, T., Efficient multi-party computation with dispute control, Theory of Cryptography, 305-328, 2006, Heidelberg: Springer, Heidelberg · Zbl 1112.94023 · doi:10.1007/11681878_16 |
| [10] | Beerliová-Trubíniová, Z.; Hirt, M.; Canetti, R., Perfectly-secure MPC with linear communication complexity, Theory of Cryptography, 213-230, 2008, Heidelberg: Springer, Heidelberg · Zbl 1162.94336 · doi:10.1007/978-3-540-78524-8_13 |
| [11] | Cramer, R.; Damgård, IB; Nielsen, JB, Secure Multiparty Computation, 2015, Cambridge: Cambridge University Press, Cambridge · Zbl 1322.68003 · doi:10.1017/CBO9781107337756 |
| [12] | Damgård, I.; Nielsen, JB; Menezes, A., Scalable and unconditionally secure multiparty computation, Advances in Cryptology - CRYPTO 2007, 572-590, 2007, Heidelberg: Springer, Heidelberg · Zbl 1215.94041 · doi:10.1007/978-3-540-74143-5_32 |
| [13] | Fehr, S.; Yuan, C.; Ishai, Y.; Rijmen, V., Towards optimal robust secret sharing with security against a rushing adversary, Advances in Cryptology - EUROCRYPT 2019, 472-499, 2019, Cham: Springer, Cham · Zbl 1509.94159 · doi:10.1007/978-3-030-17659-4_16 |
| [14] | Gennaro, R., Rabin, M.O., Rabin, T.: Simplified vss and fast-track multiparty computations with applications to threshold cryptography. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pp. 101-111 (1998) · Zbl 1333.94036 |
| [15] | Goyal, V.; Song, Y.; Zhu, C.; Micciancio, D.; Ristenpart, T., Guaranteed output delivery comes free in honest majority MPC, Advances in Cryptology - CRYPTO 2020, 618-646, 2020, Cham: Springer, Cham · Zbl 1504.94143 · doi:10.1007/978-3-030-56880-1_22 |
| [16] | Hirt, M.; Maurer, U.; Przydatek, B.; Okamoto, T., Efficient secure multi-party computation, Advances in Cryptology — ASIACRYPT 2000, 143-161, 2000, Heidelberg: Springer, Heidelberg · Zbl 0966.94010 · doi:10.1007/3-540-44448-3_12 |
| [17] | Ishai, Y.; Kushilevitz, E.; Prabhakaran, M.; Sahai, A.; Yu, C-H; Robshaw, M.; Katz, J., Secure protocol transformations, Advances in Cryptology - CRYPTO 2016, 430-458, 2016, Heidelberg: Springer, Heidelberg · Zbl 1372.94430 · doi:10.1007/978-3-662-53008-5_15 |
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.
