3

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?

Joseph Van Name
  • 1,235
  • 12
  • 19
  • 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$). – Geoffroy Couteau Apr 18 '18 at 21:40
  • @GeoffroyCouteau. I should have mentioned that the algorithm $H:f\mapsto C_{f}$ needs to be deterministic. – Joseph Van Name Apr 18 '18 at 23:02
  • @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$. – pscholl Apr 19 '18 at 09:34
  • @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. – Alex Coventry Jan 06 '19 at 22:32

0 Answers0