<p>I'm not sure if it would qualify as a <em>reduction</em> in your terms per se, but there is certainly a connection between <a href="https://en.wikipedia.org/wiki/Universal_hashing" rel="nofollow noreferrer">universal hashing</a> and error-correcting codes. Universal hashes are often used in cryptography to build message authenticators, such as <a href="https://en.wikipedia.org/wiki/Poly1305" rel="nofollow noreferrer">Poly1305</a> and <a href="https://en.wikipedia.org/wiki/Galois/Counter_Mode#Mathematical_basis" rel="nofollow noreferrer">GHASH</a>.</p>
<p>A theorem by Bierbrauer, et al. in <em>&quot;On Families of Hash Functions via Geometric Codes and Concatenation&quot;</em> states, informally, that if certain codes exist that certain universal hashes exist, and vice versa.</p>
<p>I'd suggest <em>&quot;On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes&quot;</em> by Douglas R. Stinson for background and <em>&quot;On the Minimum Number of Multiplications Necessary for Universal Hash Functions&quot;</em> by Mridul Nandi for a concrete example, if you are interested.</p>

CC BY-SA 4.0
2023-06-27T02:58:54.757Z
Thank you. I will refer to these papers for details.
Kagura Hitoha
CC BY-SA 4.0
2023-06-25T16:02:02.147Z
2023-06-25T16:02:02.147Z
orlp
<p>I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the <em>transpose</em> of a generator matrix for a ERC mapping <span class="math-container">$\mathbb{F}_2^m$</span> to <span class="math-container">$\mathbb{F}_2^n$</span> with distance <span class="math-container">$d$</span> <em>is</em> an <span class="math-container">$l$</span>-ERF where <span class="math-container">$l=n-d+1$</span>. Does there exist constant-multiplicative-overhead reductions between other cryptographic primitives, for example, between encryption and error-correcting code? The above question is stated under the context of circuit complexity.</p>

<cc.complexity-theory><circuit-complexity><reductions><cryptography>
Does there exist constant overhead reduction between common cryptographic primitives?
Kagura Hitoha
# Does there exist constant overhead reduction between common cryptographic primitives?

(Asked by: username_0 on 2023-06-24)

I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the *transpose* of a generator matrix for a ERC mapping $\mathbb{F}\_2^m$ to $\mathbb{F}\_2^n$ with distance $d$ *is* an $l$-ERF where $l=n-d+1$. Does there exist constant-multiplicative-overhead reductions between other cryptographic primitives, for example, between encryption and error-correcting code? The above question is stated under the context of circuit complexity.

**Tags:** cc.complexity-theory, circuit-complexity, reductions, cryptography


---

## 1 answers

### Answer by username_1 on 2023-06-25. Score: 4

I'm not sure if it would qualify as a *reduction* in your terms per se, but there is certainly a connection between [universal hashing](https://en.wikipedia.org/wiki/Universal_hashing) and error-correcting codes. Universal hashes are often used in cryptography to build message authenticators, such as [Poly1305](https://en.wikipedia.org/wiki/Poly1305) and [GHASH](https://en.wikipedia.org/wiki/Galois/Counter_Mode#Mathematical_basis).

A theorem by Bierbrauer, et al. in *"On Families of Hash Functions via Geometric Codes and Concatenation"* states, informally, that if certain codes exist that certain universal hashes exist, and vice versa.

I'd suggest *"On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes"* by Douglas R. Stinson for background and *"On the Minimum Number of Multiplications Necessary for Universal Hash Functions"* by Mridul Nandi for a concrete example, if you are interested.

> **Comments:**
> **username_0**: Thank you. I will refer to these papers for details.  

---

