nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Mon\(\mathbb {Z}_{2^{k}}\)a: Fast Maliciously Secure Two Party Computation on \(\mathbb {Z}_{2^{k}}\)

verfasst von : Dario Catalano, Mario Di Raimondo, Dario Fiore, Irene Giacomelli

Erschienen in: Public-Key Cryptography – PKC 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we present a new 2-party protocol for secure computation over rings of the form \(\mathbb {Z}_{2^k}\). As many recent efficient MPC protocols supporting dishonest majority, our protocol consists of a heavier (input-independent) pre-processing phase and a very efficient online stage. Our offline phase is similar to BeDOZa (Bendlin et al. Eurocrypt 2011) but employs Joye-Libert (JL, Eurocrypt 2013) as underlying homomorphic cryptosystem and, notably, it can be proven secure without resorting to the expensive sacrifice step. JL turns out to be particularly well suited for the ring setting as it naturally supports \(\mathbb {Z}_{2^k}\) as underlying message space. Moreover, it enjoys several additional properties (such as valid ciphertext-verifiability and efficiency) that make it a very good fit for MPC in general. As a main technical contribution we show how to take advantage of all these properties (and of more properties that we introduce in this work, such as a ZK proof of correct multiplication) in order to design a two-party protocol that is efficient, fast and easy to implement in practice.

Our solution is particularly well suited for relatively large choices of k (e.g. \(k=128\)), but compares favorably with the state of the art solution of SPD\(\mathbb {Z}_{2^k}\) (Cramer et al. Crypto 2018) already for the practically very relevant case of \(\mathbb {Z}_{2^{64}}\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Going Beyond Dual Execution: MPC for Functions with Efficient Verification

Nächstes Kapitel Generic Authenticated Key Exchange in the Quantum Random Oracle Model

The name MonZa is inspired by the famous race track hosting the Formula One Italian Grand Prix.

We only focuses on the preprocessing stage since the online one is identical to [9].

Also, coming up with an efficient, constant-round, protocol for a threshold JL decryption seems far from trivial due to the bit-by-bit extraction technique in the algorithm.

We remark that the original scheme from [17] allows more flexibility in the choice of p and q. For the sake of this discussion the choices above are good enough.

For a CPA-secure additive encryption scheme this property always holds: include \(C={\mathsf {Enc}}_\mathsf{pk}(b)\) in the public key with \(b=0\) for \(\mathsf {Gen}\) and \(b=1\) for \(\widetilde{\mathsf {Gen}}\), and redefine encryption as \({\mathsf {Enc}}_\mathsf{pk}(m)=C^{\odot m}\odot {\mathsf {Enc}}_\mathsf{pk}(0)\).

The last (most significant) k bits of the MAC key are not actually required to be random, since the security of the MPC protocol follows from \(\alpha \mod 2^s\) being random. However, sampling \(\alpha \) from \(\mathbb {Z}_{2^{k+s}}\) simplifies the description of the protocols.

The \([\cdot ]\)-representation for a value x of \(k+s\) bits means that we additively share in \(\mathbb {Z}_{2^{k+s}}\) the value x and its MAC \(x\cdot \alpha \bmod 2^{k+s}\). However, only the first k bits of x are authenticated.

In order to use the same ZK-proof for both players we need to assume that the commitment scheme has the same homomorphic property as the encryption scheme. If the commitment scheme is instantiated using the encryption as observed in Sect. 2.3, the homomorphic property clearly holds.

It is not strictly necessary that \(p'\) and \(q'\) are both primes: nevertheless for security each of them should contain a big enough prime factor.

When \(\varPi _{\scriptstyle \mathsf {ZKPoMCV}}\) is used in the offline phase of Mon\(\mathbb {Z}_{2^k}\)a, we have \(\mathsf{pk}=\mathsf{pk}_1\) if the \(P_1\) is the prover or \(\mathsf{pk}=\mathsf{pk}_2\) if \(P_2\) is the prover (\(\mathsf{pk}_1,\mathsf{pk}_2\) are the keys used in \(\varPi _{\scriptstyle \mathsf {ZKPoCM}}\)).

More precisely, in order for the above idea to be any useful in our protocols, we also need to extract the randomness associated to the encryption/commitment. Luckily, this happens to be the case when using JL as underlying building block.

Similarly to the analysis in [9], we ignore the negligible costs of \(\mathcal {F}_{\scriptstyle \mathsf {Rand}}\) and of the check of the openings in Triple as it can be performed in a batch when producing many triples at once.

https://keylength.com.

For sake of completeness, in the border case with \(S=80\), \(s=40\) and \(k=128\), we considered a slightly larger modulus \(|N|=1160\) in order to satisfy the security constraint \(k+2s < \frac{1}{4}\log _2(N)-S\) on JL scheme from [5].

The source code of our project is publicly available at: https://github.com/crypto-unict/monza-mpc.

https://gmplib.org.

We considered the actual ping delay between Amazon and Google data-centers.

JL decryption can be surprisingly fast for small messages; as reference a Paillier decryption, with identical parameters/machine/setting used in Table 3, has a cost that range from 7864 \(\upmu \)s to 4323 \(\upmu \)s (if CRT is exploited). JL requires only 4054 \(\upmu \)s.

Araki, T., et al.: Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier. In: 2017 IEEE Symposium on Security and Privacy, pp. 843–862. IEEE Computer Society Press, May 2017

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.), ACM CCS 2016, pp. 805–817. ACM Press, October 2016

Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: 45th FOCS, pp. 186–195. IEEE Computer Society Press, October 2004

Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_11CrossRef

Benhamouda, F., Herranz, J., Joye, M., Libert, B.: Efficient cryptosystems from \(2^k\)-th power residue symbols. J. Cryptol. 30(2), 519–549 (2017). https://doi.org/10.1007/s00145-016-9229-5MathSciNetCrossRefMATH

Bogdanov, D., Laur, S., Willemson, J.: Sharemind: a framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88313-5_13CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001

Catalano, D., Fiore, D.: Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 1518–1529. ACM Press, October 2015

Cramer, R., Damgård, I., Escudero, D., Scholl, P., Xing, C.: SPD\(\mathbb{Z}_{2^k}\): efficient MPC mod \(2^k\) for dishonest majority. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 769–798. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-96881-0_26CrossRef

10.

Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 596–613. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_37CrossRef

11.

Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1–18. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40203-6_1CrossRef

12.

Damgård, I., Orlandi, C., Simkin, M.: Yet another compiler for active security or: efficient MPC over arbitrary rings. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 799–829. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_27CrossRef

13.

Damgård, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38CrossRef

14.

Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part II. LNCS, vol. 10211, pp. 225–255. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_8CrossRef

15.

Gilboa, N.: Two party RSA key generation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_8CrossRef

16.

Goldwasser, S., Micali, S.: Probabilistic encryption and how to play mental poker keeping secret all partial information. In: 14th ACM STOC, pp. 365–377. ACM Press, May 1982

17.

Joye, M., Libert, B.: Efficient cryptosystems from 2^k-th power residue symbols. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 76–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_5CrossRef

18.

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 830–842. ACM Press, October 2016

19.

Keller, M., Pastro, V., Rotaru, D.: Overdrive: making SPDZ great again. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 158–189. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_6CrossRef

20.

Orsini, E., Smart, N.P., Vercauteren, F.: Overdrive2k: efficient secure MPC over \(z_{2^k}\) from somewhat homomorphic encryption. Cryptology ePrint Archive, Report 2019/153 (2019)

Titel: Mona: Fast Maliciously Secure Two Party Computation on
verfasst von: Dario Catalano
Mario Di Raimondo
Dario Fiore
Irene Giacomelli
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"