)]}'
{
  "commit": "76bc63d96cbf11f81d89be8d0fe0dff8238fec8f",
  "tree": "b1706797df2137efbb964c9f1003f6f41fad0e20",
  "parents": [
    "dc518c789ab79670ef471c3a5d9b3257680c2565"
  ],
  "author": {
    "name": "Jakub Patałuch",
    "email": "jjpat@google.com",
    "time": "Tue Oct 13 12:37:34 2026 +0000"
  },
  "committer": {
    "name": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Sun Oct 18 12:16:29 2026 -0700"
  },
  "message": "Use lazy reduction in ML-KEM matrix-vector products\n\nIn the NTT domain, a product of two ML-KEM polynomials consists of 128\nproducts in rings of the form GF(3329)[X]/(X^2 - zeta), each computing\na0*b0 + a1*b1*zeta and a0*b1 + a1*b0. scalar_mult reduced a1*b1 before\nmultiplying it by zeta, and then reduced both results, for three\nBarrett reductions per pair of coefficients. The matrix-vector and\ninner product functions then added each product to the running sum\nwith another conditional subtraction.\n\nThese products are only ever summed. Since the inputs are fully\nreduced, each term is below 2 * 3329^2, and a sum of up to four terms\nfits in 32 bits. Instead, accumulate the unreduced terms in a uint32_t\narray and reduce each coefficient once, at the end. A static_assert\nchecks the bound.\n\nAlso, b1*zeta only depends on the right-hand side, which is the same for\nevery row of a matrix-vector product. Compute it once per vector\nelement and pass it to the products. When encrypting, the\nmatrix-vector product and the inner product share the cache.\n\nBoth techniques are described for Kyber\u0027s matrix-vector product in\n\"Faster Kyber and Dilithium on the Cortex-M4\"\n(https://eprint.iacr.org/2022/112), as \"better accumulation\" and\n\"asymmetric multiplication\". The latter comes from \"Neon NTT\"\n(https://eprint.iacr.org/2021/986).\n\nFor one ML-KEM-768 matrix-vector product, this replaces 3,456 Barrett\nreductions and 2,304 conditional subtractions with 1,152 Barrett\nreductions.\n\nThe output is unchanged, as are the self-test known-answer values, and\nthe code remains constant-time. scalar_zero and vector_zero are no\nlonger used, so remove them.\n\nMedian of 15 runs on an Intel Xeon (Skylake-SP) at 2.0 GHz, in\nmicroseconds:\n\n                 ML-KEM-768               ML-KEM-1024\n           Before  After  Speedup    Before  After  Speedup\n  keygen     35.1   32.5    1.08x      49.2   43.3    1.14x\n  encap      24.4   20.8    1.17x      30.8   24.5    1.26x\n  decap      37.0   33.1    1.12x      48.6   41.4    1.17x\n\nChange-Id: Ib8ff5c08d24bf4c8c02218ad270ba448e96fc5f8\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/104068\nReviewed-by: David Benjamin \u003cdavidben@google.com\u003e\nCommit-Queue: David Benjamin \u003cdavidben@google.com\u003e\nPresubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com \u003cboringssl-scoped@luci-project-accounts.iam.gserviceaccount.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "8071a42eba03360fed50446c33d6590691256587",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/mlkem/mlkem.cc.inc",
      "new_id": "ab640efbc0e795167fec73feec1ea12340c623b3",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/mlkem/mlkem.cc.inc"
    }
  ]
}