ML-KEM encaps key modulus check optimization #1874
Conversation
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## main #1874 +/- ##
==========================================
- Coverage 78.47% 78.47% -0.01%
==========================================
Files 585 585
Lines 99511 99498 -13
Branches 14249 14242 -7
==========================================
- Hits 78094 78083 -11
Misses 20781 20781
+ Partials 636 634 -2 ☔ View full report in Codecov by Sentry. |
| // FIPS 203. Algorithm 5 ByteEncode_12 | ||
| // Encodes an array of 256 12-bit integers into a byte array. | ||
| // Intuition for the implementation: | ||
| // in: |xxxxxxxxyyyy| |yyyyzzzzzzzz| ... |
There was a problem hiding this comment.
I'm a bit confused how this is the same as the commented-out implementation: I thought that each 16-bit array member contained a 12-bit digit and the top 4 are discarded.
The inner loops of the above implementations which looped over the bits was iterating up to 12, then control moved to the next element, unless I'm misunderstanding.
There was a problem hiding this comment.
each 16-bit array member contained a 12-bit digit and the top 4 are discarded.
that's correct, and that's what we are doing here as well
| // FIPS 203. Algorithm 5 ByteEncode_12 | ||
| // Encodes an array of 256 12-bit integers into a byte array. | ||
| // Intuition for the implementation: | ||
| // in: |xxxxxxxxyyyy| |yyyyzzzzzzzz| ... |
// Intuition for the implementation:
// in: |xxxxxxxx| |yyyyyyyy| |zzzzzzzz| ...
// out: |xxxxxxxxyyyy| |yyyyzzzzzzzz| ...
// We divide the input in triples of elements (3 x 8 bits = 24 bits),
There was a problem hiding this comment.
Nit
Suggested change
// We divide the input in triples of elements (3 x 8 bits = 24 bits),
// We divide the input in triplets of elements (3 x 8 bits = 24 bits),
| // Intuition for the implementation: | ||
| // in: |xxxxxxxx| |yyyyyyyy| |zzzzzzzz| ... | ||
| // out: |xxxxxxxxyyyy| |yyyyzzzzzzzz| ... | ||
| // We divide the input in triples of elements (3 x 8 bits = 24 bits), |
There was a problem hiding this comment.
Nit
| // We divide the input in triples of elements (3 x 8 bits = 24 bits), | |
| // We divide the input in triplets of elements (3 x 8 bits = 24 bits), |
| // that are actually used. We commented out and kept the reference | ||
| // code for posterity. |
There was a problem hiding this comment.
Do we have to? it'll still be in the git history, you can mention that fact here.
Issues:
CryptoAlg-2620
Description of changes:
PR #1868 implemented the encapsulation key modulus check
naively, as specified in FIPS 203 which introduced a significant
performance hit to encapsulation. In this change we optimize
encoding/decoding to/from bytes functions to reduce the performance
regression.
For example, encapsulation performance (ops/s) measured on M1 macbook:
Call-outs:
Point out areas that need special attention or support during the review process. Discuss architecture or design changes.
Testing:
How is this change tested (unit tests, fuzz tests, etc.)? Are there any testing steps to be verified by the reviewer?
By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license and the ISC license.