# Do probabilistic one-way functions imply deterministic one-way functions?

Suppose $$f$$ is a probabilistic one-way function. Then my question is, does there exist a construction of a deterministic one-way function $$g$$ based on $$f$$?

Or is it possible that probabilistic one-way functions exist but deterministic one-way functions do not?

EDIT: Probabilistic one-way functions are defined in definition 2.2.2 here.

• What's your definition of a probabilistic one-way function? – Maeher Nov 1 '20 at 19:08
• @Maeher The probabilistic part means that for any given input f doesn’t always give the same output, but instead randomly selects from a set of possible outputs. The one-wayness part means that for any probabilistic polynomial time adversary A, if A is given f(x) where x is a randomly chosen n-bit string, then the probability that A outputs an x’ such that f(x) = f(x’) is less than or equal to a negligible function of n. – Keshav Srinivasan Nov 1 '20 at 19:16
• This doesn't seem like a useful definition. What about $f$ that ignores its input and returns a random $\kappa$-bit string? Is that "probabilistically one way"? – Mikero Nov 1 '20 at 19:43
• No, because then any string x’ would be a valid inversion. Maybe I should rephrase as, “the probability that A outputs an x’ such that f(x) is a possible output of f when applied to input x’ is less than or equal to a negligible function of n”. – Keshav Srinivasan Nov 1 '20 at 19:46
• In either case it would appear that you can construct a deterministic one-way function by considering the randomness as part of the input. If this function were not one-way, you could find $(x',r')$, such that $F(x',r')=F(x,r)$. This would also allow you to break the one-wayness of the probabilistic function. – Maeher Nov 1 '20 at 20:33

Let's look at the definition in the linked thesis:

Definition 2.2.2 (probabilistic one-way function). A probabilistic function, $$F$$ (with randomness domain $$R_n$$), with a corresponding deterministic verifier, $$V_F$$ , is called one-way with respect to a well-spread distribution, $$\mathbb{X}$$, if for any PPT, $$A$$: $$\Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(A(F(x, r)), F(x, r)\bigr) = 1\bigr] < \mu(n).¹$$ $$F$$ is called one-way if it is one-way with respect to the uniform distribution.

I will assume, since you did not specify anything about the distribution, that we are looking at the uniform distribution.

This definition is a bit problematic since it does not contain any kind of correctness guarantee for the verifier. In particular, take any function $$F$$ and define $$V_F$$ to be the constant $$0$$ function. According to the definition above the pair $$(F,V_F)$$ is one-way. Clearly this is not what was meant.

Definition 2.5.1 defines efficient verifiability, though this definition doesn't quite fit for a one-way function as defined above since it talks about an ensemble of keyed functions. However, in the same spirit, I will assume that Definition 2.2.2 meant to require the following from $$F$$:

Definition (Effcient Verification). A function, $$F$$ satisfies efficient verification if there exists a deterministic polynomial time algorithm, $$V_F$$, such that: $$\forall x \in X_n, r \in R_n, V_F(x, F(x, r)) = 1.$$

If that is the case then the following holds.

Theorem Let $$F : X_n \to Y_n$$ be a probabilistic one-way function with randomness domain $$R_n$$. Then the deterministic function $$G : X_n \times R_n \to Y_n$$ defined as $$G(x,r)=F(x,r)$$ is a deterministic one-way function.

Proof. Let $$A$$ denote an arbitrary PPT algorithm such that $$\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)] =\epsilon(n).$$ Note, that since the distribution over $$X_n$$ is uniform it holds that \begin{align} \epsilon(n) = &\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)]\\ =&\Pr[x \gets X_n, r\gets R_n, G(A(G(x,r))) = G(x,r)]\\ =&\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)] \end{align} where the last equality follows by the definition of $$G$$.

Now, consider the PPT algorithm $$B$$ that upon input $$y$$, executes $$(x',r')\gets A(y)$$ and outputs $$x'$$. By the definition of efficient verifiability, for all $$x,x'\in X_n$$, $$r',r \in R_n$$ it must hold that $$F(x',r') = F(x,r) \implies V_F(x',F(x,r))=1.$$ Thus, \begin{align} \epsilon(n) = &\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]\\ \leq & \Pr[x \gets X_n, r\gets R_n, V_F(B(F(x,r)),F(x,r))=1] \leq \mu(n), \end{align} where the last inequality follows from the assumption that $$F$$ is a probabilistic one-way function.

Since the above holds for arbitrary PPT $$A$$, the theorem statement follows. $$\quad\quad\Box$$

¹Where $$\mu$$ denotes an unspecified negligible function.