🔢 mathematics

Fast Bounded-Independence Functions and Their Duals

This paper presents improved constructions of fast bounded-independence functions and their duals that simultaneously optimize circuit size and algebraic degree, achieving negligible failure probability and supporting advanced cryptographic applications such as perfectly secure multiparty computation with linear complexity and optimal encrypted matrix-vector multiplication.

Original authors: Martijn Brehm, Yuval Ishai, Nicolas Resch

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martijn Brehm, Yuval Ishai, Nicolas Resch

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a digital fortress. To keep your data safe, you need two main tools: Hash Functions (like a unique fingerprint for a file) and Error-Correcting Codes (like a way to send a message that can survive being shredded and reassembled).

Usually, making these tools "perfectly random" (so hackers can't predict them) is slow and expensive. It's like trying to mix a giant vat of paint by hand; it takes forever. The goal of this paper is to build these tools so they are fast (like using a machine) but still act random enough to be secure.

Here is what the authors achieved, explained through simple analogies:

1. The "Super-Fingerprint" Machine (Fast Hash Functions)

The Problem: Imagine you have a huge library of books. You want to create a short "fingerprint" for each book so you can tell if two books are different. A "random" fingerprint is great because it's impossible to fake, but making one takes too long.
The Old Way: Previous methods could only guarantee that if you looked at two books, their fingerprints would be unrelated. If you looked at three, the pattern might start to repeat or become predictable.
The New Magic: The authors built a machine that can generate fingerprints for any number of books (say, 10, or 100) at once, and they will all look completely unrelated to each other.

The Analogy: Think of a dice roller. Old machines could only roll two dice at a time and guarantee they didn't match. This new machine can roll 100 dice, and no matter how many you look at, the results are totally unpredictable.
Why it matters: In cryptography, this means you can process data much faster without losing security. They also made sure the math behind it isn't too complicated (low "algebraic degree"), which is like saying the machine uses simple gears rather than complex, slow robotics.

2. The "Twin-Code" System (Fast Codes with Fast Duals)

The Problem: In cryptography, you often need two related codes: a "Primal" code to encrypt a message and a "Dual" code to help decrypt or verify it. Usually, you can have a fast Primal code or a fast Dual code, but rarely both at the same time. It's like having a fast lock but a slow key, or a fast key but a slow lock.
The Old Way: A recent attempt to make both fast worked, but it was finicky. It only worked for binary (0s and 1s), it had a small chance of failing, and it couldn't handle different types of data rates.
The New Magic: The authors built a system where both the lock and the key are fast, work for any type of data (not just 0s and 1s), and almost never fail.

The Analogy: Imagine a high-security vault. Previously, you could get a vault that opened quickly, but the backup key took hours to cut. Or you had a fast key but a vault that took days to open. This new design gives you a vault that opens instantly and a backup key that is cut instantly.
The "GV Bound" Achievement: They also proved these codes are as good as theoretically possible. Imagine trying to pack suitcases into a truck. The "Gilbert-Varshamov bound" is the theoretical limit of how many suitcases you can fit. These new codes pack the truck to the absolute brim, just like a random, perfect packing job would, but they do it with a fast, organized method.

3. The "Super-Resilient" Codes (List-Decoding)

The Problem: Sometimes, a message gets so corrupted (like a text message with half the letters missing) that you can't just guess the original. You have to list all the possible original messages.
The New Magic: The authors created codes that are so robust that even if a message is heavily damaged, the list of possible original messages is incredibly short (just a handful of options).

The Analogy: Imagine you receive a torn-up recipe. A normal code might say, "It could be anything from 'Bake a cake' to 'Build a house'." This new code says, "It's definitely either 'Bake a cake' or 'Bake a pie'." It narrows down the chaos to a tiny, manageable list.
The Twist: They did this for both the lock and the key (the code and its dual), which is a first.

4. Why This Matters for Security (The "Party" Analogy)

The paper shows how these tools help in Secure Multiparty Computation (MPC).

The Scenario: Imagine 100 people want to calculate their average salary without anyone revealing their own salary.
The Old Bottleneck: Doing this securely usually requires a lot of communication and computing power, scaling poorly as you add more people.
The New Result: Using these new fast codes, the amount of computing power needed grows linearly with the number of people.
The Analogy: If you have 10 people, it takes 10 minutes. If you have 1,000 people, it takes 1,000 minutes. Before, adding more people might have made the time explode (like 100 people taking 10,000 minutes). This makes secure group calculations feasible for huge groups.

Summary

The authors have built a new set of "fast-forward" buttons for cryptography. They created:

Hash functions that stay unpredictable even when you look at many inputs at once.
Encryption codes where both the encryption and decryption tools are fast, reliable, and work for any data type.
Resilient codes that can recover from heavy damage with very few guesses.

These tools allow secure computing to scale up efficiently, making it possible to protect data for large groups of people without slowing everything down to a crawl.

Technical Summary: Fast Bounded-Independence Functions and Their Duals

Problem Statement

The paper addresses the challenge of constructing cryptographic primitives that mimic the statistical properties of random functions and random linear codes while maintaining constant computational overhead. Specifically, the authors seek "fast" implementations—defined as those computable by linear-size arithmetic circuits (size $O(n)$ )—that satisfy:

Bounded Independence: Hash functions that are $t$ -wise independent for any constant $t$ .
Fast Dual Codes: Families of linear codes where both the code and its dual admit fast, systematic encoding and achieve distances close to the Gilbert-Varshamov (GV) bound.
Stronger Random-Like Properties: Extending beyond simple distance to properties like list-decodability, ensuring the codes behave like random linear codes even under local constraints (local similarity).

Previous work, such as [IKOS08] and [DI14], established fast pairwise independent hash functions and fast codes approaching the GV bound, but often with limitations regarding the independence parameter $t$ , the field of operation, or the ability to simultaneously optimize the code and its dual. A recent construction by [BR26] improved on fast dual codes but was restricted to binary fields, required a fixed rate of 1/2, had non-negligible failure probability, and lacked systematic encoding.

Methodology

The authors build upon the "IKOS construction" (Ishai, Kushilevitz, Ostrovsky, Sahai) and the "DI construction" (Druk, Ishai), generalizing them to higher independence parameters.

1. Generalizing Hash Functions

The core construction for hash functions follows a three-step pipeline:

Outer Encoding: Apply a fast linear code with large distance over a large (but constant) alphabet to the input.
Inner Hashing: Apply constant-sized, $t$ -wise independent hash functions to each coordinate of the encoded vector.
Extraction: Apply the transpose of a generator matrix of a good code (acting as an extractor) to the result.

To achieve $t$ -wise independence, the authors replace the constant-sized pairwise independent hash functions in the inner step with constant-sized $t$ -wise independent hash functions. They prove that if the outer code has sufficiently large distance (specifically $> 1 - 1/t^2$ ), the distinctness of $t$ inputs is preserved across a sufficient fraction of coordinates, allowing the inner hash functions to produce independent, uniform outputs that the final extraction step preserves.

2. Linear Uniform Output Families (LUOF)

To construct the codes, the authors utilize the concept of a Linear Uniform Output Family (LUOF). A random matrix $A$ is a LUOF if, for any non-zero input $x$ , the output $xA$ is uniformly distributed.

Fast LUOF: The authors generalize the construction of [DI14] to create a fast $t$ -LUOF. A matrix $A$ is a $t$ -LUOF if, for any set of $t$ linearly independent inputs $x_1, \dots, x_t$ , the outputs $x_1A, \dots, x_tA$ are uniformly and stochastically independent.
Construction: Similar to the hash function construction, this involves an outer code, a layer of random constant-sized matrices (acting as the "inner" function), and an extraction step. The authors prove that if the outer code has sufficient distance, the inner random matrices map linearly independent inputs to independent uniform outputs.

3. Constructing Fast Dual Codes

Using a $t$ -LUOF matrix $A \in \mathbb{F}_q^{k \times r}$ , the authors define a code $C$ with the systematic encoding map $x \mapsto (x, xA)$ .

Duality: The dual code $C^\perp$ is generated by the map $y \mapsto (-yA^\top, y)$ .
Transposition Principle: Citing the transposition principle (Lemma 3.4), they argue that if computing $xA$ is fast (linear size), then computing $yA^\top$ is also fast.
Independence of Dual: A crucial technical contribution is proving that if $A$ is a $t$ -LUOF, then $A^\top$ is also a $t$ -LUOF (Lemma 3.9). This relies on Vazirani's XOR Lemma and ensures that the dual code inherits the strong randomness properties of the primal code.

Key Contributions and Results

1. Fast $t$ -Wise Independent Hash Functions

Result: For any constant $t$ , the authors construct a family of $t$ -wise independent hash functions computable by linear-size circuits.
Optimization: For the binary field ( $q=2$ ), the algebraic degree is optimized to $\log_2 t$ . This is near-optimal, as lower degrees would fail to support $t$ -wise independence.
Efficiency: The circuit size is $O(k+r)$ , where $k$ is input length and $r$ is output length. The hidden constant depends on $t$ (roughly $\Theta(t^7)$ ), but remains constant for fixed $t$ .

2. Fast Codes with Fast Duals (GV-Bound)

Result: The authors construct a family of codes $C$ and their duals $C^\perp$ over any finite field $\mathbb{F}_q$ with arbitrary rate $R \in (0, 1)$ .
Properties:
- Both $C$ and $C^\perp$ admit fast, systematic encoding (linear size).
- Both achieve distances $\varepsilon$ -close to the Gilbert-Varshamov bound with probability $1 - 2q^{-\varepsilon n}$ .
- The construction has negligible failure probability (unlike [BR26]).
- It supports a linear-sized universal circuit for encoding.

3. Fast List-Decodable Codes with Fast Duals

Result: By utilizing the $t$ -LUOF property, the authors extend the construction to codes that are $t$ -locally similar to random linear codes.
List-Decoding: They prove that for any constant $t$ , the constructed codes (and their duals) are $(\rho, L)$ -list-decodable up to the list-decoding capacity, with list size $L = O(1/\varepsilon)$ .
Novelty: This is the first construction (to the authors' knowledge) that simultaneously achieves fast encoding, fast dual encoding, and optimal list-decodability for both the code and its dual.

Significance and Cryptographic Applications

The paper demonstrates that these constructions serve as powerful building blocks for cryptography, particularly in scenarios requiring high efficiency and strong security guarantees.

1. Perfectly Secure Multiparty Computation (MPC)

The authors present the first non-trivial protocols for perfectly secure MPC where the circuit complexity scales linearly with the number of parties ( $O(n)$ ).

Context: Previous protocols using algebraic codes (like Reed-Solomon) often incurred quasi-linear overhead.
Application: Using the fast dual codes, they construct an Oblivious Linear Evaluation (OLE) protocol and extend it to general constant-size functions. The protocol achieves a security threshold of $t = (1/2 - \varepsilon)n$ against passive adversaries.

2. Encrypted Matrix-Vector Products (EMVP)

In the context of complexity-based cryptography, the authors apply their fast dual codes to encrypted matrix-vector products.

Improvement: Their construction overcomes limitations of the [BR26] approach (which was limited to $\mathbb{F}_2$ and had non-negligible failure probability).
Benefit: This enables EMVP protocols where both matrix encoding and query encoding have asymptotically optimal circuit complexity.

3. Conservative Substitutes for Random Linear Codes

The $t$ -LUOF construction provides a "conservative" substitute for random linear codes in applications relying on the hardness of noisy linear algebra (e.g., Learning Parity with Noise - LPN).

Advantage: While previous constructions relied only on minimum distance (1-local similarity), the $t$ -LUOF ensures $t$ -local similarity, guaranteeing stronger combinatorial properties like list-decodability. This offers a more robust security assumption against attacks that might exploit local structures.

4. MPC-Friendly Hashing

The fast $t$ -wise independent hash functions with low algebraic degree are directly applicable to MPC protocols where both circuit size and algebraic degree impact communication and round complexity. The construction optimizes both simultaneously.

Conclusion

The paper successfully generalizes previous linear-size constructions to support higher independence parameters and stronger random-like properties. By introducing fast $t$ -LUOFs and proving their duality properties, the authors provide a unified framework for constructing codes and hash functions that are simultaneously fast, systematic, and statistically robust. These results enable new cryptographic protocols with optimal asymptotic complexity, particularly in information-theoretic MPC and encrypted computation.