2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by "error correcting code" here? Do you mean a black-box abstraction of error correcting codes? $\endgroup$
    – Peter Shor
    Aug 11 at 11:22
  • $\begingroup$ @Peter Shor Yes, I mean such black-box abstraction. $\endgroup$
    – Kagura Hitoha
    Aug 12 at 10:52
  • $\begingroup$ 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.) $\endgroup$
    – Peter Shor
    Aug 12 at 11:41
  • $\begingroup$ @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. $\endgroup$
    – Kagura Hitoha
    Aug 12 at 12:03
  • $\begingroup$ 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. $\endgroup$
    – lamontap
    Aug 29 at 20:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.