Is pseudorandom function also a one-way function?

Question

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?

Answer 1

(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 prf_k
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.

Answer 2

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.

2. 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).