Cryptanalysis of new Compact-LWE

Attack-newCLWE.sage

# ========================
# Compact-LWE parameters in NIST PQC Round 1
# ========================
q=2^64
t=2^32
m=128
wPos=224
wNeg=32
b=16
bp=68719476736
n=8
ll=8
R=Integers(q)
sk_max = 229119
p_size = 16777216
e_min  = 457
e_max  = 3200
# ========================
def newkeygen():
    s =vector(R, [R.random_element() for _ in range(n)])
    sp=vector(R, [R.random_element() for _ in range(n)])
    k = 0
    while gcd(k,q)>1:
        k = randint(1,q)
    kp= 0
    while gcd(kp,q)>1:
        kp= randint(1,q)
    p=0
    while gcd(p,q)>1 and sk_max * bp + p + e_max * p * (wPos+wNeg) < q:
        ptmp = randint(0,p_size)
        p = (wPos+wNeg) * bp + ptmp
    ck =0
    ckp=0
    while gcd(ckp,p)>1:
        ck = randint(1,p)
        ckp= randint(1,p)
    sk =0
    skp=0
    while gcd(sk*ck+skp*ckp,p)>1:
        sk = randint(1,sk_max)
        skp= randint(1,sk_max)
    return s,k,sk,ck,sp,kp,skp,ckp,p

def newsamplegen(s,k,sk,ck,sp,kp,skp,ckp,p):
    Rp = Integers(p)
    A =random_matrix(ZZ,m,n,x=0,y=b)
    u =vector(R,[randint(0,bp-1) for _ in range(m)])
    e =vector(R, [randint(e_min,e_max) for _ in range(m)])
    ep=vector(R, [randint(e_min,e_max) for _ in range(m)])
    r =vector(R, [randint(0,p-1) for _ in range(m)])
    # ck * ri + ckp * rpi = 0 mod p
    rp=vector(R, [(Rp(-ck * r[i].lift())/Rp(ckp)) for i in range(m)])
    v = A*s + R(1)/R(k) * (sk*u + r + p*e)
    vp= A*sp+ R(1)/R(kp)* (skp*u + rp + p*ep)
    return A,u.lift(),v.lift(),vp.lift(),e,ep

def check_l(l,u):
    pos_l = vector(ZZ,[z for z in l if z > 0])
    neg_l = vector(ZZ,[z for z in l if z < 0])
    pos_sum = pos_l * vector(ZZ,[1 for _ in range(len(pos_l))])
    neg_sum = neg_l * vector(ZZ,[1 for _ in range(len(neg_l))])
    uu = vector(ZZ,l)  * u
    return (pos_sum >= wPos) and (pos_sum <= wPos + wNeg) and (-wNeg <= neg_sum) and (neg_sum <= 0) and (uu > 0)

# Note: We sampled a vector l in the very lazy way.
# def sample_l(u): # Simple version.
#   l = vector(ZZ,[0 for _ in range(m)])
#   while not check_l(l,u):
#        l = vector(ZZ,[randint(-2,4) for _ in range(m)])
#   return l

def generate_l():
# the sum of positive entries in l will be psel
# the sum of negative entries in l will be -nsel
    buf = [randint(0,255) for _ in range(512)]
    if wNeg > 0:
        psel  = wPos + (buf[0] % wNeg)
        nsel = buf[1] % wNeg
    else:
        psel  = wPos
        nsel = 0
    l = [0 for _ in range(m)]
    posc = 0
    negc = 0
    count = psel if (nsel == 0) else (psel/nsel + 1)
    for i in range(psel+nsel):
        slot = buf[i+2] % m;
        if (count > 0) and (posc < psel):
            while (l[slot] < 0): # Move away from a negative entry
                slot = (slot + 1) % m;
            l[slot] = l[slot] + 1
            count -= 1
            posc += 1
        else:
            while (l[slot] > 0): # Move away from a negative entry
                slot = (slot + 1) % m;
            l[slot] = l[slot] - 1
            count = psel if (nsel == 0) else (psel/nsel + 1)
            negc += 1
    return l

def sample_l(u):
    l = generate_l()
    while not check_l(l,u):
        l = generate_l()
    return l

def rol(z,d):
    # cyclic left shift
    return int((z<<d)/t) + (z<<d)%t

def find_zp(z,t):
    zp = int(z/t)
    while gcd(zp,t) > 1:
        zp +=1
    return zp

def dem_encrypt(z,mu):
    zp = find_zp(z,t)
    d  = ((mu ^^ rol(z,int(log(t,2)/2))) * zp) % t
    return d

def dem_decrypt(z,d):
    zp = find_zp(z,t)
    zpinv = inverse_mod(zp,t)
    return ((zpinv * d) % t) ^^ rol(z,int(log(t,2)/2))

def kem_encrypt(A,u,v,vp):
    l = vector(ZZ,sample_l(u))
    a = l * A
    x = (l * v) % q
    xp= (l * vp) % q
    # z is a session key of KEM
    z = (l * u) % t
    return a.change_ring(ZZ),x,xp,z,l

def kem_decrypt(s,k,sk,ck,sp,kp,skp,ckp,p,a,x,xp):
    Rp = Integers(p)
    d1 = R((x - a * s) * k).lift()
    d1p= R((xp - a * sp) * kp).lift()
    d2 = Rp(ck * d1 + ckp * d1p).lift()
    sckinv = inverse_mod(sk*ck+skp*ckp,p)
    d3 = Rp(sckinv * d2).lift()
    return d3 % t

def pke_encrypt(A,u,v,vp,mu):
    a,x,xp,z,l = kem_encrypt(A,u,v,vp)
    d = dem_encrypt(z,mu)
    return a,x,xp,d, z,l

def pke_decrypt(s,k,sk,ck,sp,kp,skp,ckp,p,a,x,xp,d):
    z = kem_decrypt(s,k,sk,ck,sp,kp,skp,ckp,p,a,x,xp)
    mu = dem_decrypt(z,d)
    return mu

def subsetsumdecrypt(A,v,vp,a,x,xp):
    kappa=q
    kappa2=q
    L=block_matrix(ZZ, \
        [[1, 0, -kappa*a.row(), -kappa2 * x, -kappa2 * xp], \
         [0, t*identity_matrix(m), kappa*A, kappa2 * v.column(), kappa2 * vp.column()], \
         [0, 0, 0, kappa2*q, 0],\
         [0, 0, 0, 0, kappa2*q]])
    L=L.BKZ()

    #index of first non-zero entry in the first column of L
    idx=next((i for i,x in enumerate(L.column(0).list()) if x!=0))
    lcand = vector(ZZ,L[idx][1:m+1]/t) if L[idx][0] == 1 else vector(ZZ,-L[idx][1:m+1]/t)
    return lcand

def test_decrypt(trials=10,pairs=10,debug=true):
    succ=0
    tottime=0.0
    if debug:
        print "Start!!!"
    for npair in range(pairs):
        s,k,sk,ck,sp,kp,skp,ckp,p = newkeygen()
        A,u,v,vp,e,ep = newsamplegen(s,k,sk,ck,sp,kp,skp,ckp,p)
        print "Key pair %d" % (npair)

        succnow=0
        for _ in range(trials):
            mu = randint(0,t-1)
            a,x,xp,d, z,l = pke_encrypt(A,u,v,vp,mu)
            tm=cputime(subprocesses=True)
            lcand = subsetsumdecrypt(A,v,vp,a,x,xp)
            tottime+=float(cputime(tm))
            if debug:
                print a,x,xp,d,z,mu
                print "real   :", l*A, (l*v) %q, (l*vp)%q, (l*u)%t
                print "cracked:", lcand*A, (lcand*v) %q, (lcand*vp)%q, (lcand*u)%t
            if dem_decrypt((lcand*u)%t,d) == mu:
                succnow+=1
            # if z == (lcand*u)%t:
            #    succnow+=1
        succ+=succnow
        print "Key pair %d complete. Success rate: %d/%d." % \
                (npair,succnow,trials)
    print "Successful recoveries: %d/%d (%f)." % \
            (succ,trials*pairs,RR(100*succ/trials/pairs))
    print "Average time: %f seconds." % (tottime/trials/pairs)

# use PRG for reproducibility
set_random_seed(0)

test_decrypt(10,10,true)

# =>
# Successful recoveries: 100/100 (100.000000).
# Average time: 3.395185 seconds.

The original code is available in Cryptanalysis of Compact-LWE by Jonathan Bootle and Mehdi Tibouchi.