212 2013 6
Vol. 21No. 2 Journal of Beijing Electronic Science and Technology Institute
RLWE
1 2 1 21 22 1. 1000701
2.710071
Jun. 2013
: NTRU
: ; ; ; RLWE;RLWE
: TN918. 1 : A : 1672464X 2013 064604
1
1. 1
12:12…m m
L 12…m12…m
:
m
L 12 …ma ii a iZ
i1
12…mL
Dim LMMNLMNLFull Dimensional1. 2
22 SVPShortest Vector Problem :BZnm BxxZmy Z m y0B y
32 CVPClosest Vector Problem : BZnm tZnBx xZmyZm
Hoffstein J 1
1998NTRU NTRUNTRU2005 Regev
Learning with ErrorsLWE 2242010Lyuba shevskyRLWE 5RLWE
:NO. 61070219
:1989
21 RLWE
tByt 1.3
56
4SearchRLWE:RZqx xn 1 n2kk1q1mod2na RmmaaeRabRbasea bsSearch RLWE
5DecisionRLWE:R
Zqxxn 1n2kk1q1mod2ns
Rm ms
aRmeRa
basebRA ab s
AsRR Decision RLWEDeci sion RLWEAs
2RLWE
2. 1 npq
n:
n2k
q: qq q
47 kR:kfxkf0 kf1x
…kf
n1
xn1
fxgx fgxk
ij
n1
k0 ijk modn
2. 2
h x
fx f pxfxgxfxgx
0modq
f x fqx1modq
hx fqx 1
hxgxfx
fp x
2. 3
e x
p:n
2. 4
c xf x
fpx : xfxcx
fxhxmx fxgx e x
fx fqxfxmxf x g x e x modq 1
fxmx
fpxaxfpxfxmxmodp
m x2
12
1qq2
22
NTRU7
m x : c x mx gxex
h x
pp
RZqxx1
fgf xf0f1 x
…f xn1gxggx…f xn1 n1 01 n1
22
48
3
2013
3. 3NTRU
NTRU NTRUNTRU
NTRUNTRUNTRUNTRU
NTRUNTRU
4
RLWE NTRU NTRU
:
1HOFFSTEIN JPIPHER JSILVERMAN J H. NTRU : A ringbased public key cryptosystem C. Proceedings of the 3rd International Sympo siumANTSIII LNCS 14231998: 267
288.
2Regev O. On latticeslearning with errorsran
dom linear codesand cryptographyC. In Pro
3. 1
:T
m xINDCPAT TOn Search RLWE
:AINDCPASearch RLWE B OAsAsabbasee R BOA sa bbaseeRB ab absBb asgeab AAabs INDCPA Search RLWE
3. 2
f x g x0modqf x fq x1modqhx fqx 1
21 RLWE
ceedings of STOC2005pp. 113117. 3Gentry CPeikert Cand Vaikuntanathan V.
Trapdoors for hard lattices and new cryptographic constructionsC. STOC08VictoriaBC CanadaACM2008: 197206.
4Peikert C. Publickey cryptosystems from the worstcase shortest vector problemC. STOC 09MarylandUSAACM2009: 333342.
5LYUBASHEVSHY VPEIKERT CREGEV O.
49 On ideal lattice and learning with errors over rings
C. In Eurocrypt 2010LNCS 6110SpringVerlag2010: 123.
6.RLWENTRU J. . 2012. 5. 15. 7.NTRU
J. . 20087 .314 .
A New Publickey Cryptosystem Based on RLWE
Bai Jian12 Liu Hui12 Zhang Ruoqing12 Yang Yatao2
1. Beijing Electronic Science and Technology InstituteBeijing 100070China
2. School of Telecommunication EngineeringXidian UniversityXian710071China Abstract: Publickey cryptosystems based on lattice is postquantum cryptography and the efficiency is highwhich now becomes a hot topic. Publickey 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 publickey cryptosystem with NTRU.
Keywords: Cryptography; Postquantum Cryptosystem; Publickey Cryptosystem Based on Lattice; RLWELearning with Errors over Rings ; Publickey Cryptosystem Based on RLWE
:
Reviews
There are no reviews yet.