Fast message authentication codes (MACs, short tags that let a receiver detect tampering) are often built from universal hash functions. A typical one computes a dot product between the message words and a secret key, modulo some number $n$. The theory says that when $n$ is composite, security collapses to the smallest prime factor of $n$: the best forgery probability is $1/(p_{\min}-1)$, and it reaches 1 when $n$ is even. This would seem to rule out building a large modulus out of several word-sized primes, which is the representation GPUs handle well. A GPU multiplies 32-bit integers natively and only emulates 64-bit and wider products. Splitting a big modulus into many small primes, the residue number system, turns one wide product into several independent native ones. Each prime then becomes a "channel" that can run in parallel.
This note argues that the smallest-prime bottleneck is not a property of the modulus alone. It is a property of the modulus together with the range of values a message word may take. Once that range is fixed, security can scale with the size of all of $n$. Range is a memory-layout decision: how many bits each word occupies in a 32-bit slot. So the security analysis and the GPU mapping problem are the same design question. The proposal pairs a precise range-dependent security bound with a GPU kernel whose thread-block placement exploits the data reuse this construction creates. The two are evaluated together by one measure: authenticated gigabytes per second at a fixed forgery probability.
Core Claim
Take a squarefree odd modulus $n = p_1 p_2 \cdots p_k$ built from distinct odd primes. Use the dot-product hash over $\mathbb{Z}_n$ with keys coprime to $n$. Restrict message words to integers in $[0, W)$. We claim the worst-case collision probability is
$$\varepsilon(W) \;=\; \max_{S \,:\, \prod_{j \in S} p_j < W} \;\; \prod_{j \notin S} \frac{1}{p_j - 1},$$
where $S$ ranges over sets of prime factors whose product an adversary can fit into a single message-word difference.
The upper bound has a short proof. Any nonzero word difference $a_i$ with $|a_i| < W$ is divisible only by a set of primes whose product is below $W$, and it is invertible modulo every other prime. The Chinese remainder theorem makes the key's residues independent across primes, so each surviving prime contributes a factor of $1/(p_j-1)$. A matching attack places the same difference $\prod_{S} p_j$ in two coordinates. This attack is a generalisation we propose to formalise, not a result taken from the cited papers.
The formula recovers both known endpoints. When $W \le p_{\min}$, no prime can be cancelled, and $\varepsilon = 1/\varphi(n)$, where $\varphi(n)$ is the number of integers below $n$ coprime to it. Security then scales with all of $n$. When $W$ exceeds $n/p_{\min}$, the formula reduces to the tight $1/(p_{\min}-1)$ bound proven by On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes.
The math is elementary, and we do not claim otherwise. Its value is that it makes a layout decision visible as a security cost. Take four primes just below $2^{31}$, which together give roughly 124 bits of nominal security. If words are stored in full 32-bit slots, then $W = 2^{32}$ lets an attacker cancel one channel, and security falls to about $2^{-93}$. Packing words to 30 bits restores $2^{-124}$. A choice that looks like alignment housekeeping silently costs a quarter of the security margin.
Where This Sits
The security side builds on three works.
- The power of primes proves the smallest-prime-factor forgery bound and the failure of even moduli. It also shows that perfect secrecy requires restricting messages to units, the elements of $\mathbb{Z}_n$ that have a multiplicative inverse.
- On almost-universal multilinear modular hashing with composite moduli and its companion On a variant of multilinear modular hashing generalise the multilinear hash to composite rings. - On an Almost-Universal Hash Function Family uses Ramanujan sums to give a tight characterisation of when that hash is almost-universal: $n$ odd and all keys coprime to $n$.
These papers motivate and constrain the proposal: they forbid even moduli and fix the key condition. All of them, however, analyse unrestricted message words. Our bound adds the word range as a second parameter and shows that their tight bound is the large-$W$ end of a curve.
The key condition is cheap here. With large primes, the fraction $\varphi(n)/n$ is close to 1, so rejection sampling for coprime keys almost never rejects.
The systems side supplies the methods.
- A Compiler-assisted locality aware CTA Mapping Scheme detects reuse across thread blocks with a polyhedral model and steers blocks along the reuse dimension. It reports a 23.3% average gain over the Greedy-Then-Oldest scheduler in GPGPU-Sim. It relies on a custom dispatch register that commodity GPUs do not expose.
- Thread Batching for High-performance Energy-efficient GPU Memory Design and TEMP group blocks that share memory pages onto the same DRAM banks.
- Sparse MTTKRP Acceleration for Tensor Decomposition on GPU maps all work for one output into one thread block, which removes global atomics.
We reuse the reuse-directed mapping and the output-centric reduction. We replace the hardware dispatch register with software block-index remapping. None of these papers touches cryptographic arithmetic.
Two papers bound the arithmetic design.
- TensorFHE shows that wide modular arithmetic can be sliced into 8-bit pieces for GPU tensor cores, the matrix-multiply units on recent GPUs. It reaches 913 KOPS for the Number Theoretic Transform (NTT) on an A100.
- Optimized Modular Multiplication for SIDH shows that structured primes cut reduction from 236 cycles to 28 on an FPGA.
Both work over prime or lattice moduli and say nothing about universal-hash security.
No paper in the file connects composite-modulus hash security with thread-block mapping. The closest adjacent works are TensorFHE (modular arithmetic on GPUs, but with no MAC security analysis) and the CTA-mapping papers (no cryptographic workloads).
Research Program
The theoretical component proves the range-dependent bound for squarefree $n$. It extends the bound to prime-power factors, where a difference can be partly but not fully divisible by $p^e$. It also gives the analogous bound for the almost-Δ-universal property, which a MAC needs when the hash output is masked by a one-time pad. We then turn the bound into a design table. Each entry lists a channel count, a prime size and a word width, together with the resulting security.
The systems component treats a batch of $B$ messages of $L$ words each, hashed under $k$ residue channels, as a computation over a grid of message tiles by channels. It has two kinds of reuse.
- A message tile is read by all $k$ channels. We call a mapping channel-major when all channels for a message tile run on the same streaming multiprocessor (SM, the GPU's processing core), so the tile is loaded into shared memory once.
- A key tile is read by all $B$ messages. A key-stationary mapping keeps it resident instead.
We will derive which mapping wins as a function of $k$, $L$ and $B$ using the reuse-distance reasoning of the compiler-assisted mapping paper. Mapping is enforced in software: each block remaps its block index into a logical tile, and a persistent-block variant reads the SM identifier. Each (message, channel) accumulator stays in registers until a single final reduction, following the output-centric pattern of the MTTKRP work, so no global atomics are needed.
Word packing is the point where security and memory meet. We will implement three layouts and measure the throughput each one costs:
- 30-bit words packed across 32-bit-aligned memory, which requires an unpack step;
- 16-bit words, which are naturally aligned but carry less message per multiply;
- full 32-bit words, at the reduced security level.
Messages come from the Wiki (1 GB, 136M tokens) and Meme (402M tokens) corpora used in Hash in a flash. We cut them into fixed-size records, which gives realistic batch sizes. The main hardware is an A100 and an RTX 3090, the platforms of TensorFHE and the MTTKRP paper. The GPGPU-Sim GTX480 model from the compiler-assisted mapping paper lets us compare our software remapping against hardware-steered dispatch.
Baselines
The naive reference point is one thread per message. It uses the default hardware block dispatch, unpacked 32-bit words, and per-channel arithmetic with no shared-memory staging. This reference shows how much any engineering helps at all.
The strongest competitor for the security goal is a single large prime with fast reduction. We implement $2^{61}-1$ with two independent hashes, and $2^{127}-1$ as a multi-limb hash in the style of Poly1305, both tuned with the same shared-memory and key-staging effort as our kernel. This is the strongest alternative because prime moduli are the theoretical optimum according to The power of primes. It needs no range restriction.
The strongest competitor for the mapping goal is GEMM-style tiling with standard block swizzling. The batched hash is a skinny matrix product: messages times keys, giving one output per message and channel. Tiling of this kind is what a practitioner would reach for first. Optionally we also include an INT8 tensor-core variant that slices keys into 8-bit pieces in the manner of TensorFHE.
All kernels are compared under the same conditions:
- the same corpora, batch sizes and GPUs;
- the same autotuning budget over tile shapes, measured in wall-clock search time;
- the same target forgery probability, $2^{-120}$ or better. A kernel that cannot reach the target is reported at its achieved level and is not counted as beating anything.
On published numbers, no result was found on Lacuna for GPU throughput of universal-hash MACs. The only file numbers on the size of mapping gains are 23.3% over Greedy-Then-Oldest scheduling (compiler-assisted CTA mapping, GPGPU-Sim) and a 10.3% geometric-mean speedup for thread batching. These calibrate expectations but are not direct competitors. Beating the strongest baseline means higher throughput at equal security than the better of the $2^{61}-1$ and $2^{127}-1$ kernels, on both GPUs and both corpora.
Two ablations isolate the ingredients. The first is the same kernel with locality mapping replaced by default dispatch, which isolates the mapping. The second is the same kernel with 32-bit unpacked words, which shows what the security-preserving packing costs.
Why not just…?
Why not just use one large prime such as $2^{127}-1$? This is the main threat, and we do not argue it away. A prime needs no range restriction and gives optimal security. Its cost on GPUs is that each multiply is multi-limb and emulated, and every limb-product carry chain serialises work that residue channels keep independent. The SIDH paper's 236-versus-28-cycle gap shows how much reduction structure matters, but that was measured on FPGAs, not GPUs. The iso-security throughput comparison settles the question. If $2^{127}-1$ matches residue slicing, the systems claim fails, and what remains is the security result about layout pitfalls in existing residue-number-system designs.
Why not just run $k$ independent hashes modulo different primes? Mathematically, that is what this construction is once the range condition holds. Our contribution is to show exactly when the composite view and the independent-channels view coincide, and that they diverge when words are wider than the smallest prime. Implementations that store full 32-bit words with 31-bit primes fall into exactly that gap. The systems contribution is the same either way, because the reuse of a message across channels is what the mapping exploits.
Why not just rely on the L2 cache and default scheduling? A message tile is reused only $k$ times, roughly two to four, so a multi-megabyte L2 may capture most of that reuse without help. This is a real threat to the mapping contribution. The default-dispatch ablation decides it. We will report L1 and L2 hit rates and DRAM traffic. If the gain stays well below the 23.3% reported for compiler-assisted mapping, we will say the mapping is not worth its complexity for this workload.
Why not just auto-tune the kernel with evolutionary search? GEVO obtains part of its gains by tolerating output error, for example 51.08% under 1% error. Cryptographic tags tolerate none. Generic search also cannot see that widening a word slot costs security. We will still run a correctness-locked tile-shape search as part of the shared tuning budget.
Decisive Experiments
The first check is exhaustive, and it tests the theorem before any GPU code exists. For small moduli such as $5\cdot7\cdot11$ and $7\cdot11\cdot13$, we enumerate all keys and all message pairs for word ranges $W$ from 2 up to past $n/p_{\min}$. We then compare the measured worst-case collision probability against the formula. Agreement is required at both endpoints, $1/\varphi(n)$ and the tight GRDH value $1/(p_{\min}-1)$, and at every intermediate step. A single mismatch means the bound is wrong.
The second check runs the two-coordinate cancellation attack on a full-size four-prime instance with 32-bit words. We confirm that one channel collides deterministically, which demonstrates the predicted loss to about $2^{-93}$.
The third check is the throughput comparison at iso-security on the A100 and RTX 3090, using the Wiki and Meme record streams. It includes the mapping and packing ablations, with hit rates and DRAM traffic broken down per kernel.
The proposal succeeds if three things hold. The exhaustive counts match the bound. The attack works as predicted. And the residue-sliced kernel with locality mapping beats the best single-prime kernel at equal forgery probability, with the mapping ablation accounting for a measurable share of that margin.
References
- On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
- The power of primes: security of authentication based on a universal hash-function family
- On almost-universal multilinear modular hashing with composite moduli
- On a variant of multilinear modular hashing with applications to authentication and secrecy codes
- A Compiler-assisted locality aware CTA Mapping Scheme
- Thread Batching for High-performance Energy-efficient GPU Memory Design
- TEMP: thread batch enabled memory partitioning for GPU
- Sparse MTTKRP Acceleration for Tensor Decomposition on GPU
- TensorFHE: Achieving Practical Computation on Encrypted Data Using GPGPU
- Optimized Modular Multiplication for Supersingular Isogeny Diffie-Hellman
- Hash in a flash: Hash tables for flash devices
- GEVO: GPU Code Optimization Using Evolutionary Computation