malb
Kyber reduction model seems to use the wrong constant C in quantum mode
The definition of the constant C uses 2^{0.292 β + o(β)} as the cost of sieving. But in quantum mode, the time complexity of sieving becomes 2^{0.265 β + o(β)} and the constant C should become 1/(1 - 2^{-0.265}) = 5.95. This will result in an error of about 0.1 bit when estimating with quantum mode like the example:
Kyber(nn="list_decoding-ge19")(500, 1024)
I think the constant C might not be needed as a parameter. We can easily compute it by C = 1.0/(1.0 - 2**(-self.NN_AGPS[self.nn]["a"]))
Fwiw: the constant probably shouldn't be 0.265, but rather 0.257 (see https://eprint.iacr.org/2021/570).
Admittedly the difference will be pretty small, but if it's being changed anyway...
On Mon, 13 Mar 2023, 09:07 Martin R. Albrecht, @.***> wrote:
Agreed, can you prepare a pull request?
— Reply to this email directly, view it on GitHub https://github.com/malb/lattice-estimator/issues/71#issuecomment-1465760299, or unsubscribe https://github.com/notifications/unsubscribe-auth/AF7CASBMEUAZHWKHBN67MADW33PWTANCNFSM6AAAAAAVYRYOD4 . You are receiving this because you are subscribed to this thread.Message ID: @.***>
Well, I don't just change the constant C to 5.95. I want to compute it by C = 1.0/(1.0 - 2**(-self.NN_AGPS[self.nn]["a"])). So it can update with the dict NN_AGPS. If a new RAM model with the constant 0.257 appears, we can also easily update C while we update the dict NN_AGPS