Round-optimal and communication-efficient multiparty computation. (English) Zbl 1497.68210
Dunkelman, Orr (ed.) et al., Advances in cryptology – EUROCRYPT 2022. 41st annual international conference on the theory and applications of cryptographic techniques, Trondheim, Norway, May 30 – June 3, 2022. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 13275, 65-95 (2022).
Summary: Typical approaches for minimizing the round complexity of multiparty computation (MPC) come at the cost of increased communication complexity (CC) or the reliance on setup assumptions. A notable exception is the recent work of
P. Ananth et al. [Lect. Notes Comput. Sci. 11891, 199–228 (2019; Zbl 1455.94108)],
which used Functional Encryption (FE) combiners to obtain a round optimal (two-round) semi-honest MPC in the plain model with a CC proportional to the depth and input-output length of the circuit being computed – we refer to such protocols as circuit scalable. This leaves open the question of obtaining communication efficient protocols that are secure against malicious adversaries in the plain model, which we present in this work. Concretely, our two main contributions are:
1) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-scalable maliciously secure MPC protocols in the plain model, assuming (succinct) FE combiners.
2) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-independent – i.e., with a CC that depends only on the input-output length of the circuit – maliciously secure MPC protocols in the plain model, assuming Multi-Key Fully-Homomorphic Encryption (MFHE). Our constructions are based on a new compiler that turns a wide class of MPC protocols into k-delayed-input function MPC protocols (a notion we introduce), where the function that is being computed is specified only in the \(k\)-th round of the protocol.
As immediate corollaries of our two compilers, we derive (1) the first round-optimal and circuit-scalable maliciously secure MPC, and (2) the first round-optimal and circuit-independent maliciously secure MPC in the plain model. The latter MPC achieves the best to-date CC for a round-optimal malicious MPC protocol. In fact, it is even communication-optimal when the output size of the function being evaluated is smaller than its input size (e.g., for Boolean functions). All of our results are based on standard polynomial time assumptions.
For the entire collection see [Zbl 1493.94001].
1) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-scalable maliciously secure MPC protocols in the plain model, assuming (succinct) FE combiners.
2) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-independent – i.e., with a CC that depends only on the input-output length of the circuit – maliciously secure MPC protocols in the plain model, assuming Multi-Key Fully-Homomorphic Encryption (MFHE). Our constructions are based on a new compiler that turns a wide class of MPC protocols into k-delayed-input function MPC protocols (a notion we introduce), where the function that is being computed is specified only in the \(k\)-th round of the protocol.
As immediate corollaries of our two compilers, we derive (1) the first round-optimal and circuit-scalable maliciously secure MPC, and (2) the first round-optimal and circuit-independent maliciously secure MPC in the plain model. The latter MPC achieves the best to-date CC for a round-optimal malicious MPC protocol. In fact, it is even communication-optimal when the output size of the function being evaluated is smaller than its input size (e.g., for Boolean functions). All of our results are based on standard polynomial time assumptions.
For the entire collection see [Zbl 1493.94001].
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68N20 | Theory of compilers and interpreters |
| 68Q11 | Communication complexity, information complexity |
| 94A60 | Cryptography |
Citations:
Zbl 1455.94108References:
| [1] | Ananth, P.; Badrinarayanan, S.; Jain, A.; Manohar, N.; Sahai, A.; Hofheinz, D.; Rosen, A., From FE combiners to secure MPC and back, Theory of Cryptography, 199-228 (2019), Cham: Springer, Cham · Zbl 1455.94108 · doi:10.1007/978-3-030-36030-6_9 |
| [2] | Ananth, P., Jain, A., Jin, Z., Malavolta, G.: Multikey fhe in the plain model. Cryptology ePrint Archive, Report 2020/180 (2020). https://eprint.iacr.org/2020/180 · Zbl 1479.94113 |
| [3] | Asharov, G., Jain, A., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. Cryptology ePrint Archive, Report 2011/613 (2011). https://eprint.iacr.org/2011/613 |
| [4] | Badrinarayanan, S.; Goyal, V.; Jain, A.; Kalai, YT; Khurana, D.; Sahai, A.; Shacham, H.; Boldyreva, A., Promise zero knowledge and its applications to round optimal MPC, Advances in Cryptology - CRYPTO 2018, 459-487 (2018), Cham: Springer, Cham · Zbl 1436.94035 · doi:10.1007/978-3-319-96881-0_16 |
| [5] | Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503-513. ACM Press, May 1990. doi:10.1145/100216.100287 |
| [6] | Benhamouda, F.; Lin, H.; Nielsen, JB; Rijmen, V., k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits, Advances in Cryptology - EUROCRYPT 2018, 500-532 (2018), Cham: Springer, Cham · Zbl 1428.94060 · doi:10.1007/978-3-319-78375-8_17 |
| [7] | Blum, M.: Coin flipping by telephone. In: Gersho, A. (ed.) CRYPTO’81, vol. ECE Report 82-04, pp. 11-15. U.C. Santa Barbara, Dept. of Elec. and Computer Eng. (1981) |
| [8] | Boneh, D.; Sahai, A.; Waters, B.; Ishai, Y., Functional encryption: definitions and challenges, Theory of Cryptography, 253-273 (2011), Heidelberg: Springer, Heidelberg · Zbl 1295.94027 · doi:10.1007/978-3-642-19571-6_16 |
| [9] | Boyle, E.; Gilboa, N.; Ishai, Y.; Coron, J-S; Nielsen, JB, Group-based secure computation: optimizing rounds, communication, and computation, Advances in Cryptology - EUROCRYPT 2017, 163-193 (2017), Cham: Springer, Cham · Zbl 1415.94414 · doi:10.1007/978-3-319-56614-6_6 |
| [10] | Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309-325. ACM, January 2012. doi:10.1145/2090236.2090262 · Zbl 1347.68120 |
| [11] | Rai Choudhuri, A.; Ciampi, M.; Goyal, V.; Jain, A.; Ostrovsky, R.; Pass, R.; Pietrzak, K., Round optimal secure multiparty computation from minimal assumptions, Theory of Cryptography, 291-319 (2020), Cham: Springer, Cham · Zbl 07496583 · doi:10.1007/978-3-030-64378-2_11 |
| [12] | Choudhuri, AR; Ciampi, M.; Goyal, V.; Jain, A.; Ostrovsky, R.; Nissim, K.; Waters, B., Oblivious transfer from trapdoor permutations in minimal rounds, Theory of Cryptography, 518-549 (2021), Cham: Springer, Cham · Zbl 1511.94077 · doi:10.1007/978-3-030-90453-1_18 |
| [13] | Ciampi, M.; Ostrovsky, R.; Siniscalchi, L.; Visconti, I.; Kalai, Y.; Reyzin, L., Round-optimal secure two-party computation from trapdoor permutations, Theory of Cryptography, 678-710 (2017), Cham: Springer, Cham · Zbl 1410.94057 · doi:10.1007/978-3-319-70500-2_23 |
| [14] | Ciampi, M., Ostrovsky, R., Waldner, H., Zikas, V.: Round-optimal and communication-efficient multiparty computation. Cryptology ePrint Archive, Report 2020/1437 (2020). https://eprint.iacr.org/2020/1437 |
| [15] | Cohen, R.; Shelat, A.; Wichs, D.; Boldyreva, A.; Micciancio, D., Adaptively secure MPC with sublinear communication complexity, Advances in Cryptology - CRYPTO 2019, 30-60 (2019), Cham: Springer, Cham · Zbl 1483.68134 · doi:10.1007/978-3-030-26951-7_2 |
| [16] | Dodis, Y.; Halevi, S.; Rothblum, RD; Wichs, D.; Robshaw, M.; Katz, J., Spooky encryption and its applications, Advances in Cryptology - CRYPTO 2016, 93-122 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94045 · doi:10.1007/978-3-662-53015-3_4 |
| [17] | Friolo, D.; Masny, D.; Venturi, D.; Hofheinz, D.; Rosen, A., A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement, Theory of Cryptography, 111-130 (2019), Cham: Springer, Cham · Zbl 1455.94154 · doi:10.1007/978-3-030-36030-6_5 |
| [18] | Garg, S.; Mukherjee, P.; Pandey, O.; Polychroniadou, A.; Fischlin, M.; Coron, J-S, The exact round complexity of secure computation, Advances in Cryptology - EUROCRYPT 2016, 448-476 (2016), Heidelberg: Springer, Heidelberg · Zbl 1371.94637 · doi:10.1007/978-3-662-49896-5_16 |
| [19] | Garg, S.; Sahai, A.; Safavi-Naini, R.; Canetti, R., Adaptively secure multi-party computation with dishonest majority, Advances in Cryptology - CRYPTO 2012, 105-123 (2012), Heidelberg: Springer, Heidelberg · Zbl 1294.94047 · doi:10.1007/978-3-642-32009-5_8 |
| [20] | Garg, S., Srinivasan, A.: Garbled protocols and two-round MPC from bilinear maps. In: Umans, C. (ed.) 58th FOCS, pp. 588-599. IEEE Computer Society Press, October 2017. doi:10.1109/FOCS.2017.60 |
| [21] | Garg, S.; Srinivasan, A.; Nielsen, JB; Rijmen, V., Two-round multiparty secure computation from minimal assumptions, Advances in Cryptology - EUROCRYPT 2018, 468-499 (2018), Cham: Springer, Cham · Zbl 1428.94072 · doi:10.1007/978-3-319-78375-8_16 |
| [22] | Goldreich, O.: The Foundations of Cryptography - Volume 2 Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011 |
| [23] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218-229. ACM Press, May 1987. doi:10.1145/28395.28420 |
| [24] | Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 695-704. ACM Press, June 2011. doi:10.1145/1993636.1993729 · Zbl 1288.68020 |
| [25] | Halevi, S.; Hazay, C.; Polychroniadou, A.; Venkitasubramaniam, M.; Shacham, H.; Boldyreva, A., Round-optimal secure multi-party computation, Advances in Cryptology - CRYPTO 2018, 488-520 (2018), Cham: Springer, Cham · Zbl 1436.94070 · doi:10.1007/978-3-319-96881-0_17 |
| [26] | Ishai, Y.; Kushilevitz, E.; Paskin, A.; Rabin, T., Secure multiparty computation with minimal interaction, Advances in Cryptology - CRYPTO 2010, 577-594 (2010), Heidelberg: Springer, Heidelberg · Zbl 1283.94093 · doi:10.1007/978-3-642-14623-7_31 |
| [27] | Ishai, Y.; Prabhakaran, M.; Sahai, A.; Wagner, D., Founding cryptography on oblivious transfer – efficiently, Advances in Cryptology - CRYPTO 2008, 572-591 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94037 · doi:10.1007/978-3-540-85174-5_32 |
| [28] | Katz, J.; Ostrovsky, R.; Franklin, M., Round-optimal secure two-party computation, Advances in Cryptology - CRYPTO 2004, 335-354 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.94027 · doi:10.1007/978-3-540-28628-8_21 |
| [29] | Katz, J.; Ostrovsky, R.; Smith, A.; Biham, E., Round efficiency of multi-party computation with a dishonest majority, Advances in Cryptology — EUROCRYPT 2003, 578-595 (2003), Heidelberg: Springer, Heidelberg · Zbl 1038.94539 · doi:10.1007/3-540-39200-9_36 |
| [30] | Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC, pp. 20-31. ACM Press, May 1988. doi:10.1145/62212.62215 |
| [31] | Lindell, Y.; Pinkas, B., A proof of security of yao’s protocol for two-party computation, J. Cryptol., 22, 2, 161-188 (2008) · Zbl 1159.94364 · doi:10.1007/s00145-008-9036-8 |
| [32] | López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Karloff, H.J., Pitassi, T. (eds.) 44th ACM STOC, pp. 1219-1234. ACM Press, May 2012. doi:10.1145/2213977.2214086 · Zbl 1286.68114 |
| [33] | Morgan, A.; Pass, R.; Polychroniadou, A.; Canteaut, A.; Ishai, Y., Succinct non-interactive secure computation, Advances in Cryptology - EUROCRYPT 2020, 216-245 (2020), Cham: Springer, Cham · Zbl 07496551 · doi:10.1007/978-3-030-45724-2_8 |
| [34] | Mukherjee, P.; Wichs, D.; Fischlin, M.; Coron, J-S, Two round multiparty computation via multi-key FHE, Advances in Cryptology - EUROCRYPT 2016, 735-763 (2016), Heidelberg: Springer, Heidelberg · Zbl 1351.94060 · doi:10.1007/978-3-662-49896-5_26 |
| [35] | O’Neill, A.: Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556 (2010). https://eprint.iacr.org/2010/556 |
| [36] | Paskin-Cherniavsky, A.: Secure computation with minimal interaction. Ph.D. thesis, Computer Science Department, Technion (2012) · Zbl 1352.94075 |
| [37] | Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Babai, L. (ed.) 36th ACM STOC, pp. 232-241. ACM Press, June 2004. doi:10.1145/1007352.1007393 · Zbl 1192.68077 |
| [38] | Pass, R.; Wee, H.; Gilbert, H., Constant-round non-malleable commitments from sub-exponential one-way functions, Advances in Cryptology - EUROCRYPT 2010, 638-655 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94089 · doi:10.1007/978-3-642-13190-5_32 |
| [39] | Quach, W., Wee, H., Wichs, D.: Laconic function evaluation and applications. In: Thorup, M. (ed.) 59th FOCS, pp. 859-870. IEEE Computer Society Press, October 2018. doi:10.1109/FOCS.2018.00086 |
| [40] | Sahai, A.; Waters, B.; Cramer, R., Fuzzy identity-based encryption, Advances in Cryptology - EUROCRYPT 2005, 457-473 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94355 · doi:10.1007/11426639_27 |
| [41] | Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: 51st FOCS, pp. 531-540. IEEE Computer Society Press, October 2010. doi:10.1109/FOCS.2010.87 |
| [42] | Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162-167. IEEE Computer Society Press, October 1986. doi:10.1109/SFCS.1986.25 |
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.
