polyval: implement optimizations from eprint 2025/2171

[tarcieri]

The paper is called: "Effcient GHASH and POLYVAL Implementation Using Polynomial Multiplication: Optimized 64-bit Decomposition with Bit-Reversal Elimination"

https://eprint.iacr.org/2025/2171

It's principally about a different algebraic structure for GHASH that eliminates bit reversals, which isn't applicable to POLYVAL since those bit reversals don't exist (rather we implement GHASH in terms of POLYVAL and do one reversal up-front followed by multiply-by-x, and a final reversal for the result, which is also how this paper describes implementing GHASH).

However, in §3.3 it describes an alternative approach to multi-block message processing for GHASH. It's all framed around the PowerPC vpmsumd instruction and doesn't discuss specific other CPUs, however the instruction appears to be the PowerPC equivalent to CLMUL/PMULL, multiplying two 128-bit SIMD inputs and producing a 128-bit carryless product.

§3.3.2 in particular describes an approach to processing a message block into two intermediate values R and F which can be computed using only two vpmsumd invocations:

Implementation advantage: The values R and F can be computed using exactly two vpmsumd instructions (or equivalent on other architectures). One register holds the message block (M0, M1), and two invariant registers hold (H1, D1) and (H0, D0) respectively. This minimizes instruction count and register pressure.

If I'm reading this correctly, it seems to entirely eliminate the Montgomery reduction from the multi-block hot loop, performing a final reduction at the end, whereas our current powers-of-H eliminates intermediate reductions for each block, but still reduces after it's exhausted its set of powers-of-H (to be clear, the paper still uses powers-of-H, just without that intermediate reduction). As the quoted text notes, this reduces the number of 128-bit carryless multiplies from 3 to 2, in addition to eliminating the intermediate reduction (which itself performs two carryless multiplies)

§7.2 is called "Applying the R/F Algorithm to POLYVAL":

The paper further notes that while this optimization is useful for CPUs with carryless multiplication intrinsics, it shouldn't be applied to software implementations:

To quote the bit at the end: "The R/F algorithm provides a unified approach for both GHASH and POLYVAL on platforms with hardware carry-less multiplication, achieving approximately 1.7× speedup over traditional Karatsuba implementations."

[tarcieri]

The paper notes there is in fact already a Rust implementation of this technique available, which is Apache 2.0+MIT licensed (and whose polyval implementation already seems to use some of our code, heh):

https://github.com/seceq/hpcrypt/blob/master/hpcrypt-mac/src/intrinsics/avx2/polyval.rs
https://github.com/seceq/hpcrypt/blob/master/hpcrypt-mac/src/intrinsics/neon/polyval.rs

We can probably adapt this with credit, which would be nice versus implementing it from scratch because we're trying to get releases out soon.

The R/F algorithm optimization operates over 4-block inputs. It still exploits a powers-of-H-style optimization, but there's no longer any benefit to increasing it or having a generic type whatsoever (the R/F algorithm completely eliminates the Montgomery reduction at the end of a parallel set of blocks), which means if we implement this we can get rid of the Polyval/PolyvalGeneric split and generic parameter entirely.

[tarcieri]

#294 adapts the above implementation, but I was a little surprised to discover per the benchmarks that on my M1 Max using the PMULL backend, while it seems faster for short messages it seems slower for longer ones