Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields
Listen
Radio episode about this paper
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.
Indian Statistical Institute
cs.CR
Submitted: 2025-07-09
Updated: 2026-11-15
Code: https://github.com/kn-cs/dec-BRWHashhttps:
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
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…
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
Summary
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. p. 0 in, palash@isical. in
October 2, 2025
Abstract
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. in
October 2, 2025
Abstract
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. Choosing c > 1
gives a hash function which can be implemented using c-way single instruction multiple data
(SIMD) instructions. 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. 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. To the best of our knowledge, there is no previous
hand optimised avx2 assembly language implementation of Poly1305 which systematically considers
all feasible values of the implementation parameters. We obtained extensive timing results for all our implementations. Of more interest in the present context is the comparison between the hash functions 4-decBRWHash
and polyHash. The timings results for the prime 2130 − 5 show that for avx2 implementations,
4-decBRWHash is faster than polyHash for messages which are a few hundred bytes long, and
achieves a speed-up of about 16% (for kilobyte size messages) to 23% (for megabyte size messages). In
view of this observation, in this work we present only the timing results for the prime 2130 − 5. For
the case of polyHash1305, the timing results show that for files which are longer than a few hundred
bytes, the avx2 implementation is faster than the previously reported sequential implementation [5]. For
the case of polyHash1305, the timing results show that for files which are longer than a few hundred
bytes, the avx2 implementation is faster than the previously reported sequential implementation [5]. Of more interest in the present context is the comparison between the hash functions 4-decBRWHash
and polyHash. Of more interest in the present context is the comparison between the hash functions 4-decBRWHash
and polyHash. The timings results for the prime 2130 − 5 show that for avx2 implementations,
4-decBRWHash is faster than polyHash for messages which are a few hundred bytes long, and
achieves a speed-up of about 16% (for kilobyte size messages) to 23% (for megabyte size messages).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Theoretical Foundation of BRW Polynomials
The class of polynomials introduced in [3] to construct AXU hash functions, and later these polynomials were named the BRW polynomials <ref:2507.06490#pg2>. An important theoretical advantage of hash functions based on BRW polynomials is that the number of field multiplications required by such hash functions is about half the number of field multiplications required by hash functions based on usual polynomials [3] (see [15, 5] for further complexity improvements) <ref:2507. p. 1 A class of polynomials was introduced in [3] to construct AXU hash functions, and later these
polynomials were named the BRW polynomials [23]. An important theoretical advantage of hash
functions based on BRW polynomials is that the number of field multiplications required by such
hash functions is about half the number of field multiplications required by hash functions based
on usual polynomials [3] (see [15, 5] for further complexity improvements). This parallelism, however, does not
permit vector computation. The main theoretical contribution of the present work is to present a new AXU hash function
based on BRW polynomials which permits an efficient vector implementation. The main theoretical contribution of the present work is to present a new AXU hash function
based on BRW polynomials which permits an efficient vector implementation. We define the hash
function c-decBRWHash which is parameterised by the positive integer c. We define the hash
function c-decBRWHash which is parameterised by the positive integer c. Suppose c = 4, which
is the case that we implement. Suppose c = 4, which
is the case that we implement. The basic idea is to decimate the input stream into four parallel
streams of the same length and perform independent BRW polynomial computation on each of the
streams. The basic idea is to decimate the input stream into four parallel
streams of the same length and perform independent BRW polynomial computation on each of the
streams. Finally the outputs of the four streams are combined using usual polynomials. Finally the outputs of the four streams are combined using usual polynomials. Since the
four BRW computations are independent and are on the sequences of the same length, it is possible
to apply the algorithm from [5] in a vectorised manner to perform simultaneous computations
of the four BRW polynomials.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Vectorized Implementation Details
The computation of c-decBRWHashτ (X) requires the evaluation of Q1(τ), Q2(τ),..., Qc(τ) <ref:2507. p. 0 Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential
∗Corresponding author. 1
arXiv:2507. The basic idea is to decimate the input stream into four parallel
streams of the same length and perform independent BRW polynomial computation on each of the
streams. Finally the outputs of the four streams are combined using usual polynomials. , Ml) can be evaluated using l − 1 multiplications
and same number of additions. For the BRW polynomials the following was proved in [3]. in
October 2, 2025
Abstract
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. Choosing c > 1
gives a hash function which can be implemented using c-way single instruction multiple data
(SIMD) instructions. Computed sequentially, both
BRWHash and c-BRWHash have similar efficiencies for message which are longer than a few blocks
(for short messages BRWHash will be faster than c-BRWHash). The main advantage of c-BRWHash
is that can be implemented using SIMD operations, as we describe later.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Comparison with PolyHash
The SIMD operation counts for polyHash and 4-decBRWHash are shown in Table 3 <ref:2507.06490#pg2>. The number of unreduced SIMD multiplications required for 4-decBRWHash is about half of what is required for polyHash <ref:2507. p. 1 A class of polynomials was introduced in [3] to construct AXU hash functions, and later these
polynomials were named the BRW polynomials [23]. An important theoretical advantage of hash
functions based on BRW polynomials is that the number of field multiplications required by such
hash functions is about half the number of field multiplications required by hash functions based
on usual polynomials [3] (see [15, 5] for further complexity improvements). See Table 2 which
compares the operation counts and storage requirements for polyHash and c-BRWHash. Compared
to BRWHash, for a small value of c > 1, the hash function c-BRWHash requires a few extra
unreduced multiplications and reductions, and a little less storage. Of more interest in the present context is the comparison between the hash functions 4-decBRWHash
and polyHash. The timings results for the prime 2130 − 5 show that for avx2 implementations,
4-decBRWHash is faster than polyHash for messages which are a few hundred bytes long, and
achieves a speed-up of about 16% (for kilobyte size messages) to 23% (for megabyte size messages).Where the paper says it
Where the paper says it
Where the paper says it
Efficiency Trade-Off Between Primes
There is a generic disadvantage of 2127 −1 in comparison to 2130 − 5 <ref:2507.06490#pg2>. From Table 1, the block size n is 120 for 2127 − 1 and 128 for 2130 − 5 <ref:2507. p. 4 p m n k µ
2
127 − 1 127 120 126 126
2
130 − 5 130 128 128 128
Table 1: The parameters m, n, k and µ for the primes 2127 − 1 and 2130 − 5. [5, 15] For τ ∈ F and l ≥ 3, computing BRW(τ ; M1, . Let α ∈ Z2
µ , and P(x) and P
′
(x) be distinct polynomials in Fp[x]
satisfying P(0) = P
′
(0) = 0. The number of distinct τ ∈ Fp such that
((P(τ ) mod p) mod 2µ
) − ((P
′
(τ ) mod p) mod 2µ
) ≡ α (mod 2µ
) (6)
is at most 2
m−µ+1 times the degree of the polynomial P(x) − P
′
(x). This feature makes
BRW polynomials an attractive option for constructing AXU hash function. An extensive study of
both BRW polynomials based hash functions (named BRWHash) and usual polynomial based hash
functions (named polyHash) for the primes 2127−1 and 2130−5 was carried out in [5] (see [19] for an
update on [5]).Where the paper says it
Where the paper says it
Where the paper says it
Implementation Constraints and Trade-offs
The SIMD implementation of the 5-limb representation for 2130 − 5 is also very similar to the SIMD implementation of the 5-limb representation for 2127 − 1 <ref:2507.06490#pg2>. Four field elements are stored in 5 256-bit words as shown in Figure 1 and multiplication is done using avx2 instructions <ref:2507.06490#pg2>. The penalty due to the additional instructions required for the 4-limb representation more than cancels the benefit of requiring a less number of vpmuludq instructions <ref:2507. p. 0 These instructions permit implementation of vectorised algorithms. In a vectorised algorithm, at every step a single instruction is applied to a number of data items.Where the paper says it
Conclusion on Performance
For avx2 implementations with key powers computed on-the-fly, 4-decBRWHash1305 is faster than polyHash1305 for messages of lengths 256 bytes or more, achieves a speed-up of about 16% for messages which are a few kilobytes long to 23% for message lengths in the megabyte range <ref:2507.06490#pg2>.
Timing Results Summary
The timing results show that the avx2 implementation of polyHash1305 with g = 4 is a faster option than 1 ≤ g. For avx2 implementation of 4-decBRWHash1305, in general t = 5 is a faster option than 2 ≤ t. p. 2 In a typical file system, text
files are usually about a few kilobytes long, while media files such as high resolution pictures, audio
and video files, are a few megabytes long (see [14]). Compared to Poly1305, the new hash function
4-decBRWHash1305 provides a faster option for authentication, or authenticated encryption of such
files.Where the paper says it
Final Performance Comparison
When the number of blocks is about 500 or more, there is not much difference in the speeds of computations between when the key powers are pre-computed and when the key powers are computed on-the-fly <ref:2507.06490#pg2>. For messages having 32768 blocks, the speed-up of 4-decBRWHash1305 over polyHash1305 is about 23% <ref:2507. p. 0 Our implementations are over
prime order fields, specifically the primes 2127 − 1 and 2130 − 5. For the prime 2130 − 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.Where the paper says it
References
[1] Daniel J. Bernstein. Floating-point arithmetic and message authentication, 2004 <ref:2507. p. 5 they are set to 0. In [2] the clamping
of key bits helped in efficient floating point implementation. they are set to 0. In [2] the clamping
of key bits helped in efficient floating point implementation. Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential
∗Corresponding author. 1
arXiv:2507. Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential
∗Corresponding author. 1
arXiv:2507. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. For the prime 2130 − 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. Keywords: almost XOR universal, BRW polynomials, SIMD, assembly
implementation, avx2. For the prime 2130 − 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. Keywords: almost XOR universal, BRW polynomials, SIMD, assembly
implementation, avx2. In particular, the hash
function polyHash is based on the idea behind the design of the hash function Poly1305. The key
space and digest space for both the families polyHash and BRWHash are {0, 1}
k
; τ denotes the k-bit
5 In particular, the hash
function polyHash is based on the idea behind the design of the hash function Poly1305. The key
space and digest space for both the families polyHash and BRWHash are {0, 1}
k
; τ denotes the k-bit
5 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. BRW
polynomials were proposed by Bernstein [3] based on earlier work by Rabin and Winograd [22]. Implementations of BRW polynomials in both software and hardware over binary extension fields
were reported in [10, 11, 9, 15]. BRW
polynomials were proposed by Bernstein [3] based on earlier work by Rabin and Winograd [22]. Implementations of BRW polynomials in both software and hardware over binary extension fields
were reported in [10, 11, 9, 15]. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Polynomial hash functions were proposed independently in three papers [13, 27, 7]. The prime
2
127−1 for use in polynomial hashing was first proposed in [27], and was later used in [1, 17, 5]. Polynomial hash functions were proposed independently in three papers [13, 27, 7]. The prime
2
127−1 for use in polynomial hashing was first proposed in [27], and was later used in [1, 17, 5]. The hash function c-decBRWHash is a generalisation of BRWHash in the sense
that for c = 1, c-decBRWHash becomes exactly BRWHash. While the idea behind the construction
of c-decBRWHash is simple, there is a subtlety in the choice of key used for combining the outputs of
the four streams. The hash function c-decBRWHash is a generalisation of BRWHash in the sense
that for c = 1, c-decBRWHash becomes exactly BRWHash. While the idea behind the construction
of c-decBRWHash is simple, there is a subtlety in the choice of key used for combining the outputs of
the four streams. In
view of this observation, in this work we present only the timing results for the prime 2130 − 5. For
the case of polyHash1305, the timing results show that for files which are longer than a few hundred
bytes, the avx2 implementation is faster than the previously reported sequential implementation [5]. In
view of this observation, in this work we present only the timing results for the prime 2130 − 5. For
the case of polyHash1305, the timing results show that for files which are longer than a few hundred
bytes, the avx2 implementation is faster than the previously reported sequential implementation [5]. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. In a typical file system, text
files are usually about a few kilobytes long, while media files such as high resolution pictures, audio
and video files, are a few megabytes long (see [14]). Compared to Poly1305, the new hash function
4-decBRWHash1305 provides a faster option for authentication, or authenticated encryption of such
files. In a typical file system, text
files are usually about a few kilobytes long, while media files such as high resolution pictures, audio
and video files, are a few megabytes long (see [14]). Compared to Poly1305, the new hash function
4-decBRWHash1305 provides a faster option for authentication, or authenticated encryption of such
files. In a typical file system, text
files are usually about a few kilobytes long, while media files such as high resolution pictures, audio
and video files, are a few megabytes long (see [14]). Compared to Poly1305, the new hash function
4-decBRWHash1305 provides a faster option for authentication, or authenticated encryption of such
files. In a typical file system, text
files are usually about a few kilobytes long, while media files such as high resolution pictures, audio
and video files, are a few megabytes long (see [14]). Compared to Poly1305, the new hash function
4-decBRWHash1305 provides a faster option for authentication, or authenticated encryption of such
files. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. 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. 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. From a practical point of view, we report implementations of 4-decBRWHash for both the primes
2
127 − 1 and 2130 − 5 using the avx2 SIMD instructions available on modern Intel processors. For
completeness and for the sake of comparison, we also report new implementations of polyHash
using avx2 instructions for both 2127 − 1 and 2130 − 5. From a practical point of view, we report implementations of 4-decBRWHash for both the primes
2
127 − 1 and 2130 − 5 using the avx2 SIMD instructions available on modern Intel processors. For
completeness and for the sake of comparison, we also report new implementations of polyHash
using avx2 instructions for both 2127 − 1 and 2130 − 5. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential
∗Corresponding author. 1
arXiv:2507. Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential
∗Corresponding author. 1
arXiv:2507. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Almost XOR universal (AXU) hash functions play an important role in
both of these tasks. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Keywords: almost XOR universal, BRW polynomials, SIMD, assembly
implementation, avx2. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Keywords: almost XOR universal, BRW polynomials, SIMD, assembly
implementation, avx2. 1 Introduction
Authentication and authenticated encryption are two of the major functionalities of modern symmetric key cryptography. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. Vectorised Hashing Based on
Bernstein-Rabin-Winograd Polynomials over Prime
Order Fields
Kaushik Nath∗1 and Palash Sarkar1
1
Indian Statistical Institute, 203, B. Road, Kolkata, India 700108
Emails: kaushik. The differential probability corresponding to the triple (a, a′
, b) is defined to
be Prτ [Hashτ (a) − Hashτ (a
′
) = b], where the probability is taken over a uniform random choice
of τ from K. If for every choice of distinct a, a′
in D and b ∈ R, the differential probability
corresponding to (a, a′
, b) is at most ϵ, then we say that the family {Hashτ }τ∈K is ϵ-almost XOR
universal (ϵ-AXU). The differential probability corresponding to the triple (a, a′
, b) is defined to
be Prτ [Hashτ (a) − Hashτ (a
′
) = b], where the probability is taken over a uniform random choice
of τ from K. If for every choice of distinct a, a′
in D and b ∈ R, the differential probability
corresponding to (a, a′
, b) is at most ϵ, then we say that the family {Hashτ }τ∈K is ϵ-almost XOR
universal (ϵ-AXU).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[1] Daniel J. Bernstein. Floating-point arithmetic and message authentication, 2004 <ref:2507.06490#pg2> [3] Daniel J. Bernstein. Polynomial evaluation and message authentication, 2007 <ref:2507.06490#pg2> [4] Daniel J. Bernstein. ChaCha, a variant of Salsa20 <ref:2507.06490#pg2> [5] Sreyosi Bhattacharyya, Kaushik Nath, and Palash Sarkar. Polynomial hashing over prime order fields <ref:2507.06490#pg2> [6] Sreyosi Bhattacharyya and Palash Sarkar. Improved SIMD implementation of Poly1305 <ref:2507.06490#pg2> [7] J¨urgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, and Ben J. M. Smeets. On families of hash functions via geometric codes and concatenation <ref:2507.06490#pg2> [8] Larry Carter and Mark N. Wegman. Universal classes of hash functions <ref:2507.06490#pg2> [9] Debrup Chakraborty, Sebati Ghosh, and Palash Sarkar. A fast single-key two-level universal hash function <ref:2507.06490#pg2> [10] Debrup Chakraborty, Cuauhtemoc Mancillas-L´opez, Francisco Rodr´ıguez-Henr´ıquez, and Palash Sarkar. Efficient hardware implementations of BRW polynomials and tweakable enciphering schemes <ref:2507.06490#pg2> [11] Debrup Chakraborty, Cuauhtemoc Mancillas-L´opez, and Palash Sarkar. STES: A stream cipher based low cost scheme for securing stored data <ref:2507.06490#pg2> [12] Jean Paul Degabriele, Jan Gilcher, J´erˆome Govinden, and Kenneth G. Paterson. SoK: Efficient design and implementation of polynomial hash functions over prime fields <ref:2507.06490#pg2> [13] Bert den Boer. A simple and key-economical unconditional authentication scheme <ref:2507.06490#pg2> [14] Jesse David Dinneen and Ba Xuan Nguyen. How big are peoples’ computer files? file size distributions among user-managed collections <ref:2507.06490#pg2> [15] Sebati Ghosh and Palash Sarkar. Evaluating Bernstein-Rabin-Winograd polynomials <ref:2507.06490#pg2> [16] Martin Goll and Shay Gueron. Vectorization of Poly1305 message authentication code <ref:2507.06490#pg2> [17] Tadayoshi Kohno, John Viega, and Doug Whiting. CWC: A high-performance conventional authenticated encryption mode <ref:2507.06490#pg2> [18] Kaushik Nath and Palash Sarkar. Efficient arithmetic in (pseudo-)Mersenne prime order fields <ref:2507.06490#pg2> [19] Kaushik Nath and Palash Sarkar. An update to “Polynomial Hashing over Prime Order Fields” <ref:2507.06490#pg2> [20] E. Ozturk, J. Guilford, and V. Gopal. Large integer squaring on Intel architecture processors <ref:2507.06490#pg2> [21] E. Ozturk, J. Guilford, V. Gopal, and W. Feghali. New instructions supporting large integer arithmetic on Intel architecture processors <ref:2507.06490#pg2> [22] Michael O. Rabin and Shmuel Winograd. Fast evaluation of polynomials by rational preparation <ref:2507.06490#pg2> [23] Palash Sarkar. Efficient tweakable enciphering schemes from (block-wise) universal hash functions <ref:2507.06490#pg2> [24] Palash Sarkar. A trade-off between collision probability and key size in universal hashing using polynomials <ref:2507.06490#pg2> [25] Palash Sarkar. A new multi-linear universal hash family <ref:2507.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Vectorized Hashing for Authentication and Encrypted Data: The c-decBRWHash function allows for a vectorised implementation using avx2 SIMD instructions, enabling simultaneous computation of four independent BRW polynomial computations on decimated input streams. This capability is particularly useful for high-throughput data processing in authentication and authenticated encryption systems.
-
Speed Optimization in File Hashing: For messages longer than a few hundred bytes, the 4-decBRWHash function shows a speed-up of about 16% for kilobyte messages and improves to about 23% for megabyte range messages compared to Poly1305, making it a faster alternative for hashing large files.
-
Optimized Implementation Choices: The choice of parameters like g in polyHash and t in c-decBRWHash can be optimized based on message length to achieve the best performance, as seen by the timing results indicating that "in general g = 4 is a faster option than 1 <= g < 4" for avx2 implementations.
-
Hardware Acceleration Potential: The research explores using different field element representations, such as the 5-limb representation for prime order fields, to optimize multiplication and reduction steps, potentially leading to significant speed improvements if future SIMD instructions support carry handling.
-
Storage Efficiency Analysis: For storing key material in vectorised implementations of c-decBRWHash, the required storage scales with g and the number of blocks as 160 + 288g bytes for polyHash1305, providing a quantitative measure for resource planning in high-performance systems.
Abstract
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.
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data