<p><strong>Fully black-box reduction</strong> is defined as in <em>Notions of reducibility between crytpographic primitives</em>, O. Reingold et al.</p>
<p>Error-correcting code is used in the black-box abstract way in the sense that any implementation (instance) is eligible as long as it satisfies the definition of a <span class="math-container">$(\delta, r)$</span>-good code, where the relative distance <span class="math-container">$\delta$</span> and the code rate <span class="math-container">$r$</span> are constants. The instance is used in the manner that the reduction can only control the inputs and get the outputs (black-box).</p>
<p>We require that the universal hashing gained is strictly universal (collision probability <span class="math-container">$=1/m$</span>).</p>
<p>The question is as stated in the title and, might be better considered using circuits.</p>
<p>The method used in <em>Limits on the Provable Consequences of One-way Permutations</em> by Impagliazzo and Rudich may also provide some hint but I am not sure.</p>

CC BY-SA 4.0
2023-08-11T11:22:09.437Z
What do you mean by "error correcting code" here? Do you mean a black-box abstraction of error correcting codes?
Peter Shor 
CC BY-SA 4.0
2023-08-12T10:52:34.433Z
@Peter Shor Yes, I mean such black-box abstraction.
Kagura Hitoha
CC BY-SA 4.0
2023-08-12T11:41:37.023Z
Maybe you could expand your question to give us a definition of a black-box abstraction of an error-correcting code. I can't come up with a definition that I think makes sense. (On the other hand, I have not tried very hard so I could easily be missing something.)
Peter Shor 
CC BY-SA 4.0
2023-08-12T12:03:14.863Z
@PeterShor I expanded my question. The error-correcting code should be "good" and can be accessed only to its inputs and outputs. Black-box reduction is defined in the paper I cited. No other restrictions are imposed.
Kagura Hitoha
CC BY-SA 4.0
2023-08-29T20:04:05.080Z
Your question concerns reductions between cryptographic tasks. Universal hashing and ECC are not cryptographic primitives. What does it mean for an adversary to "break" error correction or universal hashing? Answering this is a prerequisite to answering your original question.
lamontap
CC BY-SA 4.0
2023-10-02T13:09:00.480Z
I still don't know what you mean by a black-box error-correcting code. Do you mean a linear error-correcting code with a black-box decoder, or is it more complicated than that?
Peter Shor 
<reductions><cryptography>
Is universal hashing fully black-box reducible to error correcting code?
Kagura Hitoha
# Is universal hashing fully black-box reducible to error correcting code?

(Asked by: username_0 on 2023-08-11)

**Fully black-box reduction** is defined as in *Notions of reducibility between crytpographic primitives*, O. Reingold et al.

Error-correcting code is used in the black-box abstract way in the sense that any implementation (instance) is eligible as long as it satisfies the definition of a $(\delta, r)$-good code, where the relative distance $\delta$ and the code rate $r$ are constants. The instance is used in the manner that the reduction can only control the inputs and get the outputs (black-box).

We require that the universal hashing gained is strictly universal (collision probability $=1/m$).

The question is as stated in the title and, might be better considered using circuits.

The method used in *Limits on the Provable Consequences of One-way Permutations* by Impagliazzo and Rudich may also provide some hint but I am not sure.

**Tags:** reductions, cryptography
> **Comments:**
> **username_1**: What do you mean by "error correcting code" here? Do you mean a black-box abstraction of error correcting codes?  
> **username_0**: @Peter Shor Yes, I mean such black-box abstraction.  
> **username_1**: Maybe you could expand your question to give us a definition of a black-box abstraction of an error-correcting code. I can't come up with a definition that I think makes sense. (On the other hand, I have not tried very hard so I could easily be missing something.)  
> **username_0**: @PeterShor I expanded my question. The error-correcting code should be "good" and can be accessed only to its inputs and outputs. Black-box reduction is defined in the paper I cited. No other restrictions are imposed.  
> **username_2**: Your question concerns reductions between cryptographic tasks. Universal hashing and ECC are not cryptographic primitives. What does it mean for an adversary to "break" error correction or universal hashing? Answering this is a prerequisite to answering your original question.  
> **username_1**: I still don't know what you mean by a black-box error-correcting code. Do you mean a linear error-correcting code with a black-box decoder, or is it more complicated than that?  

---

## 0 answers

