Proposal: Integrate new SHA3 and SHAKE implementations using AVX512VL extensions

[mdcornu]

Description

We (@tkanteck and I) would like to propose adding new low-level implementations of the SHA3 and SHAKE algorithms to the liboqs library, utilizing AVX512VL extensions. These implementations aim to leverage AVX512 extensions to achieve up to 50% performance improvement compared to the current AVX2 implementation.

Integration Plan

Implementation:

• Add two implementations: a single buffer (serial) implementation and a multi-buffer (times 4) implementation.
• These implementations will use AVX512VL extensions operating on 256-bit registers for a broader range of compatibility (current AVX512 systems and AVX10 in the future)
• Add a compile-time option to build these implementations based on the flag OQS_USE_SHA3_AVX512VL.
• If built, but AVX512 extensions are not available at runtime, fall back to XKCP implementation.
• The implementations will be written in GAS (GNU Assembler) to match the existing assembly code.
• File Structure:
  • Add the low-level implementations to a new directory: liboqs/src/common/sha3/avx512vl_sha3_low.
  • Add callback implementations to new file: liboqs/src/common/sha3/avx512vl_sha3.c

Initial Testing Results

Initial testing of the single buffer implementation shows a 35-50% improvement in performance depending on buffer size compared to the existing AVX2 implementation.

Request for Feedback

We would appreciate feedback on the following:

• The overall idea and its relevance to the liboqs library
• Any potential issues or concerns with the implementation, especially regarding integration and maintenance
• Suggestions on the directory or file naming and structure
• Any additional tests or documentation that might be necessary

Thank you for considering our proposal. We look forward to your feedback!

[beldmit]

Would you mind also submitting a patch to OpenSSL?

[tkanteck]

Thanks for the suggestion! Right now, we are focused on the liboqs patch. Once that's done, we'll look into submitting it to OpenSSL.

[baentsch]

You are aware that liboqs can be built using OpenSSL (incl. SHA3), thus allowing you to kill two birds with one stone ? But of course, liboqs can also be built without it, so you decide what to prioritize, @tkanteck .

To answer your question: Your proposal looks good to me and the PR would be very welcome, indeed. We'd of course would be glad if you were able to either regularly keep contributing to OQS and/or document things so clearly that the core team will be able to maintain this going forward. Your file structure proposal also looks sound. Looking forward to the PR!

[tkanteck]

Thanks a lot, @baentsch, for your insights and quick response. We've got some coding ahead of us now! 😊

[dstebila]

Thanks Marcel for the proposal. Yes, this plan looks good from the OQS front. It sounds like a valuable contribution to our project and would also be valuable to others, such as OpenSSL.

[mdcornu]

Excellent, thanks for the feedback. We'll start working on this and will reach out again when we're ready to submit for review.