×

The price of active security in cryptographic protocols. (English) Zbl 1493.94034

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12106, 184-215 (2020).
Summary: We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field \(\mathbb{F}\) with constant communication overhead over the “passive-GMW” protocol. Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields [D. Genkin et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 495–504 (2014; Zbl 1315.94073)] or a constant number of parties [Y. Ishai et al., Lect. Notes Comput. Sci. 5157, 572–591 (2008; Zbl 1183.94037)].
Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality \(\mathcal{F}_{\textsc{MULT}} \), to an actively-secure protocol for general functionalities. Roughly, \( \mathcal{F}_{\textsc{MULT}}\) is parameterized by a linear-secret sharing scheme \(\mathcal{S} \), where it takes \(\mathcal{S} \)-shares of two secrets and returns \(\mathcal{S} \)-shares of their product.
We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of \(\mathcal{F}_{\textsc{MULT}} \), which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems; and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2.
Instantiating this compiler with an “honest-majority” implementations of \(\mathcal{F}_{\textsc{MULT}}\), we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol.
For the entire collection see [Zbl 1482.94003].

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
68N20 Theory of compilers and interpreters

Software:

Ligero
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: CCS, pp. 2087-2104 (2017)
[2] Applebaum, B.; Damgård, I.; Ishai, Y.; Nielsen, M.; Zichron, L.; Katz, J.; Shacham, H., Secure arithmetic computation with constant computational overhead, Advances in Cryptology - CRYPTO 2017, 223-254 (2017), Cham: Springer, Cham · Zbl 1407.94073 · doi:10.1007/978-3-319-63688-7_8
[3] Beaver, D.; Feigenbaum, J., Efficient multiparty protocols using circuit randomization, Advances in Cryptology — CRYPTO 1991, 420-432 (1992), Heidelberg: Springer, Heidelberg · Zbl 0789.68061 · doi:10.1007/3-540-46766-1_34
[4] Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503-513 (1990)
[5] Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC, pp. 1-10 (1988)
[6] 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
[7] Chaum, D.; Crépeau, C.; Damgård, I.; Pomerance, C., Multiparty unconditionally secure protocols (abstract), Advances in Cryptology — CRYPTO 1987, 462 (1988), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-48184-2_43
[8] Chen, H.; Cramer, R.; Dwork, C., Algebraic geometric secret sharing schemes and secure multi-party computations over small fields, Advances in Cryptology - CRYPTO 2006, 521-536 (2006), Heidelberg: Springer, Heidelberg · Zbl 1129.94016 · doi:10.1007/11818175_31
[9] Chida, K.; Shacham, H.; Boldyreva, A., Fast large-scale honest-majority MPC for malicious adversaries, Advances in Cryptology - CRYPTO 2018, 34-64 (2018), Cham: Springer, Cham · Zbl 1446.94118 · doi:10.1007/978-3-319-96878-0_2
[10] Cramer, R.; Damgård, I.; Nielsen, JB; Pfitzmann, B., Multiparty computation from threshold homomorphic encryption, Advances in Cryptology — EUROCRYPT 2001, 280-300 (2001), Heidelberg: Springer, Heidelberg · Zbl 1010.94553 · doi:10.1007/3-540-44987-6_18
[11] Damgård, I.; Ishai, Y.; Dwork, C., Scalable secure multiparty computation, Advances in Cryptology - CRYPTO 2006, 501-520 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.94394 · doi:10.1007/11818175_30
[12] Damgård, I.; Keller, M.; Larraia, E.; Pastro, V.; Scholl, P.; Smart, NP; Crampton, J.; Jajodia, S.; Mayes, K., Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits, Computer Security - ESORICS 2013, 1-18 (2013), Heidelberg: Springer, Heidelberg · Zbl 1406.94041 · doi:10.1007/978-3-642-40203-6_1
[13] 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
[14] Damgård, I.; Pastro, V.; Smart, N.; Zakarias, S.; Safavi-Naini, R.; Canetti, R., Multiparty computation from somewhat homomorphic encryption, Advances in Cryptology - CRYPTO 2012, 643-662 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94104 · doi:10.1007/978-3-642-32009-5_38
[15] Döttling, N., Ghosh, S., Nielsen, J.B., Nilges, T., Trifiletti, R.: TinyOLE: efficient actively secure two-party computation from oblivious linear function evaluation. In: CCS, pp. 2263-2276 (2017)
[16] Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: STOC, pp. 699-710 (1992)
[17] Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation. In: STOC, pp. 495-504 (2014) · Zbl 1315.94073
[18] Genkin, D.; Ishai, Y.; Weiss, M.; Hirt, M.; Smith, A., Binary AMD circuits from secure multiparty computation, Theory of Cryptography, 336-366 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94057 · doi:10.1007/978-3-662-53641-4_14
[19] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game acompleteness theorem for protocols with honest majority. In: STOC, pp. 218-229 (1987)
[20] Goyal, V.; Liu, Y.; Song, Y.; Boldyreva, A.; Micciancio, D., Communication-efficient unconditional MPC with guaranteed output delivery, Advances in Cryptology - CRYPTO 2019, 85-114 (2019), Cham: Springer, Cham · Zbl 1478.68093 · doi:10.1007/978-3-030-26951-7_4
[21] Gueron, S., Lindell, Y., Nof, A., Pinkas, B.: Fast garbling of circuits under standard assumptions. In: CCS, pp. 567-578 (2015) · Zbl 1400.94146
[22] Haitner, I.; Canetti, R., Semi-honest to malicious oblivious transfer—the black-box way, Theory of Cryptography, 412-426 (2008), Heidelberg: Springer, Heidelberg · Zbl 1162.94362 · doi:10.1007/978-3-540-78524-8_23
[23] Haitner, I.; Ishai, Y.; Kushilevitz, E.; Lindell, Y.; Petrank, E., Black-box constructions of protocols for secure computation, SIAM J. Comput., 40, 2, 225-266 (2011) · Zbl 1236.94056 · doi:10.1137/100790537
[24] Halevi, S.; Kalai, YT, Smooth projective hashing and two-message oblivious transfer, J. Cryptol., 25, 1, 158-193 (2012) · Zbl 1272.94033 · doi:10.1007/s00145-010-9092-8
[25] Hazay, C., Ishai, Y., Marcedone, A., Venkitasubramaniam, M.: Leviosa: Lightweight secure arithmetic computation. In: CCS, pp. 327-344 (2019)
[26] Hazay, C.; Ishai, Y.; Venkitasubramaniam, M.; Kalai, Y.; Reyzin, L., Actively secure garbled circuits with constant communication overhead in the plain model, Theory of Cryptography, 3-39 (2017), Cham: Springer, Cham · Zbl 1406.94059 · doi:10.1007/978-3-319-70503-3_1
[27] Hazay, C.; Scholl, P.; Soria-Vazquez, E.; Takagi, T.; Peyrin, T., Low cost constant round MPC combining BMR and oblivious transfer, Advances in Cryptology - ASIACRYPT 2017, 598-628 (2017), Cham: Springer, Cham · Zbl 1420.94072 · doi:10.1007/978-3-319-70694-8_21
[28] Hazay, C., Venkitasubramaniam, M., Weiss, M.: The price of active security in cryptographic protocols. IACR Cryptology ePrint Archive 2019, 1250 (2019). https://eprint.iacr.org/2019/1250
[29] Huang, Y.; Katz, J.; Kolesnikov, V.; Kumaresan, R.; Malozemoff, AJ; Garay, JA; Gennaro, R., Amortizing garbled circuits, Advances in Cryptology - CRYPTO 2014, 458-475 (2014), Heidelberg: Springer, Heidelberg · Zbl 1335.94052 · doi:10.1007/978-3-662-44381-1_26
[30] Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21-30 (2007) · Zbl 1232.68044
[31] 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
[32] 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
[33] Ishai, Y.; Prabhakaran, M.; Sahai, A.; Reingold, O., Secure arithmetic computation with no honest majority, Theory of Cryptography, 294-314 (2009), Heidelberg: Springer, Heidelberg · Zbl 1213.94111 · doi:10.1007/978-3-642-00457-5_18
[34] Keller, M.; Pastro, V.; Rotaru, D.; Nielsen, JB; Rijmen, V., Overdrive: making SPDZ great again, Advances in Cryptology - EUROCRYPT 2018, 158-189 (2018), Cham: Springer, Cham · Zbl 1415.94446 · doi:10.1007/978-3-319-78372-7_6
[35] Kolesnikov, V.; Schneider, T.; Aceto, L.; Damgård, I.; Goldberg, LA; Halldórsson, MM; Ingólfsdóttir, A.; Walukiewicz, I., Improved garbled circuit: free XOR gates and applications, Automata, Languages and Programming, 486-498 (2008), Heidelberg: Springer, Heidelberg · Zbl 1155.94374 · doi:10.1007/978-3-540-70583-3_40
[36] Lindell, Y.; Oxman, E.; Pinkas, B.; Rogaway, P., The IPS compiler: optimizations, variants and concrete efficiency, Advances in Cryptology - CRYPTO 2011, 259-276 (2011), Heidelberg: Springer, Heidelberg · Zbl 1288.68023 · doi:10.1007/978-3-642-22792-9_15
[37] Lindell, Y.; Pinkas, B.; Naor, M., An efficient protocol for secure two-party computation in the presence of malicious adversaries, Advances in Cryptology - EUROCRYPT 2007, 52-78 (2007), Heidelberg: Springer, Heidelberg · Zbl 1141.94362 · doi:10.1007/978-3-540-72540-4_4
[38] Lindell, Y.; Pinkas, B., Secure two-party computation via cut-and-choose oblivious transfer, J. Cryptol., 25, 4, 680-722 (2012) · Zbl 1278.94056 · doi:10.1007/s00145-011-9107-0
[39] Lindell, Y.; Pinkas, B.; Smart, NP; Yanai, A.; Gennaro, R.; Robshaw, M., Efficient constant round multi-party computation combining BMR and SPDZ, Advances in Cryptology - CRYPTO 2015, 319-338 (2015), Heidelberg: Springer, Heidelberg · Zbl 1352.94049 · doi:10.1007/978-3-662-48000-7_16
[40] Lindell, Y., Riva, B.: Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: CCS, pp. 579-590 (2015)
[41] Nielsen, JB; Nordholt, PS; Orlandi, C.; Burra, SS; Safavi-Naini, R.; Canetti, R., A new approach to practical active-secure two-party computation, Advances in Cryptology - CRYPTO 2012, 681-700 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94134 · doi:10.1007/978-3-642-32009-5_40
[42] Nielsen, JB; Orlandi, C.; Reingold, O., LEGO for two-party secure computation, Theory of Cryptography, 368-386 (2009), Heidelberg: Springer, Heidelberg · Zbl 1213.94124 · doi:10.1007/978-3-642-00457-5_22
[43] Rindal, P., Rosulek, M.: Faster malicious 2-party secure computation with online/offline dual execution. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, 10-12 August 2016, pp. 297-314 (2016)
[44] Schoenmakers, B.; Tuyls, P.; Lee, PJ, Practical two-party computation based on the conditional gate, Advances in Cryptology - ASIACRYPT 2004, 119-136 (2004), Heidelberg: Springer, Heidelberg · Zbl 1094.94522 · doi:10.1007/978-3-540-30539-2_10
[45] Shamir, A., How to share a secret, Commun. ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021 · doi:10.1145/359168.359176
[46] Shelat, A., Shen, C.: Fast two-party secure computation with minimal assumptions. In: CCS, pp. 523-534 (2013)
[47] Wang, X.; Malozemoff, AJ; Katz, J.; Coron, J-S; Nielsen, JB, Faster secure two-party computation in the single-execution setting, Advances in Cryptology - EUROCRYPT 2017, 399-424 (2017), Cham: Springer, Cham · Zbl 1415.94465 · doi:10.1007/978-3-319-56617-7_14
[48] Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: CCS, pp. 21-37 (2017)
[49] Wang, X., Ranellucci, S., Katz, J.: Global-scale secure multiparty computation. In: CCS, pp. 39-56 (2017)
[50] Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162-167 (1986)
[51] Zahur, S.; Rosulek, M.; Evans, D.; Oswald, E.; Fischlin, M., Two halves make a whole - reducing data transfer in garbled circuits using half gates, Advances in Cryptology - 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.