Cheater Identification on a Budget: MPC with Identifiable Abort from Pairwise MACs
Pages 454 - 488
Abstract
Cheater identification in secure multi-party computation (MPC) allows the honest parties to agree upon the identity of a cheating party, in case the protocol aborts. In the context of a dishonest majority, this becomes especially critical, as it serves to thwart denial-of-service attacks and mitigate known impossibility results on ensuring fairness and guaranteed output delivery.
In this work, we present a new, lightweight approach to achieving identifiable abort in dishonest majority MPC. We avoid all of the heavy machinery used in previous works, instead relying on a careful combination of lightweight detection mechanisms and techniques from state-of-the-art protocols secure with (non-identifiable) abort.
At the core of our construction is a homomorphic, multi-receiver commitment scheme secure with identifiable abort. This commitment scheme can be constructed from cheap vector oblivious linear evaluation protocols based on learning parity with noise. To support cheater identification, we design a general compilation technique, similar to a compiler of Ishai et al. (Crypto 2014), but avoid its requirement for adaptive security of the underlying protocol. Instead, we rely on a different (and seemingly easier to achieve) property we call online extractability, which may be of independent interest. Our MPC protocol can be viewed as a version of the BDOZ MPC scheme (Bendlin et al., Eurocrypt 2011) based on pairwise information-theoretic MACs, enhanced to support cheater identification and a highly efficient preprocessing phase, essentially as efficient as the non-identifiable protocol of Le Mans (Rachuri & Scholl, Crypto 2022).
References
[1]
Attema, T., Dunning, V., Everts, M., Langenkamp, P.: Efficient compiler to covert security with public verifiability for honest majority MPC. In: Ateniese, G., Venturi, D. (eds.) Applied Cryptography and Network Security, ACNS 2022. LNCS, vol. 13269, pp. 663–683. Springer, Cham (2022).
[2]
Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. In: Vadhan, S.P. (eds.) Theory of Cryptography, TCC 2007. LNCS, vol. 4392, pp. 137–156. Springer, Heidelberg (2007).
[3]
Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, November 2019, pp. 291–308. ACM Press (2019)
[4]
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators from ring-LPN. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology, CRYPTO 2020. LNCS, vol. 12171, pp. 387–416 (2020). Springer, Cham.
[5]
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Lie, D., Mannan, M., Backes, M., Wang, X., (eds.) ACM CCS 2018, October 2018, pp. 896–912. ACM Press (2018)
[6]
Baum, C., David, B., Dowsley, R.: A framework for universally composable publicly verifiable cryptographic protocols. Cryptology ePrint Archive, Report 2020/207 (2020). https://eprint.iacr.org/2020/207
[7]
Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (eds.) Advances in Cryptology, EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011).
[8]
Baum C, Dittmer S, Scholl P, and Wang X Sok: vector OLE-based zero-knowledge protocols DCC 2023 91 11 3527-3561
[9]
Brandt, N.-P., Maier, S., Müller, T., Müller-Quade, J.: Constructing secure multi-party computation with identifiable abort. Cryptology ePrint Archive, Report 2020/153 (2020). https://eprint.iacr.org/2020/153
[10]
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, May 1990, pp. 503–513. ACM Press (1990)
[11]
Baum, C., Melissaris, N., Rachuri, R., Scholl, P.: Cheater identification on a budget: MPC with identifiable abort from pairwise macs. Cryptology ePrint Archive, Paper 2023/1548 (2023). https://eprint.iacr.org/2023/1548
[12]
Baum C, Orsini E, and Scholl P Hirt M and Smith A Efficient secure multiparty computation with identifiable abort Theory of Cryptography 2016 Heidelberg Springer 461-490
[13]
Baum, C., Orsini, E., Scholl, P., Soria-Vazquez, E.: Efficient constant-round MPC with identifiable abort and public verifiability. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology, CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 562–592. Springer, Cham (2020).
[14]
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, October 2001, pp. 136–145. IEEE Computer Society Press (2001)
[15]
Cohen, R., Doerner, J., Kondi, Y., Shelat, A.: Secure multiparty computation with identifiable abort from vindicating release. Cryptology ePrint Archive, Paper 2023/1136 (2023). https://eprint.iacr.org/2023/1136
[16]
Cunningham, R., Fuller, B., Yakoubov, S.: Catching MPC cheaters: identification and openability. In: Shikata, J. (eds.) Information Theoretic Security, ICITS 2017. LNCS, vol. 10681, pp. 110–134. Springer, Cham (2017).
[17]
Cohen, R., Garay, J., Zikas, V.: Broadcast-optimal two-round MPC. In: Canteaut, A., Ishai, Y. (eds) Advances in Cryptology, EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 828–858. Springer, Cham (2020).
[18]
Chen, M., et al.: Diogenes: lightweight scalable RSA modulus generation with a dishonest majority. In: 2021 IEEE Symposium on Security and Privacy, May 2021, pp. 590–607. IEEE Computer Society Press (2021)
[19]
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th ACM STOC, May 1986, pp. 364–369. ACM Press (1986)
[20]
Ciampi, M., Ravi, D., Siniscalchi, L., Waldner. H., Round-optimal multi-party computation with identifiable abort. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology, EUROCRYPT 2022, Part I. LNCS, May/June 2022, vol. 13275, pp. 335–364. Springer, Heidelberg (2022).
[21]
Damgård I, Magri B, Ravi D, Siniscalchi L, and Yakoubov S Malkin T and Peikert C Broadcast-optimal two round MPC with an honest majority Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 155-184
[22]
Damgård, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology, CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012).
[23]
Damgård, I., Ravi, D., Siniscalchi, L., Yakoubov, S.: Minimizing setup in broadcast-optimal two round MPC. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology, EUROCRYPT 2023, Part II. LNCS, vol. 14005, pp. 129–158. Springer, Heidelberg (2023).
[24]
Faust, S., Hazay, C., Kretzler, D., Schlosser, B.: Generic compiler for publicly verifiable covert multi-party computation. In: Canteaut, A., Standaert, F.X. (eds.) Advances in Cryptology, EUROCRYPT 2021, Part II. LNCS, vol. 12697, pp. 782–811. Springer, Cham (2021).
[25]
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, May 1987, pp. 218–229. ACM Press (1987)
[26]
Hazay, C., Venkitasubramaniam, M., Weiss, M.: Protecting distributed primitives against leakage: equivocal secret sharing and more. In: 3rd Conference on Information-Theoretic Cryptography, ITC 2022 (2022)
[27]
Ishai, Y., Ostrovsky, R., Seyalioglu, H.: Identifying cheaters without an honest majority. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 21–38. Springer, Heidelberg (2012).
[28]
Ishai, Y., Ostrovsky, R., Zikas, V.: Secure multi-party computation with identifiable abort. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology, CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 369–386. Springer, Heidelberg (2014).
[29]
Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013).
[30]
Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008).
[31]
Rachuri, R., Scholl, P.: Le mans: dynamic and fluid MPC for dishonest majority. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I. LNCS, vol. 13507, pp. 719–749. Springer, Heidelberg (2022).
[32]
Spini, G., Fehr, S.: Cheater detection in SPDZ multiparty computation. In: Nascimento, A.C.A., Barreto, P. (eds.) ICITS 2016. LNCS, vol. 10015, pp. 151–176. Springer, Cham (2016).
[33]
Scholl, P., Simkin, M., Siniscalchi, L.: Multiparty computation with covert security and public verifiability. In: 3rd Conference on Information-Theoretic Cryptography (2022)
[34]
Simkin, M., Siniscalchi, L., Yakoubov, S.: On sufficient oracles for secure computation with identifiable abort. In: Galdi, C., Jarecki, S. (eds.) Security and Cryptography for Networks, SCN 2022. LNCS, vol. 13409, pp. 494–515. Springer, Cham (2022).
[35]
Weng, C., Yang, K., Katz, J., Wang, X.: Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In: 2021 IEEE Symposium on Security and Privacy, May 2021, pp. 1074–1091. IEEE Computer Society Press (2021)
Index Terms
- Cheater Identification on a Budget: MPC with Identifiable Abort from Pairwise MACs
Index terms have been assigned to the content through auto-classification.
Recommendations
Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability
Advances in Cryptology – CRYPTO 2020AbstractRecent years have seen a tremendous growth in the interest in secure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial ...
Efficient Secure Multiparty Computation with Identifiable Abort
Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985We study secure multiparty computation MPC in the dishonest majority setting providing security with identifiable abort, where if the protocol aborts, the honest parties can agree upon the identity of a corrupt party. All known constructions that ...
Round-Optimal Multi-party Computation with Identifiable Abort
Advances in Cryptology – EUROCRYPT 2022AbstractSecure multi-party computation (MPC) protocols that are resilient to a dishonest majority allow the adversary to get the output of the computation while, at the same time, forcing the honest parties to abort. Aumann and Lindell introduced the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Aug 2024
508 pages
© International Association for Cryptologic Research 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 August 2024
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in