Constant-round multiparty private function evaluation with (quasi-)linear complexities. (English) Zbl 1540.68092
Tibouchi, Mehdi (ed.) et al., Applied cryptography and network security. 21st international conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13906, 115-142 (2023).
Summary: Private function evaluation (PFE) is a special case of secure multiparty computation. In multiparty PFE, the party \(P_1\) holds its private n-variable function \(f\) and private input \(x_1\), while other parties \(P_i\) (\(n\ge i\ge 2\)) hold their private input \(x_i\). All \(n\) participants can jointly evaluate the function \(f\), and learn nothing from the interactions except the result \(f(x_1,\dots,x_n)\) (known to a subset or all of the parties). The existing multiparty PFE protocols (e.g., [P. Mohassel and S. Sadeghian, Lect. Notes Comput. Sci. 7881, 557–574 (2013; Zbl 1312.94081); Lect. Notes Comput. Sci. 8874, 486–505 (2014; Zbl 1317.94129)]) are with round complexity \(O(g)\) (\(g\) is the circuit size) which makes them extremely unpractical. In this work, we propose for the first time constant-round multiparty PFE protocols that are secure against any number of corrupted parties under the semi-honest security model. We design our first construction from oblivious evaluation of switching network (OSN) protocol [Zbl 1312.94081],
which only needs 9 rounds of interaction and can achieve quasi-linear communication and computation complexities (i.e., \(O(ng\log (g)))\). Our second construction is based on singly homomorphic encryption, which only needs 8 rounds of interaction and can achieve linear complexities. The OSN-based construction also benefits from the design trick that it only relies on symmetric operations (which makes it really efficient in actual executions). We further optimize our constructions by half-gate technology.
For the entire collection see [Zbl 1523.94004].
For the entire collection see [Zbl 1523.94004].
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68P27 | Privacy of data |
| 94A60 | Cryptography |
Keywords:
private function evaluation; secure multiparty computation; constant rounds; linear complexity; quasi-linear complexitySoftware:
ABYReferences:
| [1] | Alhassan, MY; Günther, D.; Kiss, Á.; Schneider, T., Efficient and scalable universal circuits, J. Cryptol., 33, 3, 1216-1271 (2020) · Zbl 1462.94027 · doi:10.1007/s00145-020-09346-z |
| [2] | Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS 2013, pp. 535-548. ACM (2013) |
| [3] | Barni, M.; Failla, P.; Kolesnikov, V.; Lazzeretti, R.; Sadeghi, A.; Schneider, T.; Backes, M.; Ning, P., Secure evaluation of private linear branching programs with medical applications, ESORICS 2009, 424-439 (2009), Heidelberg: Springer, Heidelberg |
| [4] | Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Proceedings of the Twenty-second Annual ACM STOC, pp. 503-513 (1990) |
| [5] | Ben-Efraim, A., Lindell, Y., Omri, E.: Optimizing semi-honest secure multiparty computation for the internet. In: CCS 2016, pp. 578-590. ACM (2016) |
| [6] | Biçer, O., Bingol, M.A., Kiraz, M.S., Levi, A.: Highly efficient and re-executable private function evaluation with linear complexity. IEEE Transactions on Dependable and Secure Computing (2020) |
| [7] | Bingöl, MA; Biçer, O.; Kiraz, MS; Levi, A., An efficient 2-party private function evaluation protocol based on half gates, Comput. J., 62, 4, 598-613 (2019) · doi:10.1093/comjnl/bxy136 |
| [8] | Choi, SG; Katz, J.; Malozemoff, AJ; Zikas, V.; Garay, JA; Gennaro, R., Efficient Three-Party Computation from Cut-and-Choose, Advances in Cryptology - CRYPTO 2014, 513-530 (2014), Heidelberg: Springer, Heidelberg · Zbl 1335.94039 · doi:10.1007/978-3-662-44381-1_29 |
| [9] | Demmler, D., Schneider, T., Zohner, M.: ABY - A framework for efficient mixed-protocol secure two-party computation. In: NDSS 2015. The Internet Society (2015) |
| [10] | ElGamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31, 4, 469-472 (1985) · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074 |
| [11] | 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 STOC, pp. 218-229. ACM (1987) |
| [12] | Günther, D.; Kiss, Á.; Schneider, T.; Takagi, T.; Peyrin, T., More Efficient Universal Circuit Constructions, Advances in Cryptology - ASIACRYPT 2017, 443-470 (2017), Cham: Springer, Cham · Zbl 1409.94877 · doi:10.1007/978-3-319-70697-9_16 |
| [13] | Holz, M.; Kiss, Á.; Rathee, D.; Schneider, T.; Chen, L.; Li, N.; Liang, K.; Schneider, S., Linear-complexity private function evaluation is practical, Computer Security - ESORICS 2020, 401-420 (2020), Cham: Springer, Cham · Zbl 1522.68088 · doi:10.1007/978-3-030-59013-0_20 |
| [14] | Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS 2012. The Internet Society (2012) |
| [15] | Ishai, Y.; Kilian, J.; Nissim, K.; Petrank, E.; Boneh, D., Extending oblivious transfers efficiently, Advances in Cryptology - CRYPTO 2003, 145-161 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94422 · doi:10.1007/978-3-540-45146-4_9 |
| [16] | Katz, J.; Malka, L.; Lee, DH; Wang, X., Constant-round private function evaluation with linear complexity, Advances in Cryptology - ASIACRYPT 2011, 556-571 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94050 · doi:10.1007/978-3-642-25385-0_30 |
| [17] | Katz, J.; Ranellucci, S.; Rosulek, M.; Wang, X.; Shacham, H.; Boldyreva, A., Optimizing authenticated garbling for faster secure two-party computation, Advances in Cryptology - CRYPTO 2018, 365-391 (2018), Cham: Springer, Cham · Zbl 1457.94147 · doi:10.1007/978-3-319-96878-0_13 |
| [18] | Kiss, Á.; Schneider, T.; Fischlin, M.; Coron, J-S, Valiant’s universal circuit is practical, Advances in Cryptology - EUROCRYPT 2016, 699-728 (2016), Heidelberg: Springer, Heidelberg · Zbl 1385.94049 · doi:10.1007/978-3-662-49890-3_27 |
| [19] | Kolesnikov, V.; Kumaresan, R.; Canetti, R.; Garay, JA, Improved OT extension for transferring short secrets, Advances in Cryptology - CRYPTO 2013, 54-70 (2013), Heidelberg: Springer, Heidelberg · Zbl 1316.94080 · doi:10.1007/978-3-642-40084-1_4 |
| [20] | Lipmaa, H., Mohassel, P., Sadeghian, S.: Valiant’s universal circuit: improvements, implementation, and applications. Cryptology ePrint Archive, Paper 2016/017 (2016). https://eprint.iacr.org/2016/017 |
| [21] | Liu, H.; Yu, Yu; Zhao, S.; Zhang, J.; Liu, W.; Hu, Z.; Malkin, T.; Peikert, C., Pushing the limits of Valiant’s universal circuits: simpler, tighter and more compact, Advances in Cryptology - CRYPTO 2021, 365-394 (2021), Cham: Springer, Cham · Zbl 1497.94193 · doi:10.1007/978-3-030-84245-1_13 |
| [22] | Liu, Y.; Wang, Q.; Yiu, S.; Hanaoka, G.; Shikata, J.; Watanabe, Y., Making private function evaluation safer, faster, and simpler, PKC 2022, 349-378 (2022), Heidelberg: Springer, Heidelberg · Zbl 1492.94144 · doi:10.1007/978-3-030-97121-2_13 |
| [23] | Mohassel, P.; Sadeghian, SS; Johansson, T.; Nguyen, PQ, How to hide circuits in MPC an efficient framework for private function evaluation, EUROCRYPT 2013, 557-574 (2013), Heidelberg: Springer, Heidelberg · Zbl 1312.94081 · doi:10.1007/978-3-642-38348-9_33 |
| [24] | Mohassel, P.; Sadeghian, SS; Smart, NP; Sarkar, P.; Iwata, T., Actively secure private function evaluation, ASIACRYPT 2014, 486-505 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94129 · doi:10.1007/978-3-662-45608-8_26 |
| [25] | Paillier, P.; Stern, J., Public-key cryptosystems based on composite degree residuosity classes, EUROCRYPT 1999, 223-238 (1999), Heidelberg: Springer, Heidelberg · Zbl 0933.94027 · doi:10.1007/3-540-48910-X_16 |
| [26] | Sadeghi, A.; Schneider, T.; Lee, PJ; Cheon, JH, Generalized universal circuits for secure evaluation of private functions with application to data classification, ICISC 2008, 336-353 (2008), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-00730-9_21 |
| [27] | Valiant, L.G.: Universal circuits (preliminary report). In: Proceedings of the Eighth Annual ACM STOC, pp. 196-203 (1976) · Zbl 0365.94044 |
| [28] | Waksman, A., A permutation network, J. ACM (JACM), 15, 1, 159-163 (1968) · Zbl 0157.23702 · doi:10.1145/321439.321449 |
| [29] | Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: CCS 2017, pp. 21-37. ACM (2017) |
| [30] | Wang, X., Ranellucci, S., Katz, J.: Global-scale secure multiparty computation. In: CCS 2017, pp. 39-56. ACM (2017) |
| [31] | Yang, K., Wang, X., Zhang, J.: More efficient MPC from improved triple generation and authenticated garbling. In: CCS 2020, pp. 1627-1646. ACM (2020) |
| [32] | Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: Fast extension for correlated OT with small communication. In: CCS 2020, pp. 1607-1626. ACM (2020) |
| [33] | Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (SFCS1986), pp. 162-167. IEEE (1986) |
| [34] | Zahur, S.; Rosulek, M.; Evans, D.; Oswald, E.; Fischlin, M., Two halves make a whole - reducing data transfer in garbled circuits using half gates, EUROCRYPT 2015, 220-250 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94662 · doi:10.1007/978-3-662-46803-6_8 |
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.
