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>
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: