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

Keywords

Homomorphic NTRU
IND-CPA security
Lattices
LLL algorithm
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, Lattices, LLL algorithm, NTRU",

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

note = "Funding Information: Acknowledgement. Hyang-Sook Lee and Seongan Lim were supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2016R1D1A1B01008562). Ikkwon Yie was supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2017R1D1A1B03034721). Funding Information: Hyang-Sook Lee and Seongan Lim were supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2016R1D1A1B01008562). Ikkwon Yie was supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2017R1D1A1B03034721). 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 - Funding Information: Acknowledgement. Hyang-Sook Lee and Seongan Lim were supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2016R1D1A1B01008562). Ikkwon Yie was supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2017R1D1A1B03034721). Funding Information: Hyang-Sook Lee and Seongan Lim were supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2016R1D1A1B01008562). Ikkwon Yie was supported by Basic Science Research Program through the NRF funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2017R1D1A1B03034721). 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 - Lattices

KW - LLL algorithm

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

Keywords

Access to Document

Fingerprint

Cite this