Keyed digest function with odds of collision below the birthday bound?
Quite a difficult question. What you seem to need is a one-way permutation $P$. Indeed, suppose you have it of width $d$, then consider the function
$$
F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S))),
$$
where $E$ is any good 64-bit block cipher (say, Simon) and $K_1,K_2$ are derived from $K$.  This function $F$ should fulfill (2) because of the encryptions of both sides and (4) because it is a permutation. To satisfy (1) and (3) the permutation $P$ must be moderately easy to compute and difficult to invert.

It is quite hard to construct such permutations on so small domains as 48-64 bits. There are so called trapdoor permutations, which are easily invertible given a secret $K'$. However, this secret can probably be found very quickly in this domain, whether we talk about RSA or HFE.

I would consider algebraic constructions. There are some interesting permutations that have a compact description but no trapdoors, hence usually overlooked by cryptographers. For instance, how about
$$
\left(X^{2^k}+X+a\right)^{s}+X
$$
 over  $\mathbb{F}_{2^n}$ from a 2010 paper? Here $a$ is a field element, and $s,k$ are integers; restrictions on them are given in the paper. Even though I am not aware of any inversion algorithm, some generic methods like Groebner basis algorithms may find a preimage faster than $2^n$. In this case, if the permutation is fast enough, you may iterate it several times as long as you still conform to property (1).