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: Add bit packing functions #183

Open
7 tasks
marsella opened this issue Nov 13, 2024 · 0 comments
Open
7 tasks

ML-DSA: Add bit packing functions #183

marsella opened this issue Nov 13, 2024 · 0 comments

Comments

@marsella
Copy link
Contributor

marsella commented Nov 13, 2024

There are 4 functions for packing and unpacking between byte strings and elements in R that fall into a restricted range.

In all of them, the parameters a and b I think can be encoded as types -- I looked through and they're all fully defined in terms of constants and parameters, and the parameters can easily be encoded as types. For the non-simple functions, the polynomial's coefficients are supposed to be in the range [-a, b]; we can't represent a negative number using a type but since a itself is passed as the positive value and we don't actually do any checking in the functions, I think it's ok.

Most of the functionality already exists in the IPD version; we should be able to pull much of it in. A few changes I anticipate:

  • In SimpleBitPack, the IPD version uses b as a parameter, but it actually represents bitlen b. I think we should try to match the spec more exactly -- either by calling that parameter bitlen_b or passing b and using width b inline. I suspect this pattern is true across all the functions, and we should be consistent whatever we choose.
  • BitPack and BitUnpack use the product ab as a type parameter. I think we should take a and b separately.
  • The inline docs seem to copy the line of code from the spec. I prefer the style where inline comments have the line number (Step 2.) and any extra notes that might be helpful for someone trying to compare the two.

These are followed by the HintPack and HintUnpack functions, but I think those will be harder to express in Cryptol so I am punting them to a separate issue & PR.

  • Define and document SimpleBitPack
  • Define and document SimpleBitUnpack
  • Define a property demonstrating that the simple functions are inverses. In the docstrings, try to use at least one parameter setting that's used in the actual algorithm.
  • Define and document BitPack
  • Define and document BitUnpack
  • Define a property showing that BitUnpack is the inverse of BitPack. Maybe check that all the coefficients are in the correct range, too (unless that's given by the choice of input). Add docstrings with valid parameter choices.
  • Make sure the unpack docs have warnings about bad inputs producing malformed outputs, and the need to trust the provenance of the input.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant