3
$\begingroup$

So, in cryptography, it is sometimes the case that in order to set up a cryptosystem, one needs some output $f(x)$ for randomly generated $x$ where $f$ is a one-way function but where the input $x$ can be used to break the cryptosystem (i.e. the input $x$ is toxic waste that needs to be destroyed or the output $f(x)$ needs to be computed using some sort of secure multi-party computation).

Does there exist an efficient (by efficient I mean polynomial time) deterministic algorithm that given a one-way function $f$, returns a circuit $C_{f}$ such that for all inputs $x$, there is some $c$ where $C_{f}(x)=f(c)$ but where there is no efficient algorithm that given $x$ returns some $d$ with $f(d)=C_{f}(x)$ (preferably where the function $C_{f}$ is collision resistant)? Or does there exist some impossibility result for such a cryptosystem? If there is no impossibility result, then what is the weakest cryptosystem that ensures an algorithm $f\mapsto C_{f}$ exists?

$\endgroup$
  • $\begingroup$ There seems to be a trivial solution: pick a random $y$ in the image of $f$, and set $C_f$ to be the constant function that outputs $y$ on any input $x$. Then for any input $x$ there is $c$ such that $C_f(x)=y=f(c)$ as $y$ is in the image of $f$, but given any $x$ and $C_f$, finding $c$ is hard (it requires inverting $f$). $\endgroup$ – Geoffroy Couteau Apr 18 '18 at 21:40
  • $\begingroup$ @GeoffroyCouteau. I should have mentioned that the algorithm $H:f\mapsto C_{f}$ needs to be deterministic. $\endgroup$ – Joseph Van Name Apr 18 '18 at 23:02
  • $\begingroup$ @GeoffroyCouteau's solution can still work deterministically. E.g. if $f$ is a permutation you can choose the identity function $C_{f}(y) = y$, which is in the image of $f$. $\endgroup$ – pscholl Apr 19 '18 at 9:34
  • $\begingroup$ @GeoffroyCouteau: For general $f$, it's not feasible to find something in the range without evaluating $f(c)$ for some $c$ in the domain, and that $c$ is the "toxic waste." I think Joseph is asking whether it's possible to construct a securely oblivious computation which cryptographically randomly (using $x$ as the seed, in his notation) chooses an illegible representation of some $c$ from the domain, then returns $f(c)$, computed from that illegible representation. $\endgroup$ – Alex Coventry Jan 6 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.