README.md

DDH attack

sage attack.sage

Discriminant is  -174557545091416252635003194444861205363819426306550719724615444118398924653740853473200690165023980144269305313623219072619881598803017038440606788399640708500954596365702268338314218456077198381637651986824178122536367069027837416763824399587567438806907526544381205640408340191555642933450043607423990229926944652

starting DDH

starting attack DDH

DDH broken this cannot happen

Credits

Credit for the aux.sage file goes to Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker, authors of the paper "Practical Fully Secure Unrestricted Inner Product Functional Encryption modulo p".

attack.sage

load("aux.sage")
load("aux2.sage")

#### START ALGORITHM
a_bits = 10
b_bits = 512
k_bits = 256

while True:
    a = next_prime(ZZ.random_element(2^a_bits))
    b = ZZ.random_element(2^b_bits)
    if (b^2 -a^2)% 9 == 0:
        break

k = a*b
D = -3*k^2

print()
print("Discriminant is ", D)
print()

# you are not supposed to know this for high b 
#h = gp.qfbclassno(D)
#assert h % 3 ==0

r = next_probable_prime(ZZ.random_element(2^a_bits))
while (kronecker_symbol(D, r)!=1):
    r = next_probable_prime(ZZ.random_element(2^a_bits))

g = qfbprimeform(D, r)

# working in the principal genus
g = reduction(comp(g,g))[0]  

## DDH
print("starting DDH")
print()

# DH
x = ZZ.random_element(2^k_bits)
y = ZZ.random_element(2^k_bits)

gx = expo_pari(g,x)
gy = expo_pari(g,y)

assert  expo_pari(gx,y) == expo_pari(gy,x) 
gz =  expo_pari(gx,y)

print("starting attack DDH")
print()

cr = a^2*b

# selecting gnenerator having cubic resiude -1
prg =prime_represented(g)
if cubic_symbol(cr,prg) == 1:
    print("alg cannot work both: generator have cubic residue 1")
    exit()

prgx = prime_represented(gx)
prgy = prime_represented(gy)
r = ZZ.random_element(2^k_bits)
gr = expo_pari(g,r)
prgr =prime_represented(gr)

if cubic_symbol(cr,prgx) == 1 or cubic_symbol(cr,prgy) == 1:
    prgz = prime_represented(gz)
    assert cubic_symbol(cr,prgz) 
    if cubic_symbol(cr,prgr) == -1:
        print("DDH broken this cannot happen")
        print()
    else:
        print("all good: random form has cubic residue 1")
        print()
 
else:
    print("alg cannot work both: shares have cubic residue -1")
    print()

aux.sage

## Credits
# Credit for the `aux.sage` file goes to Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker, authors of the paper ["Practical Fully Secure Unrestricted Inner Product Functional Encryption modulo p"](https://eprint.iacr.org/2018/791.pdf).


#### AUXILIARY METHODS

def rho(f,sqrtDisc=0):
  """
  rho(f,sqrtDisc=0)
  
  INPUT:
      f -- a binary quadratic form 
      sqrtDisc -- optional: if f is indefinite square root of its discriminant
 
  OUTPUT:
      g,M where g is obtained from a reduction step of f:=(a,b,c), i.e., the normalization of (c,-b,a) and M the unimodular transformation

  """
  if type(f) == type([]): # list if indef form
    if not sqrtDisc:
       sqrtDisc = RF(sqrt(f[0].discriminant()))
    h,N = normalize([BinaryQF([f[0]._c, -f[0]._b, f[0]._a]), f[1]],sqrtDisc)
    h[1] = h[1] - L([f[0]._b/(2*f[0]._a), 1/(2*f[0]._a)], sqrtDisc)

  else:
    h,N = normalize(BinaryQF([f._c, -f._b, f._a]))

  return h, Matrix(ZZ,[[0,-1],[1,0]])*N

def isReduced(f,sqrtDisc=0):
  """
  isReduced(f,sqrtDisc=0)

  INPUT:
      f -- a binary quadratic form
      sqrtDisc -- optional: if f is indefinite square root of its discriminant
  
  OUTPUT:
      true if f is reduced
  """

  if type(f) == type([]): # list if indef form
    if not sqrtDisc:
      sqrtDisc = RF(sqrt(f[0].discriminant()))
    return abs(sqrtDisc-2*abs(f[0]._a)) < f[0]._b < sqrtDisc

  else:
    return f.is_reduced()


def comp(f,g):
  """
  comp(f, g)

  INPUT:
      f,g -- two binary quadratic forms of same disc
  
  OUTPUT:
      composition of f and g with pari
  """

  if type(f) == type([]): # list if indef form    
    h = BinaryQF(list(pari('Vec(qfbcompraw(Qfb(%s,%s,%s),Qfb(%s,%s,%s)))'%(f[0]._a,f[0]._b,f[0]._c,g[0]._a,g[0]._b,g[0]._c)))[:3])
    return [h, f[1]+g[1]]
  else:
    h = BinaryQF(list(pari('Vec(qfbcompraw(Qfb(%s,%s,%s),Qfb(%s,%s,%s)))'%(f._a,f._b,f._c,g._a,g._b,g._c))))
    
    return h


def reduction(f,sqrtDisc=0):
  """
  reduction(f,sqrtDisc=0)

  INPUT:
      f -- a binary quadratic form
      sqrtDisc -- optional: if f is indefinite square root of its discriminant
 
  OUTPUT:
      g,M where g is the reduce quadratic form equivalent to f and M the unimodular transformation
  """
  if (type(f) == type([])) and (not sqrtDisc):
    sqrtDisc = RF(sqrt(f[0].discriminant()))

  h,M = normalize(f,sqrtDisc)

  while not isReduced(h):
    h,N = rho(h,sqrtDisc)
    M = M*N

  return h,M

def qfbprimeform(D,p):
  """
  qfbprimeform(D,p)
  
  INPUT:
     D, p -- quad disc, and a prime (D,p)=1
  
  OUTPUT:
     the prime form of discriminant D with f._a=p, (D,p)=1, with pari
  """
  if D <0: 
    return normalize(BinaryQF(list(pari('Vec(qfbprimeform(%s,%s))'%(D, p)))[0:3]))[0]
  else:
    return normalize([BinaryQF(list(pari('Vec(qfbprimeform(%s,%s))'%(D, p)))[0:3]),0])[0]

def normalize(f,sqrtDisc=0):
  """
  normalize(f,sqrtDisc=0)
  
  INPUT:
      f -- a binary quadratic form
      sqrtDisc -- optional: if f is indefinite square root of its discriminant

  OUTPUT:
      g, M where g is the normalization of f and the unimodular transformation M from f to g    """
  if type(f) == type([]): # list if indef form
     if not sqrtDisc:
       sqrtDisc = RF(sqrt(f[0].discriminant()))
     if abs(f[0]._a) < sqrtDisc:
       s = sign(f[0]._a) * integer_floor((sqrtDisc-f[0]._b)/(2*abs(f[0]._a)))
     else:
       s= sign(f[0]._a) * integer_floor((abs(f[0]._a)-f[0]._b)/(2*abs(f[0]._a)))
       
     return  [BinaryQF([f[0]._a, f[0]._b+2*s*f[0]._a, f[0]._a*s^2+f[0]._b*s+f[0]._c]), f[1]], Matrix(ZZ,[[1,s],[0,1]]) 

  else:
    s = floor((f._a - f._b)/(2*f._a))
    return BinaryQF([f._a, f._b+2*s*f._a, f._a*s^2+f._b*s+f._c]), Matrix(ZZ,[[1,s],[0,1]]) 

def expo_pari(f,n):
  """
  expo_pari(f, n)

  INPUT:
      f -- binary quadratic form of neg disc
      n -- integer
  
  OUTPUT:
      red element of [f]^n with pari
  """

  return BinaryQF(list(pari('Vec(qfbnupow(Qfb(%s,%s,%s),%s))'%(f._a,f._b,f._c,n))))

aux2.sage

def prime_represented(a):
    """
    prime_represented(a)

    INPUT:
    a -- a binary quadratic form
     
    OUTPUT:
    p, a prime p represented by a such that p=1 mod 3"""

    for i in range(0,10000):
        for j in range(0,10000):
            if a(i,j) in Primes():
                if a(i,j) % 3 == 1:
                    return a(i,j)

def cubic_symbol(a,p):
    """
    cubic_symbol(a,p)

    INPUT:
    a -- an intege
    p -- a prime p such that p=1 mod 3
     
    OUTPUT:
    Return the cubic residue symbol"""

    crs = pow(a, (p-1)//3, p)
    if crs == 0 or crs == 1:
        return crs
    
    return -1