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

arXiv:2507.06490 · cs.CR · Submitted 2025-07-09 · Read on arXiv

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

Where the paper says it

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.

06490#pg2> Choosing c > 1 gives a hash function which can be implemented using c-way single instruction multiple data (SIMD) instructions <ref:2507. p. 0
Where the paper says it

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.

06490#pg2>. 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. p. 0
Where the paper says it

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.

06490#pg2>. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials <ref:2507. p. 0
Where the paper says it

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.

06490#pg2>. We obtained extensive timing results for all our implementations <ref:2507. p. 2
Where the paper says it

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.

06490#pg2>. These results show that for avx2 implementations, the prime 2130 − 5 is faster than the prime 2127 − 1 for both the hash functions 4-decBRWHash and polyHash <ref:2507. p. 2
Where the paper says it

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).

06490#pg2>. 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 <ref:2507. p. 2
Where the paper says it

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].

06490#pg2>. Of more interest in the present context is the comparison between the hash functions 4-decBRWHash and polyHash <ref:2507. p. 2
Where the paper says it

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.

06490#pg2>. 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) <ref:2507. p. 2
Where the paper says it

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).

06490#pg2>.

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

Where the paper says it

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).

06490#pg2>. 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 <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. We define the hash function c-decBRWHash which is parameterised by the positive integer c <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. Suppose c = 4, which is the case that we implement <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. 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 <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. Finally the outputs of the four streams are combined using usual polynomials <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. 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 <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>.

Vectorized Implementation Details

The computation of c-decBRWHashτ (X) requires the evaluation of Q1(τ), Q2(τ),..., Qc(τ) <ref:2507. p. 0

Where the paper says it

Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential ∗Corresponding author. 1 arXiv:2507.

06490#pg2>. Evaluations of the Qi(τ)s require evaluations of c BRW polynomials, where the inputs to the BRW polynomials are disjoint and the number of message blocks provided as input is the same for all the BRW polynomials <ref:2507. p. 1
Where the paper says it

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.

06490#pg2>. Consequently, the c BRW polynomials can be simultaneously evaluated at τ using an SIMD strategy <ref:2507. p. 3
Where the paper says it

, Ml) can be evaluated using l − 1 multiplications and same number of additions. For the BRW polynomials the following was proved in [3].

06490#pg2>. We have implemented the SIMD version of Algorithm 1 for c = 4 <ref:2507. p. 0
Where the paper says it

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.

06490#pg2>. Table 3 provides the number of 4-way SIMD operations required for computing P (as part of the computation of polyHash) and decBRWHash for l message blocks <ref:2507. p. 8
Where the paper says it

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.

06490#pg2>.

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

Where the paper says it

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).

06490#pg2>. The number of SIMD reductions required by 4-decBRWHash is at most that required by polyHash for g ≤ 4, while for g > 4, polyHash requires less number of SIMD reductions <ref:2507. p. 8
Where the paper says it

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.

06490#pg2>. Experimental results for the primes 2130 − 5 and 2127 − 1, however, show that for avx2 implementations while there is a noticeable speed-up of 4-decBRWHash over polyHash, the actual speed-up obtained is less than what is theoretically predicted by operation counts <ref:2507. p. 2
Where the paper says it

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).

06490#pg2>.

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

Where the paper says it

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, .

06490#pg2>. So for any given message, the number of blocks for 2127 − 1 will be about 16/15 times the number of blocks for 2130 −5 <ref:2507. p. 6
Where the paper says it

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).

06490#pg2>. Being required to process more blocks, suggests that hash functions based on 2127 − 1 will be slower than the corresponding hash functions based on 2130 −5 <ref:2507. p. 1
Where the paper says it

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]).

06490#pg2>.

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

Where the paper says it

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.

06490#pg2>.

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

Where the paper says it

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.

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

Where the paper says it

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.

06490#pg2>.

References

[1] Daniel J. Bernstein. Floating-point arithmetic and message authentication, 2004 <ref:2507. p. 5

Where the paper says it

they are set to 0. In [2] the clamping of key bits helped in efficient floating point implementation.

p. 5
Where the paper says it

they are set to 0. In [2] the clamping of key bits helped in efficient floating point implementation.

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. p. 0
Where the paper says it

Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential ∗Corresponding author. 1 arXiv:2507.

p. 0
Where the paper says it

Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential ∗Corresponding author. 1 arXiv:2507.

06490#pg2> [5] Sreyosi Bhattacharyya, Kaushik Nath, and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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 hashing over prime order fields <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [6] Sreyosi Bhattacharyya and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Improved SIMD implementation of Poly1305 <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 4
Where the paper says it

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

p. 4
Where the paper says it

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

06490#pg2> [8] Larry Carter and Mark N. Wegman. Universal classes of hash functions <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [9] Debrup Chakraborty, Sebati Ghosh, and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

A fast single-key two-level universal hash function <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [10] Debrup Chakraborty, Cuauhtemoc Mancillas-L´opez, Francisco Rodr´ıguez-Henr´ıquez, and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Efficient hardware implementations of BRW polynomials and tweakable enciphering schemes <ref:2507. p. 2
Where the paper says it

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].

p. 2
Where the paper says it

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].

06490#pg2> [11] Debrup Chakraborty, Cuauhtemoc Mancillas-L´opez, and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 2
Where the paper says it

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].

p. 2
Where the paper says it

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].

06490#pg2> [13] Bert den Boer. A simple and key-economical unconditional authentication scheme <ref:2507. p. 1
Where the paper says it

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.

p. 1
Where the paper says it

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.

06490#pg2> [14] Jesse David Dinneen and Ba Xuan Nguyen. How big are peoples’ computer files? p. 2
Where the paper says it

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].

p. 2
Where the paper says it

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].

file size distributions among user-managed collections <ref:2507.06490#pg2> [15] Sebati Ghosh and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Evaluating Bernstein-Rabin-Winograd polynomials <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [16] Martin Goll and Shay Gueron. Vectorization of Poly1305 message authentication code <ref:2507. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

06490#pg2> [17] Tadayoshi Kohno, John Viega, and Doug Whiting. CWC: A high-performance conventional authenticated encryption mode <ref:2507. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

06490#pg2> [18] Kaushik Nath and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Efficient arithmetic in (pseudo-)Mersenne prime order fields <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [19] Kaushik Nath and Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

An update to “Polynomial Hashing over Prime Order Fields” <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [20] E. Ozturk, J. Guilford, and V. Gopal. Large integer squaring on Intel architecture processors <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [21] E. Ozturk, J. Guilford, V. Gopal, and W. Feghali. New instructions supporting large integer arithmetic on Intel architecture processors <ref:2507. p. 1
Where the paper says it

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.

p. 1
Where the paper says it

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.

06490#pg2> [22] Michael O. Rabin and Shmuel Winograd. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Fast evaluation of polynomials by rational preparation <ref:2507. p. 0
Where the paper says it

Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential ∗Corresponding author. 1 arXiv:2507.

p. 0
Where the paper says it

Such vectorised algorithms have the potential to provide significant efficiency improvements over conventional sequential ∗Corresponding author. 1 arXiv:2507.

06490#pg2> [23] Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

Efficient tweakable enciphering schemes from (block-wise) universal hash functions <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [24] Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

A trade-off between collision probability and key size in universal hashing using polynomials <ref:2507. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

06490#pg2> [25] Palash Sarkar. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

A new multi-linear universal hash family <ref:2507. p. 3
Where the paper says it

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).

p. 3
Where the paper says it

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).

06490#pg2>

[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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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