Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields

summary

The gist

We introduce the new AXU hash function c-decBRWHash, which is parameterised by the positive integer c and is based on Bernstein-Rabin-Winograd (BRW) polynomials <ref:2507.06490#pg2> Choosing c > 1…

In short

The paper introduces c-decBRWHash, a new AXU hash function based on Bernstein-Rabin-Winograd (BRW) polynomials, designed for efficient vector implementation using AVX2 SIMD instructions. It shows that 4-decBRWHash outperforms polyHash for certain message lengths, achieving speedups of 16% to 23% for kilobyte and megabyte files, respectively.

Key concepts

BRW Polynomials
These are a specific class of polynomials used to construct AXU hash functions. A key advantage is that they require about half the number of field multiplications compared to traditional polynomial hashing methods, offering better theoretical efficiency.
c-decBRWHash
This new hash function is parameterized by an integer 'c'. When c=4, it works by splitting the input stream into four parallel streams and computing independent BRW polynomials on each. This allows for simultaneous computation using SIMD instructions.
AVX2 SIMD Implementation
This refers to using specialized processor instructions (AVX2) to perform multiple mathematical operations on data in parallel. The paper uses this technique to evaluate the required BRW polynomials simultaneously, significantly speeding up the hashing process compared to sequential methods.

Terminology used across episodes

This episode discusses

The paper

Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields · Read on arXiv

Indian Statistical Institute

We introduce the new AXU hash function decBRWHash, which is parameterised by the positive integer c and is based on Bernstein-Rabin-Winograd (BRW) polynomials. Choosing c>1 gives a hash function which can be implemented using c-way single instruction multiple data (SIMD) instructions. We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials. Our implementations are over prime order fields, specifically the primes 2 127-1 and 2 130-5. For the prime 2 130-5, for avx2 implementations, compared to the famous Poly1305 hash function, 4-decBRWHash is faster for messages which are a few hundred bytes long and achieves a speed-up of about 16% for message lengths in a few kilobytes range and improves to a speed-up of about 23% for message lengths in a few megabytes range.

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields".

Elias: Here's the gist of the paper. We introduce the new AXU hash function c-decBRWHash, which is parameterised by the positive integer c and is based on Bernstein-Rabin-Winograd (BRW) polynomials <ref:2507.06490#pg2> Choosing c > 1 gives a hash function which can be implemented using c-way single instruction multiple data (SIMD) instructions <ref:2507.06490#pg2>.

Nadia: We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors <ref:2507.06490#pg2>.

Elias: For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials <ref:2507.06490#pg2>.

Nadia: We obtained extensive timing results for all our implementations <ref:2507.06490#pg2>.

Title and authors: Nadia: So we're looking at this paper today, "Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields." It’s about introducing a new AXU hash function called c-decBRWHash, which is parameterized by a positive integer c.

Elias: And the main thing they highlight right away is that choosing c greater than one opens up the door to implementing this using c-way single instruction multiple data instructions, or SIMD instructions.

Priya: So it sounds like they're looking for a way to make these hashing algorithms much faster when you're dealing with large amounts of data, especially in systems that need high throughput.

Nadia: Exactly. They show off hand-optimized assembly implementations of the four-decBRWHash function using avxtwo SIMD instructions on modern Intel processors.

Elias: And they compare this against similar optimized avxtwo implementations of a different AXU hash function called polyHash, which uses usual polynomials.

Priya: I'm curious if the comparison between these two functions is what really matters for practical security applications.

Nadia: It is. They ran extensive timing results and found that for the prime two thousand one hundred thirty minus five the four-decBRWHash function was faster than polyHash for messages that were a few hundred bytes long <ref:2507.06490#pg1,a few hundred bytes long>.

Elias: That’s a specific number to anchor on. And they found a speed-up of about sixteen percent for message lengths in the kilobyte range and up to twenty-three percent for megabyte size messages with avxtwo implementations of four-decBRWHash versus polyHash1305 <ref:2507.06490#pg1,a speed-up of about>.

Priya: Sixteen to twenty-three percent speedups on larger files is pretty significant, especially when you're thinking about hashing things like large documents or data streams.

Nadia: It suggests that this new approach with the BRW polynomials gives a real performance edge over the standard polynomial approach when you use these vector instructions correctly.

Elias: Now, let's talk about the theory behind it. They introduce these BRW polynomials based on a class of polynomials from earlier work, and they point out a theoretical advantage: the number of field multiplications needed for hash functions based on BRW polynomials is about half as many as those required by usual polynomial-based hash functions three (see

fifteen five: for further complexity improvements) <ref:2507.06490#pg2,3 (see 15, 5 for further complexity improvements>.

Priya: Half the multiplications is a big deal theoretically. It means that even before you get into the speed of the actual computation, the structure of the math itself is more efficient.

Nadia: But then they move on to how they actually make it fast in practice. They explain that for c-decBRWHash, when c equals four, they take an input stream and decimate it into four parallel streams of the same length.

Title and authors: Elias: Then they perform independent BRW polynomial computations on each of those streams, and finally combine the outputs of those four streams using usual polynomials.

Priya: So that means they can do all those four BRW computations at the same time because they are independent and run on sequences of the same length.

Nadia: Right. And because they are independent, they can apply an algorithm from a previous study in a vectorized manner to compute all four BRW polynomials simultaneously at tau.

Elias: The paper details how the computation of c-decBRWHash tau requires evaluating Q one through Q c, and evaluations of these Q s require evaluating c BRW polynomials where the inputs to those polynomials are disjoint and the number of message blocks provided as input is the same for all of them.

Priya: So they use SIMD strategy to evaluate all those c BRW polynomials at tau simultaneously. That's the vectorization part coming together.

Nadia: They actually implemented this SIMD version of Algorithm one specifically for the case where c equals four, and Table three shows how many four-way SIMD operations are required for computing polyHash and decBRWHash for l message blocks.

Elias: Looking at Table three, they show that the number of unreduced SIMD multiplications needed for four-decBRWHash is about half of what is required for polyHash <ref:2507.06490#pg1>.

Priya: That links back to the theoretical point they made earlier about the number of field multiplications being reduced by half.

Nadia: They also mention SIMD reductions, noting that for g less than or equal to four, the number of SIMD reductions needed by four-decBRWHash is at most what is required by polyHash <ref:2507.06490#pg1>.

Elias: But for g greater than four, polyHash requires fewer number of SIMD reductions <ref:2507.06490#pg2>.

Priya: So the trade-off seems to be that the structure helps reduce multiplications, and the vectorization helps manage those operations efficiently across multiple streams.

Nadia: There's also a point about parameter choices, which is where it gets a bit more practical. They say there’s a generic disadvantage with using two thousand one hundred twenty-seven minus one compared to two thousand one hundred thirty minus five for the prime orders they test <ref:2507.06490#pg1>.

Elias: That difference comes down to block size n; for the prime order of two thousand one hundred twenty-seven minus one, the block size is one hundred twenty, while for two thousand one hundred thirty-five minus five, it's a larger one at one hundred twenty-eight.

Priya: So because two thousand one hundred twenty-seven minus one requires about sixteen over fifteen times more blocks for a given message length compared to two thousand one hundred thirty minus five the functions based on two thousand one hundred twenty-seven minus one will generally be slower <ref:2507.06490#pg1>.

Title and authors: Nadia: That makes sense. It sounds like they focused their timing results only on the prime order two thousand one hundred thirty-five minus five because it was demonstrably faster for both hash functions when using avxtwo implementations.

Elias: They also mention that the SIMD implementation of the five limb representation for two thousand one hundred thirty-five minus five is very similar to the SIMD implementation for two thousand one hundred twenty-seven minus one.

Priya: But they admit there’s a trade-off in memory usage, because storing four field elements uses five two fifty six bit words, and the penalty from needing those extra instructions for the four limb representation doesn't always cancel out the benefit of needing fewer vector multiplication instructions.

Nadia: It shows that even with hardware acceleration like avxtwo there are still implementation constraints where you have to balance instruction count against data representation.

Elias: So, when we look at the overall performance comparison between four-decBRWHash and polyHash over the prime two thousand one hundred thirty-five minus five, they found that four-decBRWHash is faster for messages which are a few hundred bytes long <ref:2507.06490#pg1,4-decBRWHash is faster for messages which are a few hundred bytes>.

Priya: And for larger messages, it keeps getting better with size. They report a speed-up of about sixteen percent for kilobyte size messages and up to twenty-three percent for megabyte size messages when using avxtwo implementations.

Nadia: That's a very concrete result showing the practical benefit of this method over the standard approach in real-world scenarios with large files.

Elias: And they also found that when the number of blocks is about five hundred or more, there isn't much difference in speed between pre-computing your key powers and computing them on the fly.

Priya: That's a nice piece of practical advice for anyone building these systems; if you can do it once upfront, it might save some time when you’re running things continuously.

Nadia: So to wrap up on this paper, the whole point is that by using BRW polynomials and vectorization with avxtwo instructions, we get a hash function that has fewer multiplications theoretically and is actually faster in practice for larger files when compared to standard polynomial hashing.

Elias: It moves the discussion from just theoretical complexity down to how fast it runs on actual hardware when you use modern instruction sets.

Priya: From my side, it’s interesting because they are testing different prime orders and showing that choosing the right prime order, like two thousand one hundred thirty-five minus five, can really make a noticeable difference in performance.

Nadia: So that's the gist of it for this paper on Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields. We'll keep an eye out for how this vectorization concept gets applied elsewhere.

The paper's summary: Nadia: So to recap, this paper introduces c-decBRWHash, which uses Bernstein Rabin Winograd polynomials parameterized by an integer c, and they’ve shown that choosing a larger c lets you use vector instructions like avxtwo SIMD to compute multiple hash functions at the same time.

Elias: Right. It takes your input stream and splits it into four parallel streams, runs the BRW math on each stream independently, and then combines those results with usual polynomials. The big theoretical win they point to is that you need about half the number of field multiplications compared to using standard polynomial hashing methods.

Priya: So it’s not just a speed boost from the vectorization; there’s a fundamental reduction in the amount of math needed upfront because of how these BRW polynomials are structured.

Nadia: Exactly. But they didn't stop there with just theory, they actually built and tested this using assembly code on modern Intel processors. They compared their four-decBRWHash against a similar function called polyHash, which uses the usual polynomials we’re already familiar with in cryptography.

Elias: And the results were pretty telling. For specific prime orders they tested, like two thousand one hundred thirty-five minus five, the four-decBRWHash was faster for messages that were a few hundred bytes long.

Priya: A few hundred bytes is small data to a hashing algorithm, so what does that mean practically? Is this only useful for massive files?

Nadia: Not necessarily. They found speed-ups of about sixteen percent when hashing kilobyte sized messages and up to twenty-three percent for messages in the megabyte range when using avxtwo. That’s a real performance gain right there.

Elias: They also looked at the trade-offs with different prime numbers, and they found that using two thousand one hundred thirty-five minus five was generally better than two thousand one hundred twenty-seven minus one because it required fewer input blocks for the same message length.

Priya: So choosing the right prime order matters a lot for real-world speed. It’s not just picking any number; you gotta pick the right one to maximize those vectorization benefits.

Nadia: And they also hit on some implementation headaches, like how storing those field elements in memory—using five two fifty six bit words—can sometimes actually make things slower because of the extra instructions needed for that specific representation.

Elias: It shows that even when you have the right algorithm and the right hardware instructions, you still have to balance out how you’re organizing your data in memory to get the best speed.

Priya: So what they showed is that this approach is promising because it offers both a theoretical efficiency gain from the polynomial structure and a practical speedup on modern hardware for larger inputs.

Nadia: Exactly. It moves the discussion past just how complex an algorithm is, to how fast it actually runs when you use modern instruction sets like avxtwo to do things in parallel.

Elias: And that makes me wonder what this means for other areas of cryptography where we might be dealing with similar polynomial structures but can't easily vectorize them right now.

The paper's improvements: Tom: So we’re talking about how they suggest improving this whole approach, moving beyond just what they did in the paper, right?

Nadia: Right. They suggest optimizing the choice of parameters like g in polyHash and t in c-decBRWHash based on how long the message is.

Elias: That makes sense. So if you know your data will be huge, you pick one set of settings that gives you the best speed for that length, instead of using a fixed setting for everything.

Priya: It’s like tuning a machine before you use it; knowing exactly what to dial in based on the job ahead saves time and resources.

Nadia: They also touch on how they can use different ways to store those numbers in memory, like that five limb representation versus others, and they say that sometimes the extra instructions for one way of storing data don't fully cancel out the speed gain from fewer vector multiplications.

Elias: It’s a trade-off between instruction count and data representation again. The paper notes that this means you have to look at the whole system, not just the math itself.

Priya: So it’s not just about finding the fastest multiplication method; it's about making smart choices for everything from memory layout to parameter selection.

Nadia: And they hint at future work where they might explore even more advanced ways to use these vector instructions, maybe looking into how those carry bits are handled in future hardware.

Elias: It sounds like the path forward involves pushing the boundaries of what we can squeeze out of these SIMD units on modern processors.

Priya: I’m interested in seeing if this concept of using different representations for the same math structure shows up in other security or measurement papers soon.

Conclusion: Tom: So we’re wrapping up this look at "Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields." The main idea is that by using these BRW polynomials and avxtwo instructions, you get a hash function with fewer multiplications theoretically and faster performance for large files in practice.

Nadia: Exactly. It’s about taking the complexity down from just theory to something that actually runs fast on modern hardware when you use those vector instructions in parallel.

Elias: I think the most important thing is seeing how a structure with fewer multiplications can translate into a real speedup, like that sixteen to twenty-three percent we saw for megabyte messages.

Priya: From my side, I’m interested because it shows that picking the right prime order, like two thousand one hundred thirty-five minus five versus two thousand one hundred twenty-seven minus one, really matters for how fast the entire process runs.

Nadia: It does. And we saw that there are still implementation details where you have to balance out instruction count against data storage methods to get the best result.

Elias: Yeah, it’s a reminder that even with great math and great hardware support, you still have to worry about the actual way you organize your data in memory.

Priya: So for someone listening who only cares about privacy and measurement, this means that if you're hashing massive amounts of data, this method might give you a practical advantage over older polynomial methods.

Nadia: Definitely. And for anyone looking at how to build faster authentication systems, it gives them a concrete example of how vectorization can help cut down on the computational load significantly.

Elias: It really shows that even established structures like BRW polynomials have room for optimization when you look at vectorization and hardware instructions.

Priya: It’s good to see this kind of work because it gives us a better tool to evaluate the performance trade-offs in real applications, not just on paper.

Nadia: So that's what we had here with "Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields." We’ll keep an eye out for how this vectorization concept gets applied elsewhere in the security and measurement space.

More episodes

← Home