Advertisement
Guest User

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!
Python 13.64 KB | None | 0 0
  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
  304.   # We start with the full space.
  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. """
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement