Proving the existence of a pseudorandom function I've been reading the Introduction to Modern Cryptography book by Katz and Lindell as part of my own learning and have come across this exercise which I am not sure how to approach. The exercise is: (exercise 3.8) 

Prove unconditionally the existence of an efficient pseudorandom function
$F:\{0,1\}^* \times \{0,1\}^* \mapsto \{0,1\}^*$ where the input-length is logarithmic
in the key-length (i.e., $F(k,x)$ is defined only when $|x| = log |k|$, in which
case $|F(k,x)| = |k|$).

There is also a hint which states that you should use the fact that any random function is also pseudorandom.

This is my initial train of thought:

We require the pseudorandom function to be indistinguishable from a function chosen uniformly at random from the set of functions that map $log|k|$ bit strings to $|k|$ bit strings (let's say this set is called $Func_{log\,|k|\, \mapsto |k|}$). I'm guessing that we need to work how many functions in this set in order to work out the probability of picking a random function, $f$, from this set.

I know that the set of functions $Func_{n \mapsto n}$ mapping $n$ bit strings to $n$ bit strings contains $2^{n*2^n}$ functions. However my first obstacle is calculating how many functions are in $Func_{log\,|k|\, \mapsto |k|}$ since the functions in this set are not bijective as they are in $Func_{n \mapsto n}$.

If I could calculate this value then I would approach the rest of the problem by calculating the amount of possible pseudorandom functions (clearly given by $|k|$ since $k$ is chosen uniformly at random). I was then hoping, if there was a similar number of functions in $Func_{log\,|k|\, \mapsto |k|}$ (although I speculate there is way more than $|k|$ functions in this set), then eventually try to show that it would be hard for any ppt distinguisher to tell between the pseudorandom function and the randomly chosen one. 

I have no idea if this is along the right line and I also don't really know how to bring the hint in to play. All I can think is that it may turn out to be easier to prove that $F$ is indistinguishable from another pseudorandom function which also happens to have been chosen at random.

If anyone could provide a hint as to how to calculate the amount of functions in $Func_{log\,|k|\, \mapsto |k|}$ or pointers for how to approach this then that would be great. As I said, I am doing the exercises for my own good so I'm not massively keen on being given a full solution straight away.
Though this is an 4-year old topic, it seems the following should work:

We can construct a function $F_k(x)$ with output length $l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)}$.

Didivde the key $k$ into $2^{O(\log n)}$ blocks with equal length, denoted by $k_i$ with $i=1,2,\dots, 2^{O(\log n)}$. Because $k$ is uniformly distributed in $\{0,1\}^n$, so is $k_i$. 

$F_k(x)= k_x$ is the pseudorandom function.