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.


1 Answer 1


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 and error-correcting codes. Universal hashes are often used in cryptography to build message authenticators, such as Poly1305 and GHASH.

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.

  • $\begingroup$ Thank you. I will refer to these papers for details. $\endgroup$ Jun 27, 2023 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.