×

On CCA-secure somewhat homomorphic encryption. (English) Zbl 1292.94106

Miri, Ali (ed.) et al., Selected areas in cryptography. 18th international workshop, SAC 2011, Toronto, ON, Canada, August 11–12, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28495-3/pbk). Lecture Notes in Computer Science 7118, 55-72 (2012).
Summary: It is well known that any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks. The question then arises as to what is the most stringent security definition which is achievable by homomorphic encryption schemes. Prior work has shown that various schemes which support a single homomorphic encryption scheme can be shown to be IND-CCA1, i.e. secure against lunchtime attacks. In this paper we extend this analysis to the recent fully homomorphic encryption scheme proposed by Gentry, as refined by Gentry, Halevi, Smart and Vercauteren. We show that the basic Gentry scheme is not IND-CCA1; indeed a trivial lunchtime attack allows one to recover the secret key. We then show that a minor modification to the variant of the somewhat homomorphic encryption scheme of Smart and Vercauteren will allow one to achieve IND-CCA1, indeed PA-1, in the standard model assuming a lattice based knowledge assumption. We also examine the security of the scheme against another security notion, namely security in the presence of ciphertext validity checking oracles; and show why CCA-like notions are important in applications in which multiple parties submit encrypted data to the “cloud” for secure processing.
For the entire collection see [Zbl 1234.94005].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Riyami, S.S., Paterson, K.G.: Certificateless Public Key Cryptography. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 452–473. Springer, Heidelberg (2003) · Zbl 1205.94072 · doi:10.1007/978-3-540-40061-5_29
[2] Armknecht, F., Peter, A., Katzenbeisser, S.: A cleaner view on IND-CCA1 secure homomorphic encryption using SOAP. IACR e-print 2010/501 (2010), http://eprint.iacr.org/2010/501
[3] Baek, J., Steinfeld, R., Zheng, Y.: Formal proofs for the security of signcryption. Journal of Cryptology 20(2), 203–235 (2007) · Zbl 1113.68045 · doi:10.1007/s00145-007-0211-0
[4] 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) · Zbl 1094.94506 · doi:10.1007/978-3-540-30539-2_4
[5] Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995) · Zbl 0881.94010 · doi:10.1007/BFb0053428
[6] 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) · Zbl 1281.94015 · doi:10.1007/978-3-642-20465-4_11
[7] Bernhard, D., Cortier, V., Pereira, O., Smyth, B., Warinschi, B.: Adapting Helios for Provable Ballot Privacy. In: Atluri, V., Diaz, C. (eds.) ESORICS 2011. LNCS, vol. 6879, pp. 335–354. Springer, Heidelberg (2011) · Zbl 05975864 · doi:10.1007/978-3-642-23822-2_19
[8] 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) · Zbl 0931.94017 · doi:10.1007/BFb0055716
[9] Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally Efficient Multi-Authority Election Scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997) · doi:10.1007/3-540-69053-0_9
[10] 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) · Zbl 0931.94018 · doi:10.1007/BFb0055717
[11] Damgård, I.B.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992) · Zbl 0764.94015 · doi:10.1007/3-540-46766-1_36
[12] Damgård, I., Groth, J., Salomonsen, G.: The theory and implementation of an electronic voting system. In: Secure Electronic Voting, pp. 77–99. Kluwer Academic Publishers (2002)
[13] Dent, A.: A Designer’s Guide to KEMs. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 133–151. Springer, Heidelberg (2003) · Zbl 1123.94336 · doi:10.1007/978-3-540-40974-8_12
[14] van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption Over the Integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010) · Zbl 1279.94130 · doi:10.1007/978-3-642-13190-5_2
[15] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Symposium on Theory of Computing – STOC 2009, pp. 169–178. ACM (2009) · Zbl 1304.94059 · doi:10.1145/1536414.1536440
[16] Gentry, C.: A fully homomorphic encryption scheme. PhD, Stanford University (2009) · Zbl 1304.94059
[17] Gentry, C., Halevi, S.: Implementing Gentry’s Fully-Homomorphic Encryption Scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129–148. Springer, Heidelberg (2011) · Zbl 1281.94026 · doi:10.1007/978-3-642-20465-4_9
[18] Hu, Z.-Y., Sun, F.-C., Jiang, J.-C.: Ciphertext verification security of symmetric encryption schemes. Science in China Series F 52(9), 1617–1631 (2009) · Zbl 1181.94097 · doi:10.1007/s11432-009-0158-x
[19] Joye, M., Quisquater, J., Yung, M.: On the Power of Misbehaving Adversaries and Security Analysis of the Original EPOC. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 208–222. Springer, Heidelberg (2001) · Zbl 0988.94513 · doi:10.1007/3-540-45353-9_16
[20] Lipmaa, H.: On the CCA1-security of ElGamal and Damgård’s ElGamal. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010. LNCS, vol. 6584, pp. 18–35. Springer, Heidelberg (2011) · Zbl 1295.94105 · doi:10.1007/978-3-642-21518-6_2
[21] Manger, J.: A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 230–238. Springer, Heidelberg (2001) · Zbl 1015.94542 · doi:10.1007/3-540-44647-8_14
[22] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Symposium on Theory of Computing – STOC 1990, pp. 427–437. ACM (1990) · doi:10.1145/100216.100273
[23] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Symposium on Theory of Computing – STOC 2005, pp. 84–93. ACM (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[24] Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–177 (1978)
[25] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. Journal ACM 56(6), 1–40 (2009) · Zbl 1325.68101 · doi:10.1145/1568318.1568324
[26] Smart, N.P.: Errors Matter: Breaking RSA-Based PIN Encryption with Thirty Ciphertext Validity Queries. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 15–25. Springer, Heidelberg (2010) · Zbl 1272.94062 · doi:10.1007/978-3-642-11925-5_2
[27] Smart, N.P., Vercauteren, F.: Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010) · Zbl 1281.94055 · doi:10.1007/978-3-642-13013-7_25
[28] Smyth, B., Cortier, V.: Attacking and fixing Helios: An analysis of ballot secrecy. In: IEEE Computer Security Foundations Symposium – CSF 2011 (to appear, 2011)
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.