# Can “nothing-up-my-sleeve” computations be obtained from other cryptosystems?

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?

• 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 at 21:40
• @GeoffroyCouteau. I should have mentioned that the algorithm $H:f\mapsto C_{f}$ needs to be deterministic. – 35093731895230467514051 Apr 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 at 9:34