Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LWE params n=2^12, q=2^790 outputs 1179 bit security (uSVP) #68

Open
Janmajayamall opened this issue Jan 24, 2023 · 1 comment
Open
Labels
bug Something isn't working

Comments

@Janmajayamall
Copy link

Running: LWE.primal_usvp(LWE.Parameters(n=2^11, q=2^790, Xs=ND.DiscreteGaussian(2.0), Xe=ND.DiscreteGaussian(2.0))) outputs:
rop: ≈2^44.2, red: ≈2^44.2, δ: 1.012950, β: 40, d: 2166, tag: usvp
This matches my expectations.

However running: LWE.primal_usvp(LWE.Parameters(n=2^12, q=2^790, Xs=ND.DiscreteGaussian(2.0), Xe=ND.DiscreteGaussian(2.0)))
outputs:
rop: ≈2^1179.1, red: ≈2^1179.1, δ: 1.000667, β: 4112, d: 4113, tag: usvp

Should I expect sudden increase in security? Or there's something wrong with the calculation.

@bencrts
Copy link
Collaborator

bencrts commented Aug 22, 2023

This is a bug, I'd expect a reasonable value of q for this parameter set to be roughly in the same range as those seen in the tables of this document: http://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf (e.g. q ~ 2^100 for n = 2^12 to achieve 128-bits of security). Increasing q to such a large value (e.g. 2^790) would reduce security significantly. This can be confirmed by checking the other estimates:

sage: params = LWE.Parameters(n=2^12, q=2^790, Xs=ND.DiscreteGaussian(2.0), Xe=ND.DiscreteGaussian(2.0))
sage: LWE.dual_hybrid(params)
rop: ≈2^47.8, mem: ≈2^29.1, m: ≈2^13.2, β: 40, d: 13197, ↻: 1, ζ: 4, tag: dual_hybrid
sage: LWE.primal_bdd(params)
rop: ≈2^45.3, red: ≈2^45.3, svp: ≈2^30.8, β: 40, η: 33, d: 4610, tag: bdd

@bencrts bencrts added the bug Something isn't working label Aug 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants