nach oben

Journal of Cryptology

Erschienen in:

25.04.2016

Reconciling Non-malleability with Homomorphic Encryption

verfasst von: Manoj Prabhakaran, Mike Rosulek

Erschienen in: Journal of Cryptology | Ausgabe 3/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Homomorphic encryption schemes are useful in designing conceptually simple protocols that operate on encrypted inputs. On the other hand, non-malleable encryption schemes are vital for designing protocols with robust security against malicious parties, in a composable setting. In this paper, we address the problem of constructing public-key encryption schemes that meaningfully combine these two opposing demands. The intuitive tradeoff we desire in an encryption scheme is that anyone should be able to change encryptions of unknown messages \(m_1, \ldots , m_k\) into a (fresh) encryption of \(T(m_1, \ldots , m_k)\) for a specific set of allowed functions T, but the scheme should be otherwise “non-malleable.” That is, no adversary should be able to construct a ciphertext whose value is related to that of other ciphertexts in any other way. For the case where the allowed functions T are all unary, we formulate precise definitions that capture our intuitive requirements and show relationships among these new definitions and other more standard ones (IND-CCA, gCCA, and RCCA). We further justify these new definitions by showing their equivalence to a natural formulation of security in the framework of Universally Composable security. Next, we describe a new family of encryption schemes that satisfy our definitions for a wide variety of allowed transformations T and prove their security under the Decisional Diffie-Hellman (DDH) assumption in two groups with related sizes. Finally, we demonstrate how encryption schemes that satisfy our definitions can be used to implement conceptually simple protocols for non-trivial computation on encrypted data, which are secure against malicious adversaries in the UC framework without resorting to general-purpose multi-party computation or zero-knowledge proofs. For the case where the allowed functions T are binary, we show that a natural generalization of our definitions is unattainable if some T is a group operation. On the positive side, we show that if one of our security requirements is relaxed in a natural way, we can in fact obtain a scheme that is homomorphic with respect to (binary) group operations, and non-malleable otherwise.

Nächster Artikel Locally Computable UOWHF with Linear Shrinkage

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

Nur mit Berechtigung zugänglich

Homomorphic encryption allows (as a feature) anyone to change encryptions of unknown messages \(m_1, \ldots , m_k\) into an encryption of \(T(m_1, \ldots , m_k)\), for some allowed set of functions T.

Technically, they achieve a very similar (arguably simpler) notion of security to HCCA.

Clearly, one could settle for a slightly imperfect correctness condition; but our constructions do not require this. Requiring \({{\textsf {CTrans}}}\) to function without the public key would also be a meaningful relaxation, suitable in some applications. See Sect. 9.

If the HCCA experiment provided an unguarded oracle for \({{\textsf {RigExtract}}}\), then our main construction would demonstrably fail to achieve HCCA security. An unguarded \({{\textsf {RigExtract}}}\) would allow the adversary to carefully craft an S-value that would allow her to win the game. The ability to send S values of one’s choosing is never needed in our future proofs, and guarding the \({{\textsf {RigEnc}}}\) and \({{\textsf {RigExtract}}}\) oracles has the effect of disallowing it.

The adversary knows \(\{ \zeta ' \mid \exists S: (\zeta ',S) \in {{\mathcal {R}}} \}\), so without loss of generality we can assume the query includes such a “valid” \(\zeta '\).

In Appendix we do consider weaker variants of unlinkability which are (equivalent to) simple correctness properties, and do not involve maliciously chosen ciphertexts.

For example, start with \({\mathcal {T}} = {\mathcal {T}} '\) and a scheme that is HCCA-secure and unlinkable with respect to \({\mathcal {T}} \). Then choose a random x and include \(y=f(x)\) in the public key, where f is a one-way function. Modify a single \(T \in {\mathcal {T}} '\) to map all preimages of y to themselves. Now the original T need not be present in the new \({\mathcal {T}} '\) (so \({\mathcal {T}} \not \subseteq {\mathcal {T}} '\)) and yet an adversary in the HCCA is unlikely to ever provide a preimage of y as the challenge plaintext, so \({\mathcal {T}} '\)-HCCA security of the scheme reduces to its \({\mathcal {T}} \)-HCCA security.

In the non-broadcasting setting, we require an additional security/correctness property, namely that \({{\textsf {CTrans}}} _{pk} (\zeta , T_2 \circ T_1)\) and \({{\textsf {CTrans}}} _{pk} ({{\textsf {CTrans}}} _{pk} (\zeta , T_1), T_2)\) are indistinguishable, for all (possibly adversarially generated) ciphertexts \(\zeta \). Our main construction indeed satisfies this property; the two distributions are identical.

The argument for RCCA security applies only when the size of the plaintext domain is superpolynomial in the security parameter. However, this is the only setting in which RCCA is generally useful.

If an adversary can successfully distinguish between encryptions of \({\textsf {msg}} \) versus \({\textsf {msg}} '\) in the original experiment, then a related adversary can successfully distinguish between either \(({\textsf {msg}},{\textsf {msg}} _0)\) or \(({\textsf {msg}} ',{\textsf {msg}} _0)\).

Strong (one-time) signature schemes are implied by one-way functions, and it is easy to construct a one-way function from the \({{\textsf {KeyGen}}}\) procedure of any HCCA-secure scheme.

A shielding construction is one in which the HCCA scheme’s decryption algorithm does not make calls to the CPA scheme’s encryption algorithm.

Besides these two linearly independent vectors \(\vec {z}\) and (1, 1, 1, 1), we require two additional independent dimensions in the security proof. Thus, a 4-dimensional space is needed.

Using the same technique as in the Cramer–Shoup scheme [23], our use of a hash can be removed, but at the expense of longer public keys.

Any vector which is not a scalar multiple of the all-ones vector will suffice.

The probability is over the residual degrees of freedom in the private key that remain after fixing the public key.

In these equations and all that follow, “\(\log \)” denotes the discrete logarithm with respect to any fixed generator of the appropriate cyclic group (\({\mathbb {G}}\) or \(\widehat{{\mathbb {G}}}\)).

Choosing a different value of \(u \) induces different strands \({\vec {x}}\) and \({\vec {y}}\), but the strands change only by scalar multiplication. In particular, linear independence is not affected by the choice of \(u \).

To see the reduction, consider the following simulator which is given a random pair \(g, g^S\) as input. We perform 4 randomized reductions to obtain \(g_{j}, g_{j} ^S\) pairs, and generate the keys of our scheme honestly using these \(g_{j} \) values; then we simulate the Hybrid 1 experiment against the adversary. We can compute a public-key component \(E \) as well as the value \(E ^{S}\) needed to generate \(\zeta '\). For the response to a \({{\textsc {rigenc}}}\) query, use this value when generating the output of \({{\textsf {RigEnc}}}\). The distribution of this ciphertext is correct, as S is random. When the adversary gives the challenge plaintext, compute \(\mu ' = {\textsf {H}} ({{\textsf {canonize}}} (m^*_1, \ldots , m^*_n))\). If \(g^{\mu '} = g^{S}\), then our simulator has successfully computed the discrete logarithm.

Actually, our protocol construction requires that the encryption scheme be only transformation-hiding (Appendix) and does not require the full power of unlinkability. Thus the protocol can be securely instantiated with even simpler encryption schemes.

For example, one may choose \({\mathbb {H}} _1 = {\mathbb {G}} \) and \({\mathbb {H}} _2=\{1\}\), leading to a useful instantiation of our scheme.

J. H. Ahn, D. Boneh, J. Camenisch, S. Hohenberger, abhi shelat, and B. Waters. Computing on authenticated data. In R. Cramer, editor, TCC, volume 7194 of Lecture Notes in Computer Science, pp. 1–20. Springer, 2012.

J. H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption. In Knudsen [46], pp. 83–107.

J. K. Andersen and E. W. Weisstein. Cunningham chain. From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/CunninghamChain.html, 2005.

M. Bellare, A. Boldyreva, A. Desai, and D. Pointcheval. Key-privacy in public-key encryption. In C. Boyd, editor, ASIACRYPT, volume 2248 of Lecture Notes in Computer Science, pp. 566–582. Springer, 2001.

M. Bellare and A. Sahai. Non-malleable encryption: Equivalence between two notions, and an indistinguishability-based characterization. In M. J. Wiener, editor, CRYPTO, volume 1666 of Lecture Notes in Computer Science, pp. 519–536. Springer, 1999.

J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Department of Computer Science, Yale University, 1987.

M. Blaze, G. Bleumer, and M. Strauss. Divertible protocols and atomic proxy cryptography. In K. Nyberg, editor, EUROCRYPT, volume 1403 of Lecture Notes in Computer Science, pp. 127–144. Springer, 1998.

D. Boneh. The decision Diffie-Hellman problem. In J. Buhler, editor, ANTS, volume 1423 of Lecture Notes in Computer Science, pp. 48–63. Springer, 1998.

D. Boneh, editor. Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science. Springer, 2003.

10.

D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF formulas on ciphertexts. In Kilian [44], pp. 325–341.

11.

D. Boneh, G. Segev, and B. Waters. Targeted malleability: homomorphic encryption for restricted computations. In S. Goldwasser, editor, ITCS, pp. 350–366. ACM, 2012.

12.

D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In Vadhan [65], pp. 535–554.

13.

A. Broadbent and A. Tapp. Information-theoretic security without an honest majority. In Kurosawa [48], pp. 410–426.

14.

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2005.

15.

R. Canetti, S. Halevi, and J. Katz. Chosen-ciphertext security from identity-based encryption. In C. Cachin and J. Camenisch, editors, EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pp. 207–222. Springer, 2004.

16.

R. Canetti and J. Herzog. Universally composable symbolic analysis of mutual authentication and key-exchange protocols. In Halevi and Rabin [39], pp. 380–403.

17.

R. Canetti and S. Hohenberger. Chosen-ciphertext secure proxy re-encryption. In P. Ning, S. D. C. di Vimercati, and P. F. Syverson, editors, ACM Conference on Computer and Communications Security, pp. 185–194. ACM, 2007.

18.

R. Canetti, H. Krawczyk, and J. B. Nielsen. Relaxing chosen-ciphertext security. In Boneh [9], pp. 565–582.

19.

M. Chase, M. Kohlweiss, A. Lysyanskaya, and S. Meiklejohn. Malleable proof systems and applications. In D. Pointcheval and T. Johansson, editors, EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pp. 281–300. Springer, 2012.

20.

D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM, 24(2):84–88, 1981.CrossRef

21.

B. Chor, N. Gilboa, and M. Naor. Private information retrieval by keywords. TR CS0917, Department of Computer Science, Technion, 1997.

22.

R. Cramer, M. K. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In U. M. Maurer, editor, EUROCRYPT, volume 1070 of Lecture Notes in Computer Science, pp. 72–83. Springer, 1996.

23.

R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, CRYPTO, volume 1462 of Lecture Notes in Computer Science, pp. 13–25. Springer, 1998.

24.

R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Knudsen [46], pp. 45–64.

25.

I. Damgård, N. Fazio, and A. Nicolosi. Non-interactive zero-knowledge from homomorphic encryption. In Halevi and Rabin [39], pp. 41–59.

26.

I. Damgård and J. B. Nielsen. Universally composable efficient multiparty computation from threshold homomorphic encryption. In Boneh [9], pp. 247–264.

27.

G. Danezis. Breaking four mix-related schemes based on universal re-encryption. Int. J. Inf. Sec., 6(6):393–402, 2007.CrossRefMATH

28.

D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography (extended abstract). In C. Koutsougeras and J. S. Vitter, editors, STOC, pp. 542–552. ACM, 1991.

29.

T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and D. Chaum, editors, CRYPTO, volume 196 of Lecture Notes in Computer Science, pp. 10–18. Springer, 1984.

30.

Free Haven Project. Anonymity bibliography. http://freehaven.net/anonbib/, 2006.

31.

C. Gentry. Fully homomorphic encryption using ideal lattices. In M. Mitzenmacher, editor, STOC, pp. 169–178. ACM, 2009.

32.

Y. Gertner, T. Malkin, and S. Myers. Towards a separation of semantic and CCA security for public key encryption. In Vadhan [65], pp. 434–455.

33.

S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270–299, Apr. 1984. Preliminary version appeared in STOC’ 82.

34.

P. Golle, M. Jakobsson, A. Juels, and P. F. Syverson. Universal re-encryption for mixnets. In T. Okamoto, editor, CT-RSA, volume 2964 of Lecture Notes in Computer Science, pp. 163–178. Springer, 2004.

35.

J. Groth. A verifiable secret shuffle of homomorphic encryptions. In Y. Desmedt, editor, Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, pp. 145–160. Springer, 2003.

36.

J. Groth. Rerandomizable and replayable adaptive chosen ciphertext attack secure cryptosystems. In Naor [50], pp. 152–170.

37.

J. Groth and S. Lu. A non-interactive shuffle with pairing based verifiability. In Kurosawa [48], pp. 51–67.

38.

J. Groth and S. Lu. Verifiable shuffle of large size ciphertexts. In T. Okamoto and X. Wang, editors, Public Key Cryptography, volume 4450 of Lecture Notes in Computer Science, pp. 377–392. Springer, 2007.

39.

S. Halevi and T. Rabin, editors. Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science. Springer, 2006.

40.

M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In B. Preneel, editor, EUROCRYPT, volume 1807 of Lecture Notes in Computer Science, pp. 539–556. Springer, 2000.

41.

Y. Ishai, E. Kushilevitz, and R. Ostrovsky. Sufficient conditions for collision-resistant hashing. In Kilian [44], pp. 445–456.

42.

M. J. Jurik. Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols. PhD thesis, BRICS, 2003.

43.

A. Kiayias and M. Yung. Non-interactive zero-sharing with applications to private distributed decision making. In R. N. Wright, editor, Financial Cryptography, volume 2742 of Lecture Notes in Computer Science, pp. 303–320. Springer, 2003.

44.

J. Kilian, editor. Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science. Springer, 2005.

45.

M. Klonowski, M. Kutylowski, A. Lauks, and F. Zagórski. Universal re-encryption of signatures and controlling anonymous information flow. In WARTACRYPT ’04 Conference on Cryptology. Bedlewo/Poznan, 2006.

46.

L. R. Knudsen, editor. Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of Lecture Notes in Computer Science. Springer, 2002.

47.

T. Koshy. Elementary Number Theory with Applications. Academic Press, 2001.

48.

K. Kurosawa, editor. Advances in Cryptology - ASIACRYPT 2007, 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007, Proceedings, volume 4833 of Lecture Notes in Computer Science. Springer, 2007.

49.

P. D. MacKenzie, M. K. Reiter, and K. Yang. Alternatives to non-malleability: Definitions, constructions, and applications (extended abstract). In Naor [50], pp. 171–190.

50.

M. Naor, editor. Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951 of Lecture Notes in Computer Science. Springer, 2004.

51.

M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In H. Ortiz, editor, STOC, pp. 427–437. ACM, 1990.

52.

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In J. Stern, editor, EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pp. 223–238. Springer, 1999.

53.

A. Patil. On symbolic analysis of cryptographic protocols. Master’s thesis, Massachusetts Institute of Technology, 2005.

54.

M. Prabhakaran and M. Rosulek. Rerandomizable RCCA encryption. In A. Menezes, editor, CRYPTO, volume 4622 of Lecture Notes in Computer Science, pp. 517–584. Springer, 2007. Full version available from http://eprint.iacr.org/2007/119.

55.

M. Prabhakaran and M. Rosulek. Cryptographic complexity of multi-party computation problems: Classifications and separations. In D. Wagner, editor, CRYPTO, volume 5157 of Lecture Notes in Computer Science, pp. 262–279. Springer, 2008.

56.

M. Prabhakaran and M. Rosulek. Homomorphic encryption with CCA security. In L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, ICALP (2), volume 5126 of Lecture Notes in Computer Science, pp. 667–678. Springer, 2008. Full version available from http://eprint.iacr.org/2008/079.

57.

M. Prabhakaran and M. Rosulek. Towards robust computation on encrypted data. In J. Pieprzyk, editor, ASIACRYPT, volume 5350 of Lecture Notes in Computer Science, pp. 216–233. Springer, 2008.

58.

C. Rackoff and D. R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pp. 433–444. Springer, 1991.

59.

M. Rosulek. The Structure of Secure Multi-Party Computation. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 2009.

60.

A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In P. Beame, editor, FOCS, pp. 543–553, 1999.

61.

K. Sako and J. Kilian. Secure voting using partially compatible homomorphisms. In Y. Desmedt, editor, CRYPTO, volume 839 of Lecture Notes in Computer Science, pp. 411–424. Springer, 1994.

62.

T. Sander, A. Young, and M. Yung. Non-interactive cryptocomputing for NC\(^{1}\). In P. Beame, editor, FOCS, pp. 554–567, 1999.

63.

V. Shoup. A proposal for an ISO standard for public key encryption. Cryptology ePrint Archive, Report 2001/112, 2001. http://eprint.iacr.org/.

64.

D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In IEEE Symposium on Security and Privacy, pp. 44–55, 2000.

65.

S. P. Vadhan, editor. Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings, volume 4392 of Lecture Notes in Computer Science. Springer, 2007.

66.

D. Wikström. A note on the malleability of the El Gamal cryptosystem. In A. Menezes and P. Sarkar, editors, INDOCRYPT, volume 2551 of Lecture Notes in Computer Science, pp. 176–184. Springer, 2002.

Titel: Reconciling Non-malleability with Homomorphic Encryption
verfasst von: Manoj Prabhakaran
Mike Rosulek
Publikationsdatum: 25.04.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9231-y

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"

Weitere Artikel der Ausgabe 3/2017

Integral Cryptanalysis on Full MISTY1

Differential-Linear Cryptanalysis Revisited

Lattices with Symmetry

Short Signatures from Diffie–Hellman: Realizing Almost Compact Public Key

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

Locally Computable UOWHF with Linear Shrinkage