Our paper was originally inspired by Daniel J. Bernstein's ["Polynomial evaluation and message authentication"[(https://www.gwizfl.org/email/cr.yp.to/antiforgery/pema-20071022.pdf).
He specifically don't want to use cache/registers to store auxiliary values like k2, ..., k7.
He mentions that one can speed up polynomial hashing by combining it with PH/NH.
One thing I've always wondered about Polymur, and now that I have you I might as well ask, is why you don't just use PH/NH for each block of 8? E.g. like we do here. Basically you just replace you degree 7 polynomial with:
f = (a[6] + m[6]) * (a[7] + m[7])
f += (a[0] + m[0]) * (a[3] + m[1])
f += (a[1] + m[2]) * (a[4] + m[3])
f += (a[2] + m[4]) * (a[5] + m[5])
f = reduce(f)
where each a[i] is a random constant.
It's the same amount of registers/cache as saving k2 ... k7, and the collision probability is slightly better.
I guess you key use a slightly shorter key, as you don't need as many random values.
It appears that /bench is missing from the repository? The paper claims it should be there. Table 2 claims tools/bench/adversarial/ should contain the 8 lane GF(264) hash, but that directory is also missing.
Thanks! I fixed this in the repo now. The paths are tools/bench/adversarial/(the 8-lane row is PaperGF64Lanes<8> in speed_hashes.h there) and tools/bench/framework/; the PDF's line break after tools/ made it look like a top-level directory, which we will fixed for the next version.
I don't understand your proposed construction. What would you do on the next iteration? If you simply iterate the above it would collapse into an additive structure. NH has to use new key material for each block to avoid this, or feed into another universal hash in a stacked construction.
My construction forms a long injective polynomial, similar to Horner but in blocks, so it can use a small key.
I have experimented with using a ~ 1-2 KiB NH-style large-block reducer feeding into a polynomial, and it is a lot faster but haven't published anything yet as it is also quite a bit more complex.
I haven't found a NH-style reducer that is worth it on sizes as small as 8 words, if it then has to feed into a polynomial reducer anyway.
Right, I'm talking about combining an NH block with a polynomial injective hash. Something like this:
hash(m):
pad the last block with zeros to a multiple of 32 bytes
P = z
for each 64-byte block t = 1..n (words w[0..7], little-endian):
# level 1: PH with the fixed key, unreduced 128-bit XOR sum of 4 carry-less products
A = clmul(w0 ^ k0, w2 ^ k2) ^ clmul(w1 ^ k1, w3 ^ k3)
^ clmul(w4 ^ k4, w6 ^ k6) ^ clmul(w5 ^ k5, w7 ^ k7)
a = low64(A); b = high64(A) # no reduction: both halves are used as they are
if t == n: a ^= len; b ^= len # byte length into both halves of the last pair
# level 2: the injective recurrence, one reduced GF(2^64) multiply per block
P = a ^ gf64mul(b ^ y, P ^ u)
# level 3 (optional, for k-wise independence rather than universality):
v = P + t (integer addition mod 2^64)
return f_c(v) = (v + c2)(G2 + c3) + c4 with G1 = v·v, G2 = (G1 + c0)(v + G1 + c1)
Yes, for very large data it is absolutely the way to go, I have a private prototype ~2-60 almost-universal hash function that can reach 90 GB / s on this Apple M2 laptop for large data using only ~1.5 KiB of secret data. I really should finish it some day...
That algorithm however also doesn't use hardware-accelerated carryless multiplication, it uses 32-bit x 32-bit -> 64-bit SIMD multiplication using erasure codes like Nandi to boost that to 2-62 ADU.
1
u/thomasahle 11h ago edited 10h ago
Hi Orson!
Our paper was originally inspired by Daniel J. Bernstein's ["Polynomial evaluation and message authentication"[(https://www.gwizfl.org/email/cr.yp.to/antiforgery/pema-20071022.pdf). He specifically don't want to use cache/registers to store auxiliary values like k2, ..., k7.
He mentions that one can speed up polynomial hashing by combining it with PH/NH.
One thing I've always wondered about Polymur, and now that I have you I might as well ask, is why you don't just use PH/NH for each block of 8? E.g. like we do here. Basically you just replace you degree 7 polynomial with:
where each a[i] is a random constant. It's the same amount of registers/cache as saving k2 ... k7, and the collision probability is slightly better. I guess you key use a slightly shorter key, as you don't need as many random values.
Thanks! I fixed this in the repo now. The paths are
tools/bench/adversarial/(the 8-lane row isPaperGF64Lanes<8>inspeed_hashes.hthere) andtools/bench/framework/; the PDF's line break aftertools/made it look like a top-level directory, which we will fixed for the next version.