nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability

verfasst von : Mark Manulis, Jérôme Nguyen

Erschienen in: Advances in Cryptology – EUROCRYPT 2024

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond \(\textrm{CCA1}\). Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (\(\textrm{vCCA}\)). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be “linked” to the original input ciphertexts. We formalize the \(\textrm{vCCA}\) notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al. in 2012.

We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic encryption schemes, namely \(\textrm{CCA1}\), \(\textrm{RCCA}\), \(\textrm{FuncCPA}\), \(\textrm{CCVA}\), and \(\textrm{HCCA}\). We prove that \(\textrm{vCCA}\) security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, \(\textrm{vCCA}\) is strictly stronger than \(\textrm{CCA1}\).

Finally, we provide a general transformation, that takes any \(\textrm{CPA}\)-secure FHE scheme and makes it \(\textrm{vCCA}\)-secure. Our transformation first turns an FHE scheme into a \(\textrm{CCA2}\)-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge (SNARK) to verifiably control the evaluation algorithm. In fact, we obtain four general variations of this transformation. We handle both the asymmetric and the symmetric key FHE schemes, and for each we give two variations differing in whether the ciphertext integrity can be verified publicly or requires the secret key. We use well-known techniques to achieve \(\textrm{CCA2}\) security in the first step of our transformation. In the asymmetric case, we use the double encryption paradigm, and in the symmetric case, we use Encrypt-then-MAC techniques. Furthermore, our transformation also gives the first \(\textrm{CCA1}\)-secure FHE scheme based on bootstrapping techniques.

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 Anamorphic Encryption: New Constructions and Homomorphic Realizations

Nächstes Kapitel Bootstrapping Bits with CKKS

Akavia, A., Gentry, C., Halevi, S., Vald, M.: Achievable CCA2 relaxation for homomorphic encryption. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC, pp. 70–99. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22365-5_3

Akavia, A., Vald, M.: On the privacy of protocols based on CPA-secure homomorphic encryption. Cryptology ePrint Archive (2021)

An, J.H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_6CrossRef

Armknecht, F., Katzenbeisser, S., Peter, A.: Group homomorphic encryption: characterizations, impossibility results, and applications. Des. Codes Crypt. 67, 209–232 (2013)MathSciNetCrossRef

Atapoor, S., Baghery, K., Pereira, H.V., Spiessens, J.: Verifiable FHE via Lattice-based SNARKs. Cryptology ePrint Archive (2024)

Baghery, K., Kohlweiss, M., Siim, J., Volkhov, M.: Another look at extraction and randomization of Groth’s zk-SNARK. In: Borisov, N., Diaz, C. (eds.) FC 2021. LNCS, vol. 12674, pp. 457–475. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-662-64322-8_22CrossRef

Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055718CrossRef

Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. J. Cryptology 21(4), 469–491 (2008). https://doi.org/10.1007/s00145-008-9026-xMathSciNetCrossRef

Bellare, M., Palacio, A.: Towards plaintext-aware public-key encryption without random oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 48–62. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30539-2_4CrossRef

10.

Biasse, J.F., Fieker, C.: Subexponential class group and unit group computation in large degree number fields. LMS J. Comput. Math. 17(A), 385–403 (2014)

11.

Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: SODA16, pp. 893–902. SIAM (2016)

12.

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: ITCS 2012, pp. 326–349 (2012)

13.

Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055716CrossRef

14.

Boneh, D., Segev, G., Waters, B.: Targeted malleability: homomorphic encryption for restricted computations. In: ITCS 2012, pp. 350–366 (2012)

15.

Boneh, D., Shen, E., Waters, B.: Strongly unforgeable signatures based on computational Diffie-Hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_15CrossRef

16.

Boneh, D., Shoup, V.: A graduate course in applied cryptography. Draft 0.6 (2023)

17.

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: ITCS 2012, pp. 309–325 (2012)

18.

Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. Cryptology ePrint Archive (2018)

19.

Canetti, R., Krawczyk, H., Nielsen, J.B.: Relaxing chosen-ciphertext security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 565–582. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_33CrossRef

20.

Canetti, R., Raghuraman, S., Richelson, S., Vaikuntanathan, V.: Chosen-ciphertext secure fully homomorphic encryption. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10175, pp. 213–240. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_8CrossRef

21.

de Castro, L., Peikert, C.: Functional Commitments for All Functions, with Transparent Setup and from SIS. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, pp. 287–320. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30620-4_10

22.

Checri, M., Sirdey, R., Boudguiga, A., Bultel, J.P.: On the practical CPAD security of “exact” and threshold FHE schemes and libraries. Cryptology ePrint Archive, Paper 2024/116

23.

Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: ACM SIGSAC 2017, pp. 1243–1255 (2017)

24.

Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 409–437. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_15CrossRef

25.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption over the torus. J. Cryptol. 33(1), 34–91 (2020)MathSciNetCrossRef

26.

Chillotti, I., Gama, N., Goubin, L.: Attacking FHE-based applications by software fault injections. Cryptology ePrint Archive (2016)

27.

Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_20CrossRef

28.

Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055717CrossRef

29.

Das, A., Dutta, S., Adhikari, A.: Indistinguishability against chosen ciphertext verification attack revisited: the complete picture. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec 2013. LNCS, vol. 8209, pp. 104–120. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41227-1_6CrossRef

30.

Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: ACM STOC 1991, pp. 542–552 (1991)

31.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRef

32.

Fauzi, P., Hovd, M.N., Raddum, H.: On the IND-CCA1 security of FHE schemes. Cryptography 6(1), 13 (2022)CrossRef

33.

Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26, 80–101 (2013)MathSciNetCrossRef

34.

Ganesh, C., Kondi, Y., Orlandi, C., Pancholi, M., Takahashi, A., Tschudi, D.: Witness-succinct universally-composable SNARKs. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, pp. 315–346. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30617-4_11

35.

Ganesh, C., Nitulescu, A., Soria-Vazquez, E.: Rinocchio: SNARKs for ring arithmetic. J. Cryptol. 36(4), 41 (2023)MathSciNetCrossRef

36.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: ACM STOC 2009, pp. 169–178. STOC 2009. Association for Computing Machinery, New York (2009). https://doi.org/10.1145/1536414.1536440

37.

Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5CrossRef

38.

Geva, R., et al.: Collaborative privacy-preserving analysis of oncological data using multiparty homomorphic encryption. Proc. Natl. Acad. Sci. 120(33), e2304415120 (2023)CrossRef

39.

Groth, J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006). https://doi.org/10.1007/11935230_29CrossRef

40.

Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_11CrossRef

41.

Krohn, M.N.: On the Definitions of Cryptographic Security: Chosen Ciphertext Attack Revisited. Ph.D. thesis, Citeseer (1999)

42.

Li, B., Micciancio, D.: On the security of homomorphic encryption on approximate numbers. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 648–677. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_23CrossRef

43.

Loftus, J., May, A., Smart, N.P., Vercauteren, F.: On CCA-secure somewhat homomorphic encryption. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 55–72. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_4CrossRef

44.

Lu, W.J., Huang, Z., Hong, C., Ma, Y., Qu, H.: Pegasus: bridging polynomial and non-polynomial evaluations in homomorphic encryption. In: S &P 2021, pp. 1057–1073. IEEE (2021)

45.

Manulis, M., Nguyen, J.: Fully homomorphic encryption beyond IND-CCA1 security: Integrity through verifiability. Cryptology ePrint Archive, Paper 2024/202 (2024). https://eprint.iacr.org/2024/202

46.

Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016, pp. 735–763. Springer, Berlin Heidelberg, Berlin, Heidelberg (2016)CrossRef

47.

Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: ACM STOC 1990, pp. 427–437 (1990)

48.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

49.

Prabhakaran, M., Rosulek, M.: Homomorphic encryption with CCA security. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 667–678. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_54CrossRef

50.

Rackoff, C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_35CrossRef

51.

Rivest, R.L., Adleman, L., Dertouzos, M.L., et al.: On data banks and privacy homomorphisms. Found. Secure Comput. 4(11), 169–180 (1978)MathSciNet

52.

Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: FOCS 1999, pp. 543–553. IEEE (1999)

53.

Viand, A.: Useable Fully Homomorphic Encryption. Ph.D. thesis, ETH Zurich (2023)

54.

Viand, A., Knabenhans, C., Hithnawi, A.: Verifiable fully homomorphic encryption. arXiv preprint arXiv:2301.07041 (2023)

55.

Wang, B., Wang, X., Xue, R.: CCA1 secure FHE from PIO, revisited. Cybersecurity 1(1), 1–8 (2018)MathSciNetCrossRef

56.

Yasuda, S., Kitagawa, F., Tanaka, K.: Constructions for the IND-CCA1 secure fully homomorphic encryption. Mathematical Modelling for Next-Generation Cryptography: CREST Crypto-Math Project, pp. 331–347 (2018)

57.

Zhang, Z., Plantard, T., Susilo, W.: Reaction attack on outsourced computing with fully homomorphic encryption schemes. In: Kim, H. (eds.) ICISC 2011. pp. 419–436. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31912-9_28

Titel: Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability
verfasst von: Mark Manulis
Jérôme Nguyen
Verlag: Springer Nature Switzerland
Buch: Advances in Cryptology – EUROCRYPT 2024
Print ISBN: 978-3-031-58722-1

Electronic ISBN: 978-3-031-58723-8

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58723-8_3

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"

Premium Partner