Use lazy reduction and parallel ExpandMask in ML-DSA
matrix_mult_montgomery Montgomery-reduced every product and then added
it to the output with a conditional subtraction. The inputs are fully
reduced, so for each coefficient the sum of the L products is at most
7 * (8380417 - 1)^2, well within the range reduce_montgomery accepts.
Instead, sum the 64-bit products and reduce once per coefficient. A
static_assert checks the bound. This speeds up the matrix-vector product
in key generation, signing and verification.
vector_expand_mask sampled the L scalars of y one at a time, each a
separate SHAKE256 computation of about five Keccak permutations, on
every signing attempt. The scalars are independent, so sample them with
the parallel x4 and x2 Keccak implementations, as vector_expand_short
already does for s1 and s2. A shared helper sets up the SHAKE256 input,
so every variant absorbs the same bytes.
The output is unchanged, as are the self-test known-answer values, and
the code remains constant-time.
Median of 15 runs on an Intel Xeon (Skylake-SP) at 2.0 GHz, in
microseconds:
Before After Speedup
ML-DSA-44
keygen 73.1 71.2 1.03x
sign 274.8 224.2 1.23x
verify 58.7 56.9 1.03x
ML-DSA-65
keygen 125.1 120.7 1.04x
sign 424.7 371.3 1.14x
verify 93.1 89.0 1.05x
ML-DSA-87
keygen 187.6 176.7 1.06x
sign 502.7 421.9 1.19x
verify 149.2 139.6 1.07x
Change-Id: I9f50a41319acff3846af7021fc89670cddc83c65
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/104088
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: 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: