# Nguyen-Stern algorithm and multivariate algorithm

a guest
Feb 10th, 2020
2,139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #; -*- mode: python;-*-
2.
3. # This is an implementation of the Nguyen-Stern algorithm, and of our new multivariate attack
4.
5. # To run the Nguyen-Stern algorithm, run the function NSattack().
6. # To run all the experiments with the Nguyen-Stern algorithm, run the function statNS().
7. # We provide the experimental results below.
8.
9. # To run our algorithm, run the function multiAttack().
10. # To run all the experiments with our algorithm, run the function statMulti().
11. # We provide the experimental results below.
12.
13. from time import time
14.
15. def genpseudoprime(eta,etamin=211):
16.   if eta<=(2*etamin):
17.     return random_prime(2^eta,False,2^(eta-1))
18.   else:
19.     return random_prime(2^etamin,False,2^(etamin-1))*genpseudoprime(eta-etamin)
20.
21. def genParams(n=10,m=20,nx0=100):
22.   #print "Generation of x0",
23.   t=time()
24.   x0=genpseudoprime(nx0)
25.   #print time()-t
26.
27.   # We generate the alpha_i's
28.   a=vector(ZZ,n)
29.   for i in range(n):
30.     a[i]=mod(ZZ.random_element(x0),x0)
31.
32.   # The matrix X has m rows and must be of rank n
33.   while True:
34.     X=Matrix(ZZ,m,n)
35.     for i in range(m):
36.       for j in range(n):
37.         X[i,j]=ZZ.random_element(2)
38.     if X.rank()==n: break
39.
40.   # We generate an instance of the HSSP: b=X*a
41.   c=vector(ZZ,[0 for i in range(m)])
42.   s=ZZ.random_element(x0)
43.   b=X*a
44.   for i in range(m):
45.     b[i]=mod(b[i],x0)
46.
47.   return x0,a,X,b
48.
49. # We generate the lattice of vectors orthogonal to b modulo x0
50. def orthoLattice(b,x0):
51.   m=b.length()
52.   M=Matrix(ZZ,m,m)
53.
54.   for i in range(1,m):
55.     M[i,i]=1
56.   M[1:m,0]=-b[1:m]*inverse_mod(b[0],x0)
57.   M[0,0]=x0
58.
59.   for i in range(1,m):
60.     M[i,0]=mod(M[i,0],x0)
61.
62.   return M
63.
64. def allones(v):
65.   if len([vj for vj in v if vj in [0,1]])==len(v):
66.     return v
67.   if len([vj for vj in v if vj in [0,-1]])==len(v):
68.     return -v
69.   return None
70.
71. def recoverBinary(M5):
72.   lv=[allones(vi) for vi in M5 if allones(vi)]
73.   n=M5.nrows()
74.   for v in lv:
75.     for i in range(n):
76.       nv=allones(M5[i]-v)
77.       if nv and nv not in lv:
78.         lv.append(nv)
79.       nv=allones(M5[i]+v)
80.       if nv and nv not in lv:
81.         lv.append(nv)
82.   return Matrix(lv)
83.
84. def allpmones(v):
85.   return len([vj for vj in v if vj in [-1,0,1]])==len(v)
86.
87. # Computes the right kernel of M using LLL.
88. # We assume that m>=2*n. This is only to take K proportional to M.height()
89. # We follow the approach from https://hal.archives-ouvertes.fr/hal-01921335/document
90. def kernelLLL(M):
91.   n=M.nrows()
92.   m=M.ncols()
93.   if m<2*n: return M.right_kernel().matrix()
94.   K=2^(m//2)*M.height()
95.
96.   MB=Matrix(ZZ,m+n,m)
97.   MB[:n]=K*M
98.   MB[n:]=identity_matrix(m)
99.
100.   MB2=MB.T.LLL().T
101.
102.   assert MB2[:n,:m-n]==0
103.   Ke=MB2[n:,:m-n].T
104.
105.   return Ke
106.
107. # This is the Nguyen-Stern attack, based on BKZ in the second step
108. def NSattack(n=60):
109.   m=int(max(2*n,16*log(n,2)))
110.   print "n=",n,"m=",m,
111.
112.   iota=0.035
113.   nx0=int(2*iota*n^2+n*log(n,2))
114.   print "nx0=",nx0
115.
116.   x0,a,X,b=genParams(n,m,nx0)
117.
118.   M=orthoLattice(b,x0)
119.
120.   t=cputime()
121.   M2=M.LLL()
122.   print "LLL step1: %.1f" % cputime(t),
123.
124.   assert sum([vi==0 and 1 or 0 for vi in M2*X])==m-n
125.   MOrtho=M2[:m-n]
126.
127.   print "  log(Height,2)=",int(log(MOrtho.height(),2)),
128.
129.   t2=cputime()
130.   ke=kernelLLL(MOrtho)
131.
132.   print "  Kernel: %.1f" % cputime(t2),
133.   print "  Total step1: %.1f" % cputime(t)
134.
135.   if n>170: return
136.
137.   beta=2
138.   tbk=cputime()
139.   while beta<n:
140.     if beta==2:
141.       M5=ke.LLL()
142.     else:
143.       M5=M5.BKZ(block_size=beta)
144.
145.     # we break when we only get vectors with {-1,0,1} components
146.     if len([True for v in M5 if allpmones(v)])==n: break
147.
148.     if beta==2:
149.       beta=10
150.     else:
151.       beta+=10
152.
153.   print "BKZ beta=%d: %.1f" % (beta,cputime(tbk)),
154.   t2=cputime()
155.   MB=recoverBinary(M5)
156.   print "  Recovery: %.1f" % cputime(t2),
157.   print "  Number of recovered vector=",MB.nrows(),
158.   nfound=len([True for MBi in MB if MBi in X.T])
159.   print "  NFound=",nfound,
160.
161.   NS=MB.T
162.   invNSn=matrix(Integers(x0),NS[:n]).inverse()
163.   ra=invNSn*b[:n]
164.   nrafound=len([True for rai in ra if rai in a])
165.   print "  Coefs of a found=",nrafound,"out of",n,
166.   print "  Total step2: %.1f" % cputime(tbk),
167.   print "  Total time: %.1f" % cputime(t)
168.
169.
170. def statNS():
171.   for n in range(70,190,20)+range(190,280,30):
172.     NSattack(n)
173.     print
174.
175. def matNbits(M):
176.   return max([M[i,j].nbits() for i in range(M.nrows()) for j in range(M.ncols())])
177.
178. # Matrix rounding to integers
179. def roundM(M):
180.   M2=Matrix(ZZ,M.nrows(),M.ncols())
181.   for i in range(M.nrows()):
182.     for j in range(M.ncols()):
183.       M2[i,j]=round(M[i,j])
184.   return M2
185.
186. def orthoLatticeMod(b,n,x0):
187.   m=b.length()
188.   assert m>=3*n
189.   assert m % n==0
190.   M=Matrix(ZZ,m,3*n)
191.   M[:2*n,:2*n]=identity_matrix(2*n)
192.   for i in range(2,m/n):
193.     M[i*n:(i+1)*n,2*n:3*n]=identity_matrix(n)
194.
195.   M[1:,0]=-b[1:]*inverse_mod(b[0],x0)
196.   M[0,0]=x0
197.
198.   for i in range(1,m):
199.     M[i,0]=mod(M[i,0],x0)
200.   return M
201.
202. def NZeroVectors(M):
203.   return sum([vi==0 and 1 or 0 for vi in M])
204.
205.
206. # This is our new multivariate attack
207. def multiAttack(n=16):
208.   if n % 2==1:
209.     m=n*(n+3)/2 # n is odd
210.   else:
211.     m=n*(n+4)/2 # n is even
212.   k=4
213.
214.   print "n=",n,"m=",m,"k=",k,
215.
216.   iota=0.035
217.   nx0=int(2*iota*n^2+n*log(n,2))
218.   print "nx0=",nx0
219.
220.   x0,a,X,b=genParams(n,m,nx0)
221.
222.   M=orthoLatticeMod(b,n,x0)
223.
224.   print "Step 1",
225.   t=cputime()
226.
227.   M[:n//k,:n//k]=M[:n//k,:n//k].LLL()
228.
229.   M2=M[:2*n,:2*n].LLL()
230.   tprecomp=cputime(t)
231.   print "  LLL:%.1f" % tprecomp,
232.
233.   RF=RealField(matNbits(M))
234.
235.   M4i=Matrix(RF,M[:n//k,:n//k]).inverse()
236.   M2i=Matrix(RDF,M2).inverse()
237.
238.   ts1=cputime()
239.   while True:
240.     flag=True
241.     for i in range((m/n-2)*k):
242.       indf=2*n+n//k*(i+1)
243.       if i==(m/n-2)*k-1:
244.         indf=m
245.
246.       mv=roundM(M[2*n+n//k*i:indf,:n//k]*M4i)
247.       if mv==0:
248.         continue
249.       flag=False
250.       M[2*n+n//k*i:indf,:]-=mv*M[:n//k,:]
251.     if flag: break
252.   print "  Sred1:%.1f" % cputime(ts1),
253.
254.   M[:2*n,:2*n]=M2
255.
256.   ts2=cputime()
257.   while True:
258.     #print "  matNBits(M)=",matNbits(M[2*n:])
259.     mv=roundM(M[2*n:,:2*n]*M2i)
260.     if mv==0: break
261.     M[2*n:,:]-=mv*M[:2*n,:]
262.   print "  Sred2:%.1f" % cputime(ts2),
263.
264.   # The first n vectors of M should be orthogonal
265.   northo=NZeroVectors(M[:n,:2*n]*X[:2*n])
266.
267.   for i in range(2,m/n):
268.     northo+=NZeroVectors(M[i*n:(i+1)*n,:2*n]*X[:2*n]+X[i*n:(i+1)*n])
269.
270.   print "  #ortho vecs=",northo,"out of",m-n,
271.
272.   # Orthogonal of the orthogonal vectors
273.   # We compute modulo 3
274.   MO=Matrix(GF(3),n,m)
275.
276.   tk=cputime()
277.   MO[:,:2*n]=kernelLLL(M[:n,:2*n])
278.   print "  Kernel LLL: %.1f" % cputime(tk),
279.
280.   for i in range(2,m/n):
281.     MO[:,i*n:(i+1)*n]=-(M[i*n:(i+1)*n,:2*n]*MO[:,:2*n].T).T
282.   #print "Total kernel computation",cputime(tk)
283.   print "  Total Step 1: %.1f" % cputime(t)
284.
285.   print "Step 2",
286.   t2=cputime()
287.   xt23=Matrix(GF(3),[(-x).list()+[x[i]*x[j]*((i==j) and 1 or 2) for i in range(n) for j in range(i,n)] for x in MO.T])
288.   ke3=xt23.right_kernel().matrix()
289.   print "  Kernel: %.1f" % cputime(t2),
290.
291.   assert xt23.nrows()==m
292.   assert xt23.ncols()==n*(n+1)/2+n
293.
294.   ke23=Matrix(GF(3),n,n*n)
295.   ind=n
296.   for i in range(n):
297.     for j in range(i,n):
298.       ke23[:,i*n+j]=ke3[:,ind]
299.       ke23[:,j*n+i]=ke3[:,ind]
300.       ind+=1
301.
302.   tei=cputime()
303.   # We will compute the list of eigenvectors
305.   # We loop over the coordinates. This will split the eigenspaces.
306.   li=[Matrix(GF(3),identity_matrix(n))]
307.   for j in range(n):       # We loop over the coordinates of the wi vectors.
308.     #print "j=",j
309.     M=ke23[:,j*n:(j+1)*n]   # We select the submatrix corresponding to coordinate j
310.     li2=[]                 # We initialize the next list
311.     for v in li:
312.       if v.nrows()==1:     # We are done with this eigenvector
313.         li2.append(v)
314.       else:     # eigenspace of dimension >1
315.         #print "eigenspace of dim:",v.nrows()
316.         A=v.solve_left(v*M)  # v*M=A*v. When we apply M on the right, this is equivalent to applying the matrix A.
317.                               # The eigenvalues of matrix A correspond to the jth coordinates of the wi vectors in that
318.                               # eigenspace
319.         for e,v2 in A.eigenspaces_left():    # We split the eigenspace according to the eigenvalues of A.
320.           vv2=v2.matrix()
321.           #print "  eigenspace of dim:",(vv2*v).nrows()
322.           li2.append(vv2*v)                   # The new eigenspaces
323.
324.     li=li2
325.
326.   #print "Eigenvectors computation",cputime(tei)
327.
328.   NS=Matrix([v[0] for v in li])*MO
329.   for i in range(n):
330.     if any(c==2 for c in NS[i]): NS[i]=-NS[i]
331.
332.   print "  Number of recovered vectors:",NS.nrows(),
333.
334.   nfound=len([True for NSi in NS if NSi in X.T])
335.   print "  NFound=",nfound,"out of",n,
336.
337.   NS=NS.T
338.
339.   # b=X*a=NS*ra
340.   invNSn=matrix(Integers(x0),NS[:n]).inverse()
341.   ra=invNSn*b[:n]
342.   nrafound=len([True for rai in ra if rai in a])
343.
344.   print "  Coefs of a found=",nrafound,"out of",n,
345.   print "  Total step2: %.1f" % cputime(t2),
346.   print "  Total runtime: %.1f" % cputime(t),
347.   print
348.
349. def statMulti():
350.   for n in range(70,210,20)+[220,250]:
351.     multiAttack(n)
352.     print
353.
354. # Results for the Nguyen-Stern algorithm
355. """
356. n= 70 m= 140 nx0= 772
357. LLL step1: 3.1   log(Height,2)= 3   Kernel: 1.6   Total step1: 4.8
358. BKZ beta=2: 0.1   Recovery: 1.3   Number of recovered vector= 70   NFound= 70   Coefs of a found= 70 out of 70   Total step2: 1.6   Total time: 6.3
359.
360. n= 90 m= 180 nx0= 1151
361. LLL step1: 10.2   log(Height,2)= 3   Kernel: 4.9   Total step1: 15.1
362. BKZ beta=10: 0.6   Recovery: 2.8   Number of recovered vector= 90   NFound= 90   Coefs of a found= 90 out of 90   Total step2: 3.8   Total time: 18.8
363.
364. n= 110 m= 220 nx0= 1592
365. LLL step1: 28.7   log(Height,2)= 4   Kernel: 12.5   Total step1: 41.2
366. BKZ beta=10: 3.1   Recovery: 5.3   Number of recovered vector= 110   NFound= 110   Coefs of a found= 110 out of 110   Total step2: 9.3   Total time: 50.5
367.
368. n= 130 m= 260 nx0= 2095
369. LLL step1: 81.8   log(Height,2)= 4   Kernel: 24.8   Total step1: 106.7
370. BKZ beta=20: 10.1   Recovery: 9.1   Number of recovered vector= 130   NFound= 130   Coefs of a found= 130 out of 130   Total step2: 20.5   Total time: 127.2
371.
372. n= 150 m= 300 nx0= 2659
373. LLL step1: 159.6   log(Height,2)= 5   Kernel: 44.7   Total step1: 204.3
374. BKZ beta=30: 243.2   Recovery: 13.6   Number of recovered vector= 150   NFound= 150   Coefs of a found= 150 out of 150   Total step2: 258.8   Total time: 463.1
375.
376. n= 170 m= 340 nx0= 3282
377. LLL step1: 370.5   log(Height,2)= 5   Kernel: 115.3   Total step1: 485.9
378. BKZ beta=30: 26304.5   Recovery: 20.0   Number of recovered vector= 170   NFound= 170   Coefs of a found= 170 out of 170   Total step2: 26328.1   Total time: 26814.0
379.
380. n= 190 m= 380 nx0= 3965
381. LLL step1: 823.1   log(Height,2)= 6   Kernel: 180.9   Total step1: 1004.1
382.
383. n= 220 m= 440 nx0= 5099
384. LLL step1: 3827.6   log(Height,2)= 7   Kernel: 1751.9   Total step1: 5579.6
385.
386. n= 250 m= 500 nx0= 6366
387. LLL step1: 7163.8   log(Height,2)= 7   Kernel: 3388.0   Total step1: 10552.0
388. """
389.
390.
391. # Results for our multivariate algorithm
392. """
393. n= 70 m= 2590 k= 4 nx0= 772
394. Step 1   LLL:3.1   Sred1:1.4   Sred2:1.9   #ortho vecs= 2520 out of 2520   Kernel LLL: 1.7   Total Step 1: 8.5
395. Step 2   Kernel: 8.6   Number of recovered vectors: 70   NFound= 70 out of 70   Coefs of a found= 70 out of 70   Total step2: 16.4   Total runtime: 24.9
396.
397. n= 90 m= 4230 k= 4 nx0= 1151
398. Step 1   LLL:10.7   Sred1:4.2   Sred2:4.4   #ortho vecs= 4140 out of 4140   Kernel LLL: 5.0   Total Step 1: 25.3
399. Step 2   Kernel: 23.0   Number of recovered vectors: 90   NFound= 90 out of 90   Coefs of a found= 90 out of 90   Total step2: 40.9   Total runtime: 66.2
400.
401. n= 110 m= 6270 k= 4 nx0= 1592
402. Step 1   LLL:32.1   Sred1:7.9   Sred2:10.9   #ortho vecs= 6160 out of 6160   Kernel LLL: 11.7   Total Step 1: 64.4
403. Step 2   Kernel: 52.1   Number of recovered vectors: 110   NFound= 110 out of 110   Coefs of a found= 110 out of 110   Total step2: 89.4   Total runtime: 153.7
404.
405. n= 130 m= 8710 k= 4 nx0= 2095
406. Step 1   LLL:87.4   Sred1:18.2   Sred2:22.6   #ortho vecs= 8580 out of 8580   Kernel LLL: 26.8   Total Step 1: 158.3
407. Step 2   Kernel: 112.7   Number of recovered vectors: 130   NFound= 130 out of 130   Coefs of a found= 130 out of 130   Total step2: 184.5   Total runtime: 342.9
408.
409. n= 150 m= 11550 k= 4 nx0= 2659
410. Step 1   LLL:217.9   Sred1:33.6   Sred2:36.6   #ortho vecs= 11400 out of 11400   Kernel LLL: 48.4   Total Step 1: 341.6
411. Step 2   Kernel: 206.9   Number of recovered vectors: 150   NFound= 150 out of 150   Coefs of a found= 150 out of 150   Total step2: 329.2   Total runtime: 670.8
412.
413. n= 170 m= 14790 k= 4 nx0= 3282
414. Step 1   LLL:425.7   Sred1:58.6   Sred2:66.6   #ortho vecs= 14620 out of 14620   Kernel LLL: 81.9   Total Step 1: 640.5
415. Step 2   Kernel: 358.7   Number of recovered vectors: 170   NFound= 170 out of 170   Coefs of a found= 170 out of 170   Total step2: 558.8   Total runtime: 1199.3
416.
417. n= 190 m= 18430 k= 4 nx0= 3965
418. Step 1   LLL:1421.4   Sred1:97.5   Sred2:114.0   #ortho vecs= 18240 out of 18240   Kernel LLL: 206.6   Total Step 1: 1850.4
419. Step 2   Kernel: 576.3   Number of recovered vectors: 190   NFound= 190 out of 190   Coefs of a found= 190 out of 190   Total step2: 879.0   Total runtime: 2729.4
420.
421. n= 220 m= 24640 k= 4 nx0= 5099
422. Step 1   LLL:3273.3   Sred1:216.1   Sred2:227.5   #ortho vecs= 24420 out of 24420   Kernel LLL: 2044.5   Total Step 1: 5778.5
423. Step 2   Kernel: 1108.7   Number of recovered vectors: 220   NFound= 220 out of 220   Coefs of a found= 220 out of 220   Total step2: 1630.1   Total runtime: 7408.6
424.
425. n= 250 m= 31750 k= 4 nx0= 6366
426. Step 1   LLL:7157.7   Sred1:352.4   Sred2:421.0   #ortho vecs= 31500 out of 31500   Kernel LLL: 3947.6   Total Step 1: 11902.7
427. Step 2   Kernel: 1842.2   Number of recovered vectors: 250   NFound= 250 out of 250   Coefs of a found= 250 out of 250   Total step2: 2750.1   Total runtime: 14652.8
428. """