API tools faq
paste
Guest User

Cryptanalysis of GGH15 multilinear maps

a guest
Apr 12th, 2016
637
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 11.94 KB | None | 0 0
raw download clone embed print report
  1. from itertools import product
  2.  
  3. n=2
  4. m=10
  5. nb=12
  6. m2=m//2
  7. nq=nb*m2
  8. q=random_prime(2^nq,lbound=2^(nq-1))
  9. B=2
  10.  
  11. R=ZZ["x"]
  12. K=CyclotomicField(2*n,"x")
  13. f=R.gen()**n+1
  14. Rq=R.change_ring(IntegerModRing(q))
  15. Rqf=Rq.quotient_ring(Rq.ideal(f))
  16.  
  17. def roundFromK(a):
  18.   return R([round(c) for c in a.list()])
  19.  
  20. def roundFromVecK(v):
  21.   return vector([roundFromK(vi) for vi in v])
  22.  
  23. def roundCoef(p):
  24.   res=[]
  25.   for c in p.change_ring(ZZ).list():
  26.     if c<q/2:
  27.       res.append(c)
  28.     else:
  29.       res.append(c-q)
  30.   return ZZ['x'](res)
  31.  
  32. def roundCoefVec(v):
  33.   return vector(map(roundCoef,v))
  34.  
  35. def prodScal(a,b):
  36.   return sum([a[i]*b[i] for i in range(len(a))])
  37.  
  38. def randVecRq(l):
  39.   return vector(Rq,[Rq.random_element(degree=n-1) for i in range(l)])
  40.  
  41. def randVecRSmall(l):
  42.   return vector(R,[R.random_element(x=-B,y=B+1,degree=n-1) for i in range(l)])
  43.  
  44. def randomMatRSmall(l):
  45.   return Matrix(R,[[R.random_element(x=-B,y=B+1,degree=n-1) for i in range(l)] for j in range(l)])
  46.  
  47. def genKeySample():
  48.   c=randVecRq(m//2)
  49.   X=randomMatRSmall(m//2)
  50.   b=vector(ZZ,[2^(i*nb) for i in range(m2)])
  51.   a=vector(Rq,list(c)+list((b+c*X) % f))
  52.   return a,X
  53.  
  54. def binary(u):
  55.   dig=[u[i].lift().digits(base=2^nb,padto=m//2) for i in range(n)]
  56.   return vector(R,[R([dig[i][j] for i in range(n)]) for j in range(m//2)])
  57.  
  58. def sample(a,X,u,fullSize=False):
  59.   """Return small s such that a.s=u [q] where a=[c | b+c.X]
  60.     With fullSize=True, s is full size modulo q"""
  61.   if fullSize:
  62.     s=randVecRq(m)
  63.     s[0]=Rq((u-prodScal(s[1:],a[1:]) % f)*a[0].inverse_mod(f)) % f
  64.     s=roundCoefVec([Rq(si) for si in s])
  65.   else:
  66.     c=a[0:m//2]
  67.     sp1=vector(R,[R.random_element(x=-2^nb,y=2^nb,degree=n-1) for i in range(m//2)]) # randVecRSmall(m//2)
  68.     b=vector(ZZ,[2^(i*nb) for i in range(m2)])
  69.     s2=binary((u-prodScal(c,sp1)) % f)
  70.     s1=sp1-X*s2 % f
  71.     s=vector(list(s1)+list(s2))
  72.   return s
  73.  
  74. def testSample():
  75.   R=ZZ["x"]
  76.   K=CyclotomicField(2*n,"x")
  77.   f=R.gen()**n+1
  78.   Rq=R.change_ring(IntegerModRing(q))
  79.  
  80.   a,X=genKeySample()
  81.   u=Rq.random_element(degree=n-1)
  82.   print u
  83.   s=sample(a,X,u)
  84.   print "u=",u,"\na=",a,"\ns=",s,"\na.s=",prodScal(a,s) % f
  85.  
  86. class KeySample():
  87.   def __init__(self):
  88.     self.a,self.X=genKeySample()
  89.  
  90.   def sampleVec(self,u,fullSize):
  91.     return sample(self.a,self.X,u,fullSize)
  92.    
  93.   def sampleMat(self,U,fullSize):
  94.     return Matrix([self.sampleVec(u % f,fullSize) for u in U]).transpose()
  95.  
  96.   def sampleMatApprox(self,U,fullSize=False):
  97.     E=randVecRSmall(m)
  98.     return self.sampleMat(U+E,fullSize)
  99.  
  100. def toR(x):
  101.   return ZZ['x'](map(ZZ,x.list()))
  102.  
  103. def toVecR(v):
  104.   return vector(ZZ['x'],map(toR,v.list()))
  105.  
  106. def toMatR(M):
  107.   return Matrix([toVecR(v*v.denominator()) for v in M])
  108.  
  109. # attack without the safeGuards
  110. def genParams(kappa=3,safeGuards=False):
  111.   if not n.is_power_of(2):
  112.     raise ValueError
  113.  
  114.   print "n=",n
  115.   print "m=",m
  116.   print "q=",q
  117.  
  118.   print "size of q=",q.nbits()
  119.  
  120.   r=2*m+2
  121.   nv=r+1   # we need 2*m+3 encodings Cij
  122.   nu=r+2   # total number of encodings
  123.  
  124.   print "r=",r
  125.   while True:
  126.     print "Generating the Aij matrices"
  127.     A0=randVecRq(m)
  128.     Aij=[[KeySample() for j in range(kappa)] for i in range(kappa)]
  129.  
  130.     print "Generating the secret exponents"
  131.     s=randVecRSmall(kappa)
  132.     t=[s]+[randVecRSmall(kappa) for i in range(nv)]
  133.  
  134.     print "Generating encodings Cij"
  135.     Cij=[[[] for j in range(kappa)] for i in range(kappa)]
  136.     for (i,j,l) in product(range(kappa),range(kappa),range(nu)):
  137.       Cij[i][j].append(Aij[i][j].sampleMatApprox( \
  138.                t[l][(j-i+kappa)%kappa] * (Aij[i][j+1].a if j<kappa-1 else A0)))
  139.  
  140.     print "Attack first step"
  141.    
  142.     # to adapt the indices to arbitrary kappa, it's easiest to consider
  143.     # the second row and the last row (of index 1 and k=kappa-1
  144.     # respectively); on the second row, t_2 appears third, and on the last
  145.     # row, t_kappa appears in the last but one position, hence the
  146.     # following choice.
  147.  
  148.     k   = kappa-1
  149.     l0  = 1   # we work with constant indices for t_3,...,t_kappa
  150.     A10 = Aij[1][0] # row 2
  151.     Ak0 = Aij[k][0] # row kappa
  152.  
  153.     #       t_kappa            t_1
  154.     C1L = [Cij[1][0][l0] * Cij[1][1][l] for l in range(nu)]
  155.  
  156.     #       t_2               t_3*...*t_{kappa-1}
  157.     C1R = [Cij[1][2][l] * prod([Cij[1][j][l0] for j in range(3,kappa)]) \
  158.            for l in range(nu)]
  159.  
  160.     #       t_2               t_3*...*t_{kappa}      
  161.     CkL = [Cij[k][0][l] * prod([Cij[k][j][l0] for j in range(1,kappa-1)]) \
  162.            for l in range(nu)]
  163.  
  164.     #       t_1
  165.     CkR = [Cij[k][k][l] for l in range(nu)]
  166.  
  167.     W=Matrix(K,[[roundCoef(( \
  168.         (A10.a*C1L[i]*C1R[j]-Ak0.a*CkL[j]*CkR[i]) % f)[0]) \
  169.                  for j in range(1,1+r)] for i in range(nv)])   # nv=r+1
  170.  
  171.     W2=Matrix(K,[[roundCoef(( \
  172.         (A10.a*C1L[i]*C1R[j]-Ak0.a*CkL[j]*CkR[i]) % f)[0]) \
  173.                   for j in range(1,1+r)] for i in [0]+range(2,nu)])  #nu=nv+1=r+2
  174.    
  175.     print "  Kernel computation"
  176.  
  177.     a=W.kernel().matrix()[0]       #len(a)=nv=r+1
  178.     b=W2.kernel().matrix()[0]      #len(b)=nv=r+1
  179.  
  180.     gc=gcd(a.denominator(),b.denominator())
  181.     print "  gc=",gc
  182.     if gc!=1:
  183.       print "  gc<>1: we restart the attack"
  184.       continue
  185.  
  186.     a=toVecR(a*a.denominator())
  187.     b=toVecR(b*b.denominator())
  188.  
  189.     a=vector(a.list()+[0])
  190.     b=vector([b[0]]+[0]+b.list()[1:])
  191.  
  192.     print "  Bezout computation"
  193.  
  194.     gc,ca,cb=xgcd(ZZ(a[0]),ZZ(b[0]))
  195.     u=ca*a+cb*b    # we have u[0]=1   len(u)=nu=nv+1=r+2
  196.  
  197.     ps=prodScal([ti[0] for ti in t],u) % f # ps should be 0.
  198.  
  199.     print "  Check scalar product:",ps
  200.     if ps==0: break
  201.  
  202.   print "Attack second step"
  203.   # we compute the difference between the first line and the last line
  204.  
  205.   A00 = Aij[0][0]
  206.  
  207.   #         t1
  208.   C0L = [Cij[0][0][l] for l in range(nu)]
  209.  
  210.   #         t2                 t3*...*t_{kappa}
  211.   C0R = [Cij[0][1][l] * prod([Cij[0][j][l0] for j in range(2,kappa)]) \
  212.          for l in range(nu)]
  213.  
  214.   Omega=sum([vector([roundCoef(((A00.a*C0L[j]*C0R[l]-Ak0.a*CkL[l]*CkR[j]) % f)[0]) for l in range(1,m+1)])*(-u[j])  % f for j in range(1,len(u))])
  215.  
  216.   # equivalent of D00, the private key for user 1.
  217.   D0Lp=prodScal([-ui for ui in u[1:]],C0L[1:])
  218.  
  219.   # this product is computed from public encodings.
  220.   C0Rp =Matrix(K,[[roundCoef(C0R[j][i][0]) for j in range(1,m+1)] for i in range(m)])
  221.  
  222.   print "  C0Rp.rank()=",C0Rp.rank()
  223.  
  224.   print "  Computing approximate error vector"
  225.   E=roundFromVecK(C0Rp.solve_left(Omega))
  226.  
  227.   print "true secret:"
  228.   print A00.a*prod([Cij[0][i][0] for i in range(kappa)]) % f
  229.   print "computed secret:"
  230.   print (A00.a*D0Lp-E)*prod([Cij[0][i][0] for i in range(1,kappa)]) % f
  231.  
  232.  
  233. def genParamsSafeguards(kappa=3):
  234.   if not n.is_power_of(2):
  235.     raise ValueError
  236.  
  237.   print "n=",n
  238.   print "m=",m
  239.   print "q=",q
  240.  
  241.   s=randVecRSmall(kappa)
  242.   print "s=",s
  243.  
  244.   print "Generating graded encoding parameters with safeguards"
  245.  
  246.   A0=randVecRq(m)
  247.   Aij=[[KeySample() for j in range(kappa)] for i in range(kappa)]
  248.  
  249.   # for some reason this sometimes does not work
  250.   #Rij=[[random_matrix(Rqf,m,m,algorithm='echelonizable',rank=m) if j>0 else \
  251.   #        identity_matrix(Rqf, m) for j in range(kappa)] for i in range(kappa)]
  252.  
  253.   Rij=[[random_matrix(Rqf,m,m) if j>0 else \
  254.           identity_matrix(Rqf, m) for j in range(kappa)] for i in range(kappa)]
  255.  
  256.   Rijinv=[[Rij[i][j]^(-1) for j in range(kappa)] for i in range(kappa)]
  257.  
  258.   # lift from Rqf to Rq
  259.   Rij=[[Rij[i][j].apply_map(lift) for j in range(kappa)] \
  260.           for i in range(kappa)]
  261.   Rijinv=[[Rijinv[i][j].apply_map(lift) for j in range(kappa)] \
  262.           for i in range(kappa)]
  263.  
  264.   r=2*m+2
  265.   print "r=",r
  266.   nenc=m+r  # total number of encodings
  267.   print "nenc=",nenc
  268.  
  269.   print "Generating Diffie-Hellman encodings with safeguards"
  270.   t=[s]+[randVecRSmall(kappa) for i in range(1,nenc)]
  271.  
  272.   Cij=[[[] for j in range(kappa)] for i in range(kappa)]
  273.  
  274.   for (i,j,l) in product(range(kappa),range(kappa),range(nenc)):
  275.     v=t[l][(j-i+kappa)%kappa] * (Aij[i][j+1].a if j<kappa-1 else A0)
  276.     fullSize=(j==0)
  277.     C= Aij[i][j].sampleMatApprox(v,fullSize)
  278.     Cij[i][j].append(Rij[i][j] * C * (Rijinv[i][j+1] if j<kappa-1 else Rijinv[i][0]) % f)
  279.  
  280.   # This is step one of the attack without safeguards.
  281.   print "Phase 1: finding a linear relation between secret exponent and other exponent"
  282.   k   = kappa-1
  283.   l0  = 1
  284.   A10 = Aij[1][0]
  285.   Ak0 = Aij[k][0]
  286.  
  287.   #       t_kappa            t_1
  288.   C1L = [Cij[1][0][l0] * Cij[1][1][l]  % f for l in range(nenc)]
  289.    
  290.   #       t_2               t_3*...*t_{kappa-1}
  291.   C1R = [Cij[1][2][l] * prod([Cij[1][j][l0] for j in range(3,kappa)]) % f \
  292.            for l in range(nenc)]
  293.  
  294.   #       t_2               t_3*...*t_{kappa}      
  295.   CkL = [Cij[k][0][l] * prod([Cij[k][j][l0] for j in range(1,kappa-1)]) % f \
  296.            for l in range(nenc)]
  297.  
  298.   #       t_1      
  299.   CkR = [Cij[k][k][l] for l in range(nenc)]
  300.  
  301.   print "  Finding relations between discrete logs"
  302.  
  303.   for nk in range(r+2,nenc+1):  # we initially work with nk vectors in total
  304.     W=Matrix(K,[[roundCoef(( \
  305.           (A10.a*C1L[i]*C1R[j]-Ak0.a*CkL[j]*CkR[i]) % f)[0]) \
  306.                for j in range(1,1+r)] for i in [0]+range(1,nk-1)])
  307.  
  308.     W2=Matrix(K,[[roundCoef(( \
  309.           (A10.a*C1L[i]*C1R[j]-Ak0.a*CkL[j]*CkR[i]) % f)[0]) \
  310.                 for j in range(1,1+r)] for i in [0]+range(2,nk)])
  311.  
  312.     a=W.kernel().matrix()[0]   # len(a)=nk-1
  313.     b=W2.kernel().matrix()[0]  # len(b)=nk-1
  314.     gc=gcd(a.denominator(),b.denominator())
  315.     print "  nk=",nk,"gc=",gc
  316.     if gc==1:
  317.       break
  318.      
  319.   assert gc==1
  320.  
  321.   a=toVecR(a*a.denominator())  
  322.   b=toVecR(b*b.denominator())  
  323.  
  324.   # we now work with vectors of size nenc=r+m=3m+2
  325.   a=vector(a.list()+[0]+[0 for i in range(nenc-nk)])
  326.   b=vector([b[0]]+[0]+b.list()[1:]+[0 for i in range(nenc-nk)])
  327.  
  328.   print "  gcd computation"
  329.    
  330.   gc,ca,cb=xgcd(ZZ(a[0]),ZZ(b[0]))
  331.   u=ca*a+cb*b    # we have u[0]=1   len(u)=nenc
  332.  
  333.   ps=prodScal([t[l][0] for l in range(nenc)],u) % f
  334.  
  335.   print "  Check scalar product:",ps
  336.   assert ps==0
  337.  
  338.   print "Phase 2: expressing the encoding of s_kappa on first row as a linear combination of the others."
  339.  
  340.   A00 = Aij[0][0]
  341.  
  342.   #         t1
  343.   C0L = [Cij[0][0][l] for l in range(nenc)]
  344.  
  345.   #         t2*...*t_{kappa_1}                                t_{kappa}
  346.   C0R = [prod([Cij[0][j][l0] for j in range(1,kappa-1)]) * Cij[0][kappa-1][l] % f \
  347.          for l in range(nenc)]
  348.  
  349.   #       t_kappa            
  350.   C1L = [Cij[1][0][l]  for l in range(nenc)]
  351.    
  352.   #       t_1             t_2*...*t_{kappa-1}
  353.   C1R = [Cij[1][1][l] * prod([Cij[1][j][l0] for j in range(2,kappa)]) % f \
  354.            for l in range(nenc)]
  355.  
  356.  
  357.   W=Matrix(K,[[roundCoef(( \
  358.           (A00.a*C0L[j]*C0R[i]-A10.a*C1L[i]*C1R[j]) % f)[0]) \
  359.                for j in range(1,1+r)] for i in range(nenc)])
  360.  
  361.   vker=W.kernel().matrix()[0]
  362.  
  363.   # same as the attack without safeguards
  364.   print "Phase 3: computing Omega and computing the error"
  365.  
  366.   A00 = Aij[0][0]
  367.  
  368.   #         t1
  369.   C0L = [Cij[0][0][l] for l in range(nenc)]
  370.  
  371.   #         t2*...*t_{kappa_1}                                t_{kappa}
  372.   C0R = [prod([Cij[0][j][0] for j in range(1,kappa-1)]) * Cij[0][kappa-1][l] % f \
  373.          for l in range(nenc)]
  374.  
  375.   #         t2*...*t_{kappa-1}                              t_{kappa}
  376.   CkL = [prod([Cij[k][j][0] for j in range(kappa-2)]) * Cij[k][kappa-2][l] % f \
  377.            for l in range(nenc)]
  378.  
  379.   #       t_1      
  380.   CkR = [Cij[k][k][l] for l in range(nenc)]
  381.  
  382.   Omega=vector(K,sum([vector([roundCoef(((A00.a*C0L[j]*C0R[l]-Ak0.a*CkL[l]*CkR[j]) % f)[0]) \
  383.                      for l in range(1,nenc)])*(-u[j])  % f for j in range(1,len(u))]))
  384.  
  385.   #  estimated error
  386.   EC=roundFromK(prodScal(Omega,(-vker)[1:]))
  387.  
  388.   # equivalent of D00, the private key for user 1.
  389.   D0Lp=prodScal([-ui for ui in u[1:]],C0L[1:]) %f
  390.  
  391.   print "true secret:"
  392.   print A00.a*prod([Cij[0][i][0] for i in range(kappa)]) % f
  393.  
  394.   print "Computing the first component of the secret:"
  395.   print (A00.a*D0Lp*prod([Cij[0][i][0] for i in range(1,kappa)]) % f)[0]-EC
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!