4
$\begingroup$

Can I assume this? Specifically, I want to know if the following two cases are valid. Suppose $prf_k(m)=c$

  1. One-wayness: Only given $c$, we cannot reveal $m$.
  2. Without key $k$, even given $m$, cannot get $c$.

They seem intuitive, but I want to be assured of their validity when I say that. Is a pseudorandom function also a one-way function?

$\endgroup$
  • 1
    $\begingroup$ are you given the key $k$ in the first one? The second one should hold. $\endgroup$ – SEJPM Oct 20 '15 at 21:21
  • $\begingroup$ No, you don't have the key $k$. $\endgroup$ – cryptodog Oct 20 '15 at 21:53
  • 1
    $\begingroup$ In this case you shouldn't be able to distinguish prf from a random function and you can't find the input faster than brute-force. $\endgroup$ – SEJPM Oct 20 '15 at 21:55
  • 3
    $\begingroup$ @SEJPM A small mistake: PRF security doesn't guarantee that you won't be able to find the input faster than brute-force. It simply state that there exists no polynomial-time algorithm that will be able to distinguish between the PRF and a random function. Note that there might be a subexponential algorithm (which will be much faster than brute-force) that might be able to distinguish and even retrieve the key, and the PRF will be considered secure nevertheless. $\endgroup$ – DiG Oct 21 '15 at 18:46
4
$\begingroup$

(Note the OP's clarification that even for 1, the adversary does not have the key k.)

Yes. $\:$ The way to show anything like those, is to use the fact that oracle access to prfk
is sufficient to efficiently determine the extent to which an adversary is violating those.

def straight-line_reduction_1_():
 m = random_element_of_(domain(F))
 query F on m
 let c be the output of F on m
 send c to inner_adversary_1
 forward any queries and responses between inner_adversary_1 and the F oracle
 let guess be the output of inner_adversary_1 on c
 if guess == m:
  return True
 else:
  return False

straight-line_reduction_1_ uses only a small amount of space and makes only one more oracle query than inner_adversary_1, and straight-line_reduction_1_'s runtime is dominated by forwarding queries/responses from/to inner_adversary_1. ​ (So, straight-line_reduction_1_
is efficient.) ​ For all F, the probability of straight-line_reduction_1_ outputting True is equal
to the probability of inner_adversary_1 correctly guessing m given c. ​ However, if F is a
truly random function and inner_adversary_1 makes at most q queries, then the probability
of inner_adversary_1 correctly guessing m given c is at most (q+1)/(cardinality(domain(F))).
(That should be proven, but I'll only bother doing so if you ask.)
Given that result (which I didn't provide a proof of), it then follows that the probability of inner_adversary_1 correctly guessing m given c by making at most q queries is at most (q+1)/(cardinality(domain(F))) plus the extent to which the combination of inner_adversary_1
with straight-line_reduction_1_ distinguishes the function family from random.

In particular, if the function family is pseudorandom then 1 holds.

One can proceed analogously to show that
if the function family is pseudorandom then 2 also holds.

$\endgroup$
  • 1
    $\begingroup$ Thank you! though I need some time to understand the proof. $\endgroup$ – cryptodog Oct 21 '15 at 2:37
2
$\begingroup$
  1. Given c one cannot reveal m.

The statement should thus be, given $c$, any polynomial type adversary $A$ can determine $m$ with a non-negligible probability.

This is so because - anyone can brute force all possible $m$ and apply $PRF_k(m)$ and check if it equals to $c$. This might be computationally improbable (not impossible since the adversary $A$ can make a guess and get lucky).

Here are a few things to note as well. PR-functions are provable secure considering that underlying assumptions that some problems are hard to solve (or cannot be efficiently solved in polynomial time). Eg. discreet logarithmic problem, factorization of the product of 2 n-bit primes, subset problem. (This is not a concrete prove since hard to solve is just as assumption and one needs to prove $N != NP$ to make a concrete statement)

Also note that if the security parameter (size of $m$ and $c$) is low, them brute force attack is feasible.

This as long you have a large enough security parameter, any polynomial time adversary and a PRF that is provable secure (under the assumption on a hard problem), you can say given c, one cannot find m with high probability.

  1. Without $k$, given $m$ one cannot find $c$

Since it is a $PRF_k$, you can say that only with non-negligible probability, give a message $m$, any polynomial adversary $A$ can guess $c$.

An example of negligible probability is O($2^{-n}$) where n > 60

This should be formal enough to say (although one can always add more details).

$\endgroup$
  • $\begingroup$ Thank you very much! I think you mean "negligible" since $n>60$ $\endgroup$ – cryptodog Nov 8 '15 at 15:10
  • $\begingroup$ That's correct. Made the fix. $\endgroup$ – kung_fu_coder Nov 10 '15 at 21:53

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.