Errors and strange results in some attacks with LWR instances

[Bbalon-a]

Hi ! I found some issues with the estimator when I deal with a LWR instance with rounding from Q=2^q to P=2^p. The secret is taken uniformly between 0 and Q-1 and the error follows an uniform distribution with standard deviation (std) being a function of Q/P. Some issues pop up for any q and others when the std of those distributions becomes important. 1) For any q Some attacks (rough estimates, primal_hybrid, primal_usvp) fail when n is small (i.e. <32).

from estimator import *
Q = 2**10
X_s = ND.UniformMod(Q)
P=2**6 
X_e = ND.UniformMod(Q/P)
n_list = [10,15,20,30,40,50]

for n in n_list:
    print("\nn = {}\n".format(n))  
    LWR = LWE.Parameters(tag="LWR",n=n,q=Q, Xs=X_s, Xe=X_e)
    print(repr(LWE.estimate.rough(LWR,jobs=10)))
    print(repr(LWE.estimate(LWR,jobs=10)))

2) For higher q a) The rough estimates gives unexpected results

• The security estimates of dual_hybrid exhibit a sawtooth pattern as n increases.
• The security estimates of usvp bomb out unexpectly (could be the same as #94)

from estimator import *
Q = 2**16
X_s = ND.UniformMod(Q)
P=2**6 
X_e = ND.UniformMod(Q/P)
n_list = [32,40,48,56,64,72,80,88,96,104,112,120,128]
for n in n_list:
    print("\nn = {}\n".format(n))    
    LWR = LWE.Parameters(tag="LWR",n=n,q=Q, Xs=X_s, Xe=X_e)
    print(LWE.estimate.rough(LWR,jobs=10))

n	usvp	dual_hybrid
32	11.7	91.1
40	14.9	25.1
48	21.3	97.8
56	27.2	102.1
64	33	43.7
72	38.8	51.7
80	44.7	120
88	inf	127.5
96	inf	135.7
104	inf	144.7
112	inf	105.1
120	inf	/
128	inf	/

b) Primal_bdd does not pass sanity check when the std of both distributons become important

from estimator import *
Q = 2**32
X_s = ND.UniformMod(Q)
P= 2**6
X_e = ND.UniformMod(Q/P)
n_list = [32,64,128,256,512]
for n in n_list:
    print("\nn = {}\n".format(n))    
    LWR = LWE.Parameters(tag="LWR",n=n,q=Q, Xs=X_s, Xe=X_e)
    try:
        print(repr(LWE.primal_bdd(LWR,jobs=10)))
    except Exception as e:
        print(type(e).__name__, "-", e)