Vulnerable Public Keys in NTRU Cryptosystem
- PDF / 151,338 Bytes
- 8 Pages / 532.91 x 737.01 pts Page_size
- 2 Downloads / 209 Views
Chinese Annals of Mathematics, Series B c The Editorial Office of CAM and
Springer-Verlag Berlin Heidelberg 2020
Vulnerable Public Keys in NTRU Cryptosystem∗ Liqing XU1
Hao CHEN1
Chao LI2
Longjiang QU2
Abstract In this paper the authors give an efficient bounded distance decoding (BDD for short) algorithm for NTRU lattices under some conditions about the modulus number q and the public key h. They then use this algorithm to give plain-text recovery attack to NTRUEncrypt and forgery attack on NTRUSign. In particular the authors figure out a weak domain of public keys such that the recent transcript secure version of NTRU signature scheme NTRUMLS with public keys in this domain can be forged. Keywords Lattice, CVP, NTRU Lattice 2000 MR Subject Classification 11H06, 52C07
1 Introduction 1.1 SVP and approximating SVP A lattice L is a discrete subgroup in Rn generated by several linear independent vectors b1 , · · · , bm over the ring of integers, where m ≤ n, L := {a1 b1 + · · ·+ am bm : a1 ∈ Z, · · · , am ∈ p Z}. The volume vol(L) of this lattice is det(B · Bτ ), where B := (bij ) is the m × n generator matrix of this lattice, where bi = (bi1 , · · · , bin ) ∈ Rn , i = 1, · · · , m, are base vectors of this lattice. The length of the shortest non-zero lattice vectors is denoted by λ1 (L). The famous
shortest vector problem (SVP for short) is as follows: Given an arbitrary Z basis of an arbitrary lattice L, find a lattice vector with length λ1 (L) (see [12]). The approximating SVP Gap SVPf (m) is to find some lattice vectors of length within f (m)λ1 (L), where f (m) is an approximating factor as a function of the lattice dimension m (see [12]). A breakthrough result of Ajtai [1] shows that SVP is NP-hard under the randomized reduction. Another breakthrough proved by Micciancio asserts that approximating SVP within a constant factor is NP-hard under the randomized reduction (see [12]). For the latest development we refer to [10]. It has been proved that approximating SVP within a quasi-polynomial factor is NP-hard under the randomized reduction. Since the publication of [5], block Korkine-Zolotarev (BKZ for short) type algorithms with extreme pruning enumerations of large blocksizes 50 − 150 as subroutines were proposed such Manuscript received January 2, 2019. College of Information Science and Technology/College of Cyber Security, Jinan University, Guangzhou 510632, China. E-mail: [email protected] [email protected] 2 The College of Liberal Arts and Science, National University of Defence Technology, Changsha 410073, China. E-mail: lichao [email protected] ljqu [email protected] ∗ This work was supported by the National Natural Science Foundation of China (Nos. 11531002, 61722213, 61572026) and by the Major Program of Guangdong Basic and Applied Research (No. 2019B030302008). 1 The
658
L. Q. Xu, H. Chen, C. Li and L. J. Qu
that relative “shorter” lattice bases can be reduced from arbitrary given lattice bases. These algorithms can be used to solve some NTRU challenge problems (see [3, 5]). 1.2 NTRUEncrypt and NT
Data Loading...
