Instantly share code, notes, and snippets.

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

Last active September 22, 2023 09:56
Show Gist options
• Save malb/7c8b86520c675560be62eda98dab2a6f to your computer and use it in GitHub Desktop.
Knowledge K-M-ISIS is false

# 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))

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)
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}$$.