Add inverse NTTs for Kyber & Dilithium

slothy-optimizer / slothy

Assembly super-optimization via constraint solving

https://slothy-optimizer.github.io/slothy/

Other

165 stars 10 forks source link

Add inverse NTTs for Kyber & Dilithium #37

Closed dop-amin closed 6 months ago

dop-amin commented 7 months ago

This PR introduces inverse NTTs for Kyber and Dilithium. The type of transposition and reduction is supposed to match the code from PQClean [1,2].

TODO:

[x] Add optimized Dilithium invNTTs
[ ] ~~Simplify syntax as in #36~~ (do this separately, we want to re-run every example for this)
[ ] ~~Optional: Add intt_kyber_1234_567~~ (from experience, these variants perform not as well as the ones that merge more layers in the second merge)

[1] https://github.com/PQClean/PQClean/tree/8e221ae797b229858a0b0d784577a8cb149d5789/crypto_sign/dilithium3/aarch64 [2] https://github.com/PQClean/PQClean/tree/8e221ae797b229858a0b0d784577a8cb149d5789/crypto_kem/kyber768/aarch64

hanno-becker commented 7 months ago

@dop-amin I cancelled the CI which was spinning indefinitely on the example dry run.

hanno-becker commented 7 months ago

@dop-amin Are you going to investigate the CI failure or do you need help?

hanno-becker commented 7 months ago

@dop-amin Is there [going to be] a sibling PR to PQAX as well adding tests for the inverse NTT?

dop-amin commented 7 months ago

@dop-amin Are you going to investigate the CI failure or do you need help?

Hi Hanno, I think the CI just times out because it takes too long to go through all the examples. Especially the ones using heuristics seem to take long because it involves so many individual calls to the solver. Do you have a suggestion on how to go about this? We could disable the CI for examples using heuristics.

dop-amin commented 7 months ago

@dop-amin Is there [going to be] a sibling PR to PQAX as well adding tests for the inverse NTT?

Yes, I've been planning to submit it for a couple of days but now I finally did so. Thanks for reminding me.

hanno-becker commented 7 months ago

Hi Hanno, I think the CI just times out because it takes too long to go through all the examples. Especially the ones using heuristics seem to take long because it involves so many individual calls to the solver. Do you have a suggestion on how to go about this? We could disable the CI for examples using heuristics.

I am surprised by this because the dry run sets functional_only=True, allow_renaming=False and allow_reordering=False if I remember correctly -- this should not take long. Can you double-check that your scripts in example.py do not overwrite this?

dop-amin commented 6 months ago

LGTM, @dop-amin -- thank you very much for this work.

Great, thanks for your feedback in the process!