How to create new instance for the relation?

[liaoguangyu]

In /demo/kyber1024/data.h, the vectors A1, t, s contains the value of the demo instance, how to partition the vectors so that As+e=t holds? When we generate the a new MLWE instance, the verification process fails.

[liaoguangyu]

the result of polynomial multiplication in the demo is different from that of the navie polymonial multiplication.

[p-steuer]

how to partition the vectors so that As+e=t holds?

Let Rq be the kyber ring, then for the coefficents arrays A1_, t_, s_ from data.h the following holds:

[A1_|Id] * s_ = t_

when A1_ is parsed as a 4x4 matrix over Rq, s_ as a dim 8 column vector over Rq and t_ as a dim 4 column vector over Rq, where the coefficients in a polynomial are parsed from low to high degree., the polynomials in a column vector are parsed from low to high row and the polynomials in a matrix are parsed in row major order.
Id is the 4x4 identity matrix, concatenated to A1_.

So given As+e=t, s_ is to be understood as the concatenation of e and s (i.e., s_[0]=s[0], ..., s_[3]=s[3], s_[4]=e[0] ... s_[7]=e[3]).

the result of polynomial multiplication in the demo is different from that of the navie polymonial multiplication.

Here is the sagemath code to verify that above equation holds for the data in demo.h (and also clarifies the parsing of int coeffs to poly matrices/vectors):

A1=[ ... ] # paste array A1_ from data.h here
s=[ ... ]  # paste array s_ from data.h here
t=[ ... ]  # paste array t_ from data.h here
d=256
q=3329
Rq = QuotientRing(Integers(q)['x'], Integers(q)['x'].ideal(x ^ d+1), 'x')
A1_=matrix(Rq,4,4)
s_=vector(Rq,8)
t_=vector(Rq,4)
for i in range(4):
    for j in range(4):
        A1_[i,j]=Rq(A1[d * (i * 4 + j):d * (i * 4 + j)+d])
for i in range(8):
    s_[i]=Rq(s[i*d:i*d+d])
for i in range(4):
    t_[i]=Rq(t[i*d:i*d+d])
A1_*s_[0:4]+s_[4:8]==t_