21 2 2013 6
Vol. 21No. 2 Journal of Beijing Electronic Science and Technology Institute
R LWE
1 2 1 2 1 2 2 1. 1000701
2. 710071
Jun. 2013
: NTRU
: ; ; ; R LWE; R LWE
: TN918. 1 : A : 1672 464X 2013 06 46 04
1
1. 1
12:12…m m
L 12…m 12…m
:
m
L 1 2 … m a i i a i Z
i 1
12…m L
Dim L MMN L M N L Full Dimensional 1. 2
22 SVPShortest Vector Problem : BZnm BxxZmy Z m y 0 B y
32 CVPClosest Vector Problem : B Znm t Zn Bx x Zm y Zm
Hoffstein J 1
1998 NTRU NTRU NTRU 2005 Regev
Learning with ErrorsLWE 2 242010 Lyuba shevsky R LWE 5 R LWE
: NO. 61070219
: 1989
21 RLWE
tByt 1.3
56
4SearchRLWE:R Zqx xn 1 n 2kk1q 1mod2na Rm m a a e R a b R b a s e a b s Search R LWE
5DecisionRLWE:R
Zqxxn 1n2kk1q1mod2ns
Rm m s
aRmeRa
basebRA ab s
As R R Decision R LWE Deci sion R LWE As
2 R LWE
2. 1 npq
n:
n 2k
q: q q q
47 kR:kfx kf0 kf1x
…kf
n1
xn1
fxgx fgxk
ij
n1
k 0 i j k modn
2. 2
h x
f x f p x fxgxfxgx
0modq
f x fq x 1modq
hx fqx 1
h x g x f x
fp x
2. 3
e x
p: n
2. 4
c x f x
fpx : x fxcx
fxhxmx fxgx e x
fx fqx fxmx f x g x e x modq 1
fxmx
fpxax fpxfxmxmodp
m x 2
1 2
1 qq2
22
NTRU7
m x : c x mx gxex
h x
pp
RZqxx1
fgf x f0 f1 x
…f xn1gxggx…f xn1 n1 01 n1
22
48
3
2013
3. 3 NTRU
NTRU NTRU NTRU
NTRU NTRU NTRU NTRU
NTRU NTRU
4
R LWE NTRU NTRU
:
1HOFFSTEIN JPIPHER JSILVERMAN J H. NTRU : A ring based public key cryptosystem C. Proceedings of the 3rd International Sympo sium ANTS III LNCS 14231998: 267
288.
2Regev O. On latticeslearning with errorsran
dom linear codesand cryptographyC. In Pro
3. 1
: T
m x IND CPA T TOn Search R LWE
:AINDCPA Search R LWE B O As Asabbasee R B O A s a b b a s e e R B ab ab s Bb asgeab AAab s IND CPA Search R LWE
3. 2
f x g x 0modqf x fq x 1modq hx fqx 1
21 RLWE
ceedings of STOC2005pp. 113 117. 3Gentry CPeikert Cand Vaikuntanathan V.
Trapdoors for hard lattices and new cryptographic constructionsC. STOC08VictoriaBC CanadaACM2008: 197 206.
4Peikert C. Public key cryptosystems from the worst case shortest vector problemC. STOC 09MarylandUSAACM2009: 333 342.
5LYUBASHEVSHY VPEIKERT CREGEV O.
49 On ideal lattice and learning with errors over rings
C. In Eurocrypt 2010LNCS 6110Spring Verlag2010: 1 23.
6. R LWE NTRU J. . 2012. 5. 15. 7. NTRU
J. . 2008 7 . 31 4 .
A New Public key Cryptosystem Based on R LWE
Bai Jian12 Liu Hui12 Zhang Ruoqing12 Yang Yatao2
1. Beijing Electronic Science and Technology InstituteBeijing 100070China
2. School of Telecommunication EngineeringXidian UniversityXian710071China Abstract: Public key cryptosystems based on lattice is post quantum cryptography and the efficiency is highwhich now becomes a hot topic. Public key cryptosystem is designed based on the learning with errors over ring in lattice. We give the choice of parameters and how to generate the keysencrypt
theplaintextanddecryptthecipertextindetails. Andalsothesecurityofthispublickeycryptosys tem and the analysis of efficiency are discussed. In the endwe compare the public key cryptosystem with NTRU.
Keywords: Cryptography; Post quantum Cryptosystem; Public key Cryptosystem Based on Lattice; R LWE Learning with Errors over Rings ; Public key Cryptosystem Based on R LWE
: