A polynomial time algorithm for breaking NTRU encryption with multiple keys

Jiseung Kim; Changmin Lee

doi:10.1007/s10623-023-01233-5

A polynomial time algorithm for breaking NTRU encryption with multiple keys

Jiseung Kim
, Changmin Lee^*

^*Corresponding author for this work

Korea Institute for Advanced Study

Research output: Contribution to journal › Journal article › peer-review

8 Scopus citations

Abstract

We present a polynomial time algorithm for breaking NTRU encryption schemes with multiple keys. Our algorithm takes advantage of the specific sampling regime used in NTRU encryption, which samples secret polynomials with a fixed number of coefficients of 1 and - 1 . By constructing an equation system on the secret keys, we are able to recover the unique secret key when n multiple keys sharing a common denominator are given for an extension degree n. This result shows that NTRU encryption schemes with multiple keys can be solved in polynomial time in n.

Original language	English
Pages (from-to)	2779-2789
Number of pages	11
Journal	Designs, Codes, and Cryptography
Volume	91
Issue number	8
DOIs	https://doi.org/10.1007/s10623-023-01233-5
State	Published - 2023.08

Keywords

Cryptanalysis
Lattices
NTRU encryption with multiple keys
NTRUPrime with multiple keys

Quacquarelli Symonds(QS) Subject Topics

Computer Science & Information Systems
Mathematics
Data Science

Access to Document

10.1007/s10623-023-01233-5

Cite this

@article{ca0575ab93704193b82a172ed6109251,

title = "A polynomial time algorithm for breaking NTRU encryption with multiple keys",

abstract = "We present a polynomial time algorithm for breaking NTRU encryption schemes with multiple keys. Our algorithm takes advantage of the specific sampling regime used in NTRU encryption, which samples secret polynomials with a fixed number of coefficients of 1 and - 1 . By constructing an equation system on the secret keys, we are able to recover the unique secret key when n multiple keys sharing a common denominator are given for an extension degree n. This result shows that NTRU encryption schemes with multiple keys can be solved in polynomial time in n.",

keywords = "Cryptanalysis, Lattices, NTRU encryption with multiple keys, NTRUPrime with multiple keys",

author = "Jiseung Kim and Changmin Lee",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = aug,

doi = "10.1007/s10623-023-01233-5",

language = "English",

volume = "91",

pages = "2779--2789",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

number = "8",

}

TY - JOUR

T1 - A polynomial time algorithm for breaking NTRU encryption with multiple keys

AU - Kim, Jiseung

AU - Lee, Changmin

PY - 2023/8

Y1 - 2023/8

N2 - We present a polynomial time algorithm for breaking NTRU encryption schemes with multiple keys. Our algorithm takes advantage of the specific sampling regime used in NTRU encryption, which samples secret polynomials with a fixed number of coefficients of 1 and - 1 . By constructing an equation system on the secret keys, we are able to recover the unique secret key when n multiple keys sharing a common denominator are given for an extension degree n. This result shows that NTRU encryption schemes with multiple keys can be solved in polynomial time in n.

AB - We present a polynomial time algorithm for breaking NTRU encryption schemes with multiple keys. Our algorithm takes advantage of the specific sampling regime used in NTRU encryption, which samples secret polynomials with a fixed number of coefficients of 1 and - 1 . By constructing an equation system on the secret keys, we are able to recover the unique secret key when n multiple keys sharing a common denominator are given for an extension degree n. This result shows that NTRU encryption schemes with multiple keys can be solved in polynomial time in n.

KW - Cryptanalysis

KW - Lattices

KW - NTRU encryption with multiple keys

KW - NTRUPrime with multiple keys

UR - https://www.scopus.com/pages/publications/85158102697

U2 - 10.1007/s10623-023-01233-5

DO - 10.1007/s10623-023-01233-5

M3 - Journal article

AN - SCOPUS:85158102697

SN - 0925-1022

VL - 91

SP - 2779

EP - 2789

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 8

ER -

A polynomial time algorithm for breaking NTRU encryption with multiple keys

Abstract

Keywords

Quacquarelli Symonds(QS) Subject Topics

Access to Document

Other files and links

Fingerprint

Cite this