Use lazy reduction in ML-KEM matrix-vector products

In the NTT domain, a product of two ML-KEM polynomials consists of 128
products in rings of the form GF(3329)[X]/(X^2 - zeta), each computing
a0*b0 + a1*b1*zeta and a0*b1 + a1*b0. scalar_mult reduced a1*b1 before
multiplying it by zeta, and then reduced both results, for three
Barrett reductions per pair of coefficients. The matrix-vector and
inner product functions then added each product to the running sum
with another conditional subtraction.

These products are only ever summed. Since the inputs are fully
reduced, each term is below 2 * 3329^2, and a sum of up to four terms
fits in 32 bits. Instead, accumulate the unreduced terms in a uint32_t
array and reduce each coefficient once, at the end. A static_assert
checks the bound.

Also, b1*zeta only depends on the right-hand side, which is the same for
every row of a matrix-vector product. Compute it once per vector
element and pass it to the products. When encrypting, the
matrix-vector product and the inner product share the cache.

Both techniques are described for Kyber's matrix-vector product in
"Faster Kyber and Dilithium on the Cortex-M4"
(https://eprint.iacr.org/2022/112), as "better accumulation" and
"asymmetric multiplication". The latter comes from "Neon NTT"
(https://eprint.iacr.org/2021/986).

For one ML-KEM-768 matrix-vector product, this replaces 3,456 Barrett
reductions and 2,304 conditional subtractions with 1,152 Barrett
reductions.

The output is unchanged, as are the self-test known-answer values, and
the code remains constant-time. scalar_zero and vector_zero are no
longer used, so remove them.

Median of 15 runs on an Intel Xeon (Skylake-SP) at 2.0 GHz, in
microseconds:

                 ML-KEM-768               ML-KEM-1024
           Before  After  Speedup    Before  After  Speedup
  keygen     35.1   32.5    1.08x      49.2   43.3    1.14x
  encap      24.4   20.8    1.17x      30.8   24.5    1.26x
  decap      37.0   33.1    1.12x      48.6   41.4    1.17x

Change-Id: Ib8ff5c08d24bf4c8c02218ad270ba448e96fc5f8
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/104068
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>
1 file changed
tree: b1706797df2137efbb964c9f1003f6f41fad0e20
  1. .agents/
  2. .bcr/
  3. .github/
  4. agents/
  5. bench/
  6. cmake/
  7. crypto/
  8. decrepit/
  9. docs/
  10. fuzz/
  11. gen/
  12. include/
  13. infra/
  14. pki/
  15. rust/
  16. ssl/
  17. third_party/
  18. tool/
  19. util/
  20. .bazelignore
  21. .bazelrc
  22. .bazelversion
  23. .clang-format
  24. .clang-format-ignore
  25. .clangd
  26. .gitattributes
  27. .gitignore
  28. API-CONVENTIONS.md
  29. AUTHORS
  30. BREAKING-CHANGES.md
  31. BUILD.bazel
  32. build.json
  33. BUILDING.md
  34. CMakeLists.txt
  35. codereview.settings
  36. CONTRIBUTING.md
  37. FUZZING.md
  38. go.mod
  39. go.sum
  40. INCORPORATING.md
  41. LICENSE
  42. MODULE.bazel
  43. MODULE.bazel.lock
  44. PORTING.md
  45. PRESUBMIT.py
  46. PrivacyInfo.xcprivacy
  47. README.md
  48. SANDBOXING.md
  49. SECURITY.md
  50. STYLE.md
README.md

BoringSSL

BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.

Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.

Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.

BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.

Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.

Project links:

To file a security issue, use the Chromium process and mention in the report this is for BoringSSL. You can ignore the parts of the process that are specific to Chromium/Chrome.

There are other files in this directory which might be helpful: