malb/knowledge-krisis-is-false.org Secret

## knowledge-krisis-is-false.org

      
    Raw
  

              knowledge-krisis-is-false.org
            
          
    Knowledge K-M-ISIS is false

We will use trapdoor sampling to setup the K-M-ISIS Trapdoor.
def lqf(q, B=2):
    return ceil(log(q/2.,B))

def gadgetf(n, q, B=2):
    lq = lqf(q, B=B)
    g = [B^i for i in range(lq)]
    G = matrix(ZZ, n, n*lq)
    for i in range(n):
        for j in range(lq):
            G[i, i*lq + j] = g[j]
    return G

def decomp(t, B=2):
    n = len(t)
    q = t.base_ring().order()
    lq = lqf(q, B=B)
    x = vector(ZZ, n * lq)
    for i in range(n):
        t_ = t[i].lift_centered()
        if t_ < 0:
            sgn = -1
            t_ = -t_
        else:
            sgn = 1
        for j in range(lq):            
            x[i*lq + j] = sgn* (t_ % B)
            t_ = t_ // B
    return x

def trap_gen(n, q, B=2):
    lq = lqf(q, B=B)
    A_ = random_matrix(GF(q), n, n*lq)
    G = gadgetf(n, q, B=B)
    R = random_matrix(ZZ, n*lq, n*lq, x=-B, y=B)
    A = A_.augment((G - A_*R).change_ring(GF(q)))
    T = block_matrix(ZZ, 2, 2, [identity_matrix(n*lq), -R, matrix(ZZ, n*lq, n*lq), identity_matrix(n*lq)])
    return A, T

def sample_pre(t, A, T, B=2):
    n = A.nrows()
    q = A.base_ring().order()
    lq = lqf(q, B=B)
    x0 = random_vector(ZZ, n*lq, x=-B, y=B+1)
    A0 = A.matrix_from_columns(range(n*lq))
    t -= A0*x0
    
    x1 = decomp(t, B=B)
    x = vector(ZZ, list(x0) + list(x1))
    x = (~T).change_ring(ZZ) * x
    return x

n = 5
q = 7681
A, T = trap_gen(n, q, B=2)
t = random_vector(GF(q), n)
x = sample_pre(t, A, T, B=2)
assert t == A*x
We setup some knowledge K-M-ISIS instance:
n = 5
q = 7681
A, T = trap_gen(n, q, B=2)
k = T.ncols()
D = block_matrix([[identity_matrix(ZZ, 3)], [matrix(ZZ, 2, 3)]])

ru = []
for i in range(k):
    r_ = random_vector(GF(q), 3)
    u_ = sample_pre(D*r_, A, T, B=2)
    ru.append((r_,u_))
A0, A1 = A.matrix_from_rows(range(3)), A.matrix_from_rows(range(3,5))
T1 = matrix([u_ for r_, u_ in ru]).T
We then find some arbitrary, i.e. large, pre-image of zero.
y = A1.T.kernel().basis_matrix()[0].lift_centered()
We use Babai’s rounding to find a short vector:
x = ~T1*y
x = vector([ZZ(x_.round()) for x_ in x.change_ring(RR)])
z = y - T1*x
A*z
(1023, 4430, 2005, 0, 0)

That is, we have found a short vector \(\mathbf{z}\) where we do not immediately know a short linear combination of our \(\mathbf{u}_i\). Instead, \(\mathbf{z}\) is computed as a large affine combination.
1 Variant (1)

Indeed, the same attack applies as is if we replace \(\mathbf{D} = [\mathbf{I} | \mathbf{0}]\) with a random \(\mathbf{D}\). The “trick” is that everything lives in the same subspace so is zero modulo that subspace.
n = 5
q = 7681
A, T = trap_gen(n, q, B=2)
k = T.ncols()
D = random_matrix(GF(q), 5, 3)

ru = []
for i in range(k):
    r_ = random_vector(GF(q), 3)
    u_ = sample_pre(D*r_, A, T, B=2)
    ru.append((r_,u_))
The attack essentially relies on that we hand out a trapdoor for the bottom part of \(\mathbf{A}\) and that we do not care about what goes on in the top part. So we split the matrix and construct our trapdoor.
A0, A1 = A.matrix_from_rows(range(3)), A.matrix_from_rows(range(3,5))
T1 = matrix([u_ for r_, u_ in ru]).T
We then find some arbitrary, i.e. large, pre-image of zero.
y = A.solve_right(D*random_vector(GF(q), 3))
D.solve_right(A*y)
(5159, 1485, 266)

We use Babai’s rounding to find a short vector:
x = ~T1*y.lift_centered()
x = vector([ZZ(x_.round()) for x_ in x.change_ring(RR)])
z = y - T1*x
D.solve_right(A*z)
(275, 1084, 534)

2 Variant (2)

We consider a noisy module check instead:
n = 5
q = 7681
A, T = trap_gen(n, q, B=2)
k = T.ncols() + 2
D = block_matrix([[identity_matrix(ZZ, 3)], [matrix(ZZ, 2, 3)]])

ru = []
for i in range(k):
    r_ = random_vector(GF(q), 3)
    e_ = vector([0, 0, 0, ZZ.random_element(-5, 5), ZZ.random_element(-5, 5)])
    t_ = D*r_ + e_
    u_ = sample_pre(t_, A, T, B=2)
    ru.append((t_,r_,e_, u_))
To break it, we consider an extended version of \(\mathbf{A}\) to roll the noisy part into \(\mathbf{u}\).
AX = block_matrix([[A,matrix(ZZ, 3, 2).stack(-identity_matrix(2))]])
T1 = matrix([list(u_) + list(e_[3:]) for t_, r_, e_, u_ in ru]).T
We now have a trapdoor for the extended version of \(\mathbf{A}\) for the space orthogonal to \(\mathbf{D}\).
for c in (AX*T1).columns():
    D.solve_right(c)
We find an arbitrary solution:
y = AX.solve_right(D*random_vector(GF(q), 3))
D.solve_right(AX*y)
(5314, 277, 6181)

We use Babai’s rounding to find a short vector:
x = ~T1*y.lift_centered()
x = vector([ZZ(x_.round()) for x_ in x.change_ring(RR)])
z = y - T1*x
t = A*z[:-2]
t.lift_centered()
(-2053, 736, 2366, -10, 20)

Note that \(\mathbf{t}\) has short entries in the last two components as required and
t[3] = 0; t[4]=0
D.solve_right(t)
(5628, 736, 2366)

otherwise lives in the space spanned by \(\mathbf{D}\).
3 References