switch to ternary search for zeta

[TabOg]

I've been seeing some issues with local minima in the zeta search: I was looking at the parameters from this paper, and saw (excuse formatting):

parameters = LWE.Parameters(n=2**17, q = 2**3104, Xs=ND.SparseTernary(p=96, m=96, n=2 ** 17), Xe=ND.DiscreteGaussian(3.19), m=oo)
LWE.primal_hybrid(parameters, babai=False, mitm=False)
>> rop: ≈2^141.4, red: ≈2^141.3, svp: ≈2^136.1, β: 350, η: 2, ζ: ≈2^12.9 ...
LWE.primal_hybrid(parameters, babai=False, mitm=True)
>> rop: ≈2^152.3, red: ≈2^152.2, svp: ≈2^148.1, β: 248, η: 32, ζ: ≈2^15.0 ...

i.e., switching MITM on increases the complexity, which I don't think can ever be true.

I tracked the issue down to there being local minima in zeta, and the binary search is just heading for the wrong one. I experimented a bit with neighborhoods, but didn't have much success, partly because I don't have a great sense for what the curve with zeta looks like for these massive parameters. Additionally, these two zeta are 2^14.5 apart.

Instead I implemented a different hot fix, switching to a ternary search for this loop only. This isn't an ideal fix, as

1. It's slower: asymptotically 15% slower (2log_3/2 (x) vs 3log_2(x)): in practice, maybe 25%. This may be because of my implementation of course
2. Sometimes it finds worse minima than binary search: in particular for schemes.Kyber512.updated(Xs=ND.SparseTernary(16)) in the examples, it finds an attack that is maybe 5 bits more complex than current binary search.

I tried to avoid both of these by only using the ternary search when n >= 2 ** 15, since 1. it's already slow then 2. I didn't see any parameters in this range where the ternary search finds a worse attack

Now with the parameters above I find

LWE.primal_hybrid(parameters, babai=False, mitm=True)
>> rop: ≈2^134.9, red: ≈2^134.6, svp: ≈2^132.2, β: 322, η: 33, ζ: ≈2^13.8 ...

i.e. about 17 bits better.

Let me know what you think

[malb]

I think slower is fine, but that it might output worse results is a bit worrying, no? Not quite sure how to handle this.

[TabOg]

Yeah agree and also unsure.

Maybe I'll try a different approach instead which keeps the gradient descent checking, but looks at like [x - 10, x + 10] (or similar) and see how that looks

[TabOg]

Oh I think I'm talking about what's implemented as neighborhood()! I had a go at setting a few values for the precision parameter, and still couldn't get attacks as good as the ternary search, and sometimes worse than the binary search. Overall I think this needs a bit more investigation unfortunately, PR is premature