nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Cryptanalysis of the Co-ACD Assumption

verfasst von : Pierre-Alain Fouque, Moon Sung Lee, Tancrède Lepoint, Mehdi Tibouchi

Erschienen in: Advances in Cryptology -- CRYPTO 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

At ACM-CCS 2014, Cheon, Lee and Seo introduced a new number-theoretic assumption, the Co-Approximate Common Divisor (Co-ACD) assumption, based on which they constructed several cryptographic primitives, including a particularly fast additively homomorphic encryption scheme. For their proposed parameters, they found that their scheme was the “most efficient of those that support an additive homomorphic property”. Unfortunately, it turns out that those parameters, originally aiming at 128-bit security, can be broken in a matter of seconds.

Indeed, this paper presents several lattice-based attacks against the Cheon–Lee–Seo (CLS) homomorphic encryption scheme and of the underlying Co-ACD assumption that are effectively devastating for the proposed constructions. A few known plaintexts are sufficient to decrypt any ciphertext in the symmetric-key CLS scheme, and small messages can even be decrypted without any known plaintext at all. This breaks the security of both the symmetric-key and the public-key variants of CLS encryption as well as the underlying decisional Co-ACD assumption. Moreover, Coppersmith techniques can be used to solve the search variant of the Co-ACD problem and mount a full key recovery on the CLS scheme.

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 Explicit Non-malleable Codes Against Bit-Wise Tampering and Permutations

Nächstes Kapitel Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP

[BCF+14]

Bi, J., Coron, J.-S., Faugère, J.-C., Nguyen, P.Q., Renault, G., Zeitoun, R.: Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 185–202. Springer, Heidelberg (2014) CrossRef

[Bro01]

Broughan, K.A.: The gcd-sum function. J. Integer Sequences 4, 01.2.2, 19 (2001)

[CCK+13]

Cheon, J.H., Coron, J.-S., Kim, J., Lee, M.S., Lepoint, T., Tibouchi, M., Yun, A.: Batch fully homomorphic encryption over the integers. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 315–335. Springer, Heidelberg (2013) CrossRef

[CH12]

Cohn, H., Heninger, N.: Approximate common divisors via lattices. In: ANTS X (2012)

[CLS14]

Cheon, J.H., Lee, H.T., Seo, J.H.: A new additive homomorphic encryption based on the Co-ACD problem. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS, pp. 287–298. ACM, New York (2014)

[CLT13]

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013) CrossRef

[CLT14]

Coron, J.-S., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 311–328. Springer, Heidelberg (2014) CrossRef

[CN11]

Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011) CrossRef

[CN12]

Chen, Y., Nguyen, P.Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 502–519. Springer, Heidelberg (2012) CrossRef

[CNT10]

Coron, J.-S., Naccache, D., Tibouchi, M.: Fault attacks against emv signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 208–220. Springer, Heidelberg (2010) CrossRef

[CNT12]

Coron, J.-S., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 446–464. Springer, Heidelberg (2012) CrossRef

[Cop97]

Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10(4), 233–260 (1997)MathSciNetCrossRefMATH

[DGHV10]

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) CrossRef

[FLLT14]

Fouque, P.-A., Lee, M.S., Lepoint, T., Tibouchi, M.: Cryptanalysis of the Co-ACD assumption. Cryptology ePrint Archive. Full version of this paper, Report 2014/1024 (2014). http://eprint.iacr.org/

[How01]

Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 51. Springer, Heidelberg (2001) CrossRef

[JL13]

Joye, M., Libert, B.: Efficient cryptosystems from 2\(^\text{ k }\)-th power residue symbols. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 76–92. Springer, Heidelberg (2013) CrossRef

[LLL82]

Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH

[LT15]

Lepoint, T., Tibouchi, M.: Cryptanalysis of a (somewhat) additively homomorphic encryption scheme used in PIR. In: WAHC (2015)

[May03]

May, A.: New RSA Vulnerabilities Using Lattice Reduction Methods. Ph.D. thesis, University of Paderborn (2003)

[MR09]

Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Berlin (2009)CrossRef

[Ngu10]

Nguyen, P.Q.: Hermite’s constant and lattice algorithms. In: Nguyen, P.Q., Vallée, B. (eds.) The LLL Algorithm, Information Security and Cryptography, pp. 19–69. Springer, Berlin (2010)

[NLV11]

Naehrig, M., Lauter, K.E., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Cachin, C., Ristenpart, T. (eds), ACM CCSW, pp. 113–124, ACM (2011)

[NS97]

Nguyên, P.Q., Stern, J.: Merkle-hellman revisited: a cryptanalysis of the qu-vanstone cryptosystem based on group factorizations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 198–212. Springer, Heidelberg (1997) CrossRef

[NS98a]

Nguyên, P.Q., Stern, J.: The béguin-quisquater server-aided RSA protocol from crypto 1995 is not secure. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 372–379. Springer, Heidelberg (1998) CrossRef

[NS98b]

Nguyên, P.Q., Stern, J.: Cryptanalysis of a fast public key cryptosystem presented at SAC 1997. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, p. 213. Springer, Heidelberg (1999) CrossRef

[NS99]

Nguyên, P.Q., Stern, J.: The hardness of the hidden subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 31. Springer, Heidelberg (1999) CrossRef

[NS01]

Nguyên, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 146. Springer, Heidelberg (2001) CrossRef

[NT12]

Nguyen, P.Q., Tibouchi, M.: Lattice-based fault attacks on signatures. In: Joye, M., Tunstall, M. (eds.) Fault Analysis in Cryptography, Information Security and Cryptography, pp. 201–220. Springer, Berlin (2012)CrossRef

[Pai99]

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 223. Springer, Heidelberg (1999) CrossRef

[S+14]

Stein, W. et al.: Sage Mathematics Software (Version 6.4). The Sage Development Team (2014). http://www.sagemath.org

[vdPS13]

van de Pol, J., Smart, N.P.: Estimating key sizes for high dimensional lattice-based systems. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 290–303. Springer, Heidelberg (2013) CrossRef

Titel: Cryptanalysis of the Co-ACD Assumption
verfasst von: Pierre-Alain Fouque
Moon Sung Lee
Tancrède Lepoint
Mehdi Tibouchi
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology -- CRYPTO 2015
Print ISBN: 978-3-662-47988-9

Electronic ISBN: 978-3-662-47989-6

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-47989-6_27

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