A lattice attack on homomorphic NTRU with non-invertible public keys

Soyoung Ahn; Hyang Sook Lee; Seongan Lim; Ikkwon Yie

doi:10.1007/978-3-319-89500-0_22

A lattice attack on homomorphic NTRU with non-invertible public keys

Soyoung Ahn, Hyang Sook Lee, Seongan Lim, Ikkwon Yie

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In 2011, Stehlé and Steinfeld modified the original NTRU to get a provably IND-CPA secure NTRU under the hardness assumption of standard worst-case problems over ideal lattices. In 2012, López-Alt et al. proposed the first multikey fully homomorphic encryption scheme based on the IND-CPA secure NTRU. Interestingly, this homomorphic NTRU and subsequent homomorphic variants of NTRU removed the condition ‘invertible public key’ of the underlying IND-CPA secure NTRU. In this paper, we investigate the security influence of using non-invertible public key in the homomorphic NTRU. As a result, we present how to mount a lattice attack to message recovery for the homomorphic NTRU when the public key is non-invertible. Our result suggests that using invertible public keys in the homomorphic NTRU is necessary for its security.

Original language	English
Title of host publication	Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings
Editors	Sihan Qing, Dongmei Liu, Chris Mitchell, Liqun Chen
Publisher	Springer Verlag
Pages	248-254
Number of pages	7
ISBN (Print)	9783319894997
DOIs	https://doi.org/10.1007/978-3-319-89500-0_22
State	Published - 2018
Event	19th International Conference on Information and Communications Security, ICICS 2017 - Beijing, China Duration: 6 Dec 2017 → 8 Dec 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10631 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Information and Communications Security, ICICS 2017
Country/Territory	China
City	Beijing
Period	6/12/17 → 8/12/17

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.

Keywords

Homomorphic NTRU
IND-CPA security
LLL algorithm
Lattices
NTRU

Access to Document

10.1007/978-3-319-89500-0_22

Cite this

Ahn, S., Lee, H. S., Lim, S., & Yie, I. (2018). A lattice attack on homomorphic NTRU with non-invertible public keys. In S. Qing, D. Liu, C. Mitchell, & L. Chen (Eds.), Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings (pp. 248-254). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10631 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-89500-0_22

Ahn, Soyoung ; Lee, Hyang Sook ; Lim, Seongan et al. / A lattice attack on homomorphic NTRU with non-invertible public keys. Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. editor / Sihan Qing ; Dongmei Liu ; Chris Mitchell ; Liqun Chen. Springer Verlag, 2018. pp. 248-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{00e0925e39824099b7585c0f2f4eae6a,

title = "A lattice attack on homomorphic NTRU with non-invertible public keys",

abstract = "In 2011, Stehl{\'e} and Steinfeld modified the original NTRU to get a provably IND-CPA secure NTRU under the hardness assumption of standard worst-case problems over ideal lattices. In 2012, L{\'o}pez-Alt et al. proposed the first multikey fully homomorphic encryption scheme based on the IND-CPA secure NTRU. Interestingly, this homomorphic NTRU and subsequent homomorphic variants of NTRU removed the condition {\textquoteleft}invertible public key{\textquoteright} of the underlying IND-CPA secure NTRU. In this paper, we investigate the security influence of using non-invertible public key in the homomorphic NTRU. As a result, we present how to mount a lattice attack to message recovery for the homomorphic NTRU when the public key is non-invertible. Our result suggests that using invertible public keys in the homomorphic NTRU is necessary for its security.",

keywords = "Homomorphic NTRU, IND-CPA security, LLL algorithm, Lattices, NTRU",

author = "Soyoung Ahn and Lee, {Hyang Sook} and Seongan Lim and Ikkwon Yie",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 19th International Conference on Information and Communications Security, ICICS 2017 ; Conference date: 06-12-2017 Through 08-12-2017",

year = "2018",

doi = "10.1007/978-3-319-89500-0_22",

language = "English",

isbn = "9783319894997",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "248--254",

editor = "Sihan Qing and Dongmei Liu and Chris Mitchell and Liqun Chen",

booktitle = "Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings",

}

Ahn, S, Lee, HS, Lim, S & Yie, I 2018, A lattice attack on homomorphic NTRU with non-invertible public keys. in S Qing, D Liu, C Mitchell & L Chen (eds), Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10631 LNCS, Springer Verlag, pp. 248-254, 19th International Conference on Information and Communications Security, ICICS 2017, Beijing, China, 6/12/17. https://doi.org/10.1007/978-3-319-89500-0_22

A lattice attack on homomorphic NTRU with non-invertible public keys. / Ahn, Soyoung; Lee, Hyang Sook; Lim, Seongan et al.
Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. ed. / Sihan Qing; Dongmei Liu; Chris Mitchell; Liqun Chen. Springer Verlag, 2018. p. 248-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10631 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A lattice attack on homomorphic NTRU with non-invertible public keys

AU - Ahn, Soyoung

AU - Lee, Hyang Sook

AU - Lim, Seongan

AU - Yie, Ikkwon

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - In 2011, Stehlé and Steinfeld modified the original NTRU to get a provably IND-CPA secure NTRU under the hardness assumption of standard worst-case problems over ideal lattices. In 2012, López-Alt et al. proposed the first multikey fully homomorphic encryption scheme based on the IND-CPA secure NTRU. Interestingly, this homomorphic NTRU and subsequent homomorphic variants of NTRU removed the condition ‘invertible public key’ of the underlying IND-CPA secure NTRU. In this paper, we investigate the security influence of using non-invertible public key in the homomorphic NTRU. As a result, we present how to mount a lattice attack to message recovery for the homomorphic NTRU when the public key is non-invertible. Our result suggests that using invertible public keys in the homomorphic NTRU is necessary for its security.

AB - In 2011, Stehlé and Steinfeld modified the original NTRU to get a provably IND-CPA secure NTRU under the hardness assumption of standard worst-case problems over ideal lattices. In 2012, López-Alt et al. proposed the first multikey fully homomorphic encryption scheme based on the IND-CPA secure NTRU. Interestingly, this homomorphic NTRU and subsequent homomorphic variants of NTRU removed the condition ‘invertible public key’ of the underlying IND-CPA secure NTRU. In this paper, we investigate the security influence of using non-invertible public key in the homomorphic NTRU. As a result, we present how to mount a lattice attack to message recovery for the homomorphic NTRU when the public key is non-invertible. Our result suggests that using invertible public keys in the homomorphic NTRU is necessary for its security.

KW - Homomorphic NTRU

KW - IND-CPA security

KW - LLL algorithm

KW - Lattices

KW - NTRU

UR - http://www.scopus.com/inward/record.url?scp=85045962169&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-89500-0_22

DO - 10.1007/978-3-319-89500-0_22

M3 - Conference contribution

AN - SCOPUS:85045962169

SN - 9783319894997

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 248

EP - 254

BT - Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings

A2 - Qing, Sihan

A2 - Liu, Dongmei

A2 - Mitchell, Chris

A2 - Chen, Liqun

PB - Springer Verlag

T2 - 19th International Conference on Information and Communications Security, ICICS 2017

Y2 - 6 December 2017 through 8 December 2017

ER -

Ahn S, Lee HS, Lim S, Yie I. A lattice attack on homomorphic NTRU with non-invertible public keys. In Qing S, Liu D, Mitchell C, Chen L, editors, Information and Communications Security - 19th International Conference, ICICS 2017, Proceedings. Springer Verlag. 2018. p. 248-254. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-89500-0_22

A lattice attack on homomorphic NTRU with non-invertible public keys

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this