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

Bring NTT sections of ML-KEM up to gold standard #147

Open
8 of 10 tasks
marsella opened this issue Oct 3, 2024 · 0 comments
Open
8 of 10 tasks

Bring NTT sections of ML-KEM up to gold standard #147

marsella opened this issue Oct 3, 2024 · 0 comments
Assignees
Labels
CNSA 2.0 improvement Addresses fixes or changes to existing specs

Comments

@marsella
Copy link
Contributor

marsella commented Oct 3, 2024

Right now there is a bunch of stuff related to NTT (Section 4.3) in the main body of ML-KEM. There are naive and fast versions of the NTT algorithm (with a "dispatcher" to hard-code which one to use), as well as 1D and 2D applications. We should try to contain this a little more intentionally.

There are also some places where the NTT-related code doesn't obviously align with the spec.

  • Make an NTT submodule that contains all the NTT stuff -- everything in section 4.3. Maybe also section 4.3.1 -- I'm not sure what will make the most sense.
  • Add types for Rq and Tq instead of using the same Z_q_256 for both. I'm not sure if this should belong in the NTT submodule or the enclosing one.
  • At the "dispatcher", add docs explaining the equivalence of the two versions and note the specific place in the spec that says it's fine to use equivalent algorithms.
  • We need to be able to run NTT over vectors and NTTInv over single elements and vectors. Rename NTT' and NTT to NTT and NTT_Vec, and similarly for NTTInv (related: Bring encoding and compression functions in ML-KEM up to gold standard #144 discusses the naming choice)
  • In the submodule, make all the different instantiations of NTT private. The only public things in the submodule should be NTT, NTT_Vec, NTTInv, NTTInv_Vec, and, if they're included, MultiplyNTTs and the R_q/T_q types.
  • Update the naive version (ParametericNTT) to more obviously match the spec.
    • In the spec, BitRev7 is supposed to operate over 7-bit vectors but it currently operates over 8-bit vectors. Try to align this better with the spec.
    • The use of BitRev7 in ParametricNTT is different from what's in the spec. Fix it or add a comment explaining why they're equivalent.
  • Make sure all the NTT equivalence properties have docstrings
  • Align MultiplyNTTs better with the spec. E.g. the exponent for zeta is not the same as what's in the spec. Fix it or add a comment explaining why they're equivalent.
@marsella marsella added CNSA 2.0 improvement Addresses fixes or changes to existing specs labels Oct 3, 2024
marsella added a commit that referenced this issue Oct 15, 2024
marsella added a commit that referenced this issue Oct 15, 2024
This doesn't replace all uses of `Z_q_256`, but it gets all the easy
ones.
marsella added a commit that referenced this issue Oct 15, 2024
This replaces `'`s with suffixes explictly describing what type of data
each NTT function operates over.
marsella added a commit that referenced this issue Oct 15, 2024
This adds some documentation around the NTT module explaining where the
spec says it's allowed to choose any version of their algorithms that
are the same.
marsella added a commit that referenced this issue Oct 16, 2024
Several properties didn't have correct `repl` commands in the
docstrings.
marsella added a commit that referenced this issue Oct 16, 2024
- Adds docs to BitRev and contains its behavior a bit better
- Adjust spacing, naming, etc in MultiplyNTTs and BaseCaseMultiply
marsella added a commit that referenced this issue Oct 16, 2024
This doesn't make them spec adherent but it simplifies the section a bit.
@marsella marsella self-assigned this Oct 16, 2024
marsella added a commit that referenced this issue Oct 17, 2024
aims to match the spec more closely, as much as that's possible with the
built-in limitations of cryptol.
marsella added a commit that referenced this issue Oct 31, 2024
marsella added a commit that referenced this issue Oct 31, 2024
marsella added a commit that referenced this issue Oct 31, 2024
This doesn't replace all uses of `Z_q_256`, but it gets all the easy
ones.
marsella added a commit that referenced this issue Oct 31, 2024
This replaces `'`s with suffixes explictly describing what type of data
each NTT function operates over.
marsella added a commit that referenced this issue Oct 31, 2024
This adds some documentation around the NTT module explaining where the
spec says it's allowed to choose any version of their algorithms that
are the same.
marsella added a commit that referenced this issue Oct 31, 2024
Several properties didn't have correct `repl` commands in the
docstrings.
marsella added a commit that referenced this issue Oct 31, 2024
- Adds docs to BitRev and contains its behavior a bit better
- Adjust spacing, naming, etc in MultiplyNTTs and BaseCaseMultiply
marsella added a commit that referenced this issue Oct 31, 2024
This doesn't make them spec adherent but it simplifies the section a bit.
marsella added a commit that referenced this issue Oct 31, 2024
aims to match the spec more closely, as much as that's possible with the
built-in limitations of cryptol.
marsella added a commit that referenced this issue Oct 31, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
CNSA 2.0 improvement Addresses fixes or changes to existing specs
Projects
None yet
Development

No branches or pull requests

1 participant