0
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ What's your definition of a probabilistic one-way function? $\endgroup$
    – Maeher
    Nov 1 '20 at 19:08
  • $\begingroup$ @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. $\endgroup$ Nov 1 '20 at 19:16
  • 2
    $\begingroup$ 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"? $\endgroup$
    – Mikero
    Nov 1 '20 at 19:43
  • $\begingroup$ 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”. $\endgroup$ Nov 1 '20 at 19:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – Maeher
    Nov 1 '20 at 20:33
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.