Does there exist constant overhead reduction between common cryptographic primitives?

Question

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.

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.