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

ML-DSA: Implement hint pack functions #184

Open
4 tasks done
marsella opened this issue Nov 13, 2024 · 0 comments · May be fixed by #197
Open
4 tasks done

ML-DSA: Implement hint pack functions #184

marsella opened this issue Nov 13, 2024 · 0 comments · May be fixed by #197
Assignees
Labels
CNSA 2.0 version-update Addresses a new version of an existing spec

Comments

@marsella
Copy link
Contributor

marsella commented Nov 13, 2024

The HintBitPack and HintBitUnpack functions deal with sparse vectors and require tracking where the non-zero terms in a set of polynomials are. This kind of index-tracking functionality can be hard to express in Cryptol.

There's a version in the IPD that uses recursion but doesn't look a lot like the spec. I think it's worth exploring two avenues: try cleaning up the IPD version to see if it can be more closely mapped with some renaming and reordering; or try rewriting from scratch using a different approach (I briefly considered a recursive function that has Index as a type parameter and y as a continually-updated array).

The IPD omitted a malformed input check that was added back in the final draft. We need to make sure this gets added as well.

There are failure modes in HintBitUnpack so at the least, we should modify the existing implementation to return an Option that's None in the case of failures.

  • Explore implementation approaches for HintBitPack; feel free to make a draft PR or post in the comments here with ideas to get feedback.
  • Modify HintBitUnpack to return an option
  • Explore implementation approaches for HintBitUnpack
  • Make a property showing that unpack reverses pack.
@marsella marsella added CNSA 2.0 version-update Addresses a new version of an existing spec labels Nov 13, 2024
@marsella marsella self-assigned this Nov 21, 2024
marsella added a commit that referenced this issue Nov 26, 2024
marsella added a commit that referenced this issue Nov 27, 2024
There is a bug that I haven't identified yet; it's triggered at L202 but
I cannot figure out why.
marsella added a commit that referenced this issue Nov 27, 2024
Changes the type of the index `i` to an integer to avoid overflow when
indexing into the larger array.
@marsella marsella linked a pull request Nov 27, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
CNSA 2.0 version-update Addresses a new version of an existing spec
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant