Best differential characteristic for this PRF Consider the following construction of a PRF $F: \{0,1\}^{128} \times \{0,1\}^{64} \to \{0,1\}^{64}$ on 64-bit messages and 128-bit keys.  Define $f:\{0,1\}^3 \to \{0,1\}$ by

$$f(c,x,y) = \begin{cases} \neg(x \land y) &amp;\text{if $c=0$}\\
\neg(x \lor y) &amp;\text{if $c=1$.} \end{cases}$$

Define an (unkeyed) round function $R_i: \{0,1\}^{1024} \to \{0,1\}^{768}$ by

$R_i(S[0..1023])$:
For $j := 0,1,2,\dots,767$, do:
&nbsp;&nbsp; $S'[j] := f(c_{i,j},S[r_{i,j}],S[r'_{i,j}])$
Return $S'[0..767]$.

Here the $c_{i,j},r_{i,j},r'_{i,j}$ are design-time constants chosen randomly at design time, from $c_{i,j} \in \{0,1\}$, $r_{i,j} \in \{0,1,\dots,1023\}$, $r'_{i,j} \in \{256,257,\dots,1023\}$.  These design-time constants are public and known to everyone.

Finally, define the PRF by:

$F(K,M)$:
$S_0 := K||M||M||K||M||M||K||M||M||K||M||M$.
For $i := 0,1,2,\dots,47$, do:
&nbsp;&nbsp;$S_{i+1} := K||M||M||R_i(S_i)$.
Return $S_{48}[256,257,\dots,319]$.

My question: What is the probability of the highest-probability differential characteristic in this PRF?  Of course the answer will depend on the random choice of the design-time constants, but I'm looking for a typical answer or "average-case" answer.  I am excluding related-key attacks, so I care about

$$\Pr[\Delta M \to \Delta Y] = \Pr_{K,M}[F_K(M) \oplus F_K(M \oplus \Delta M) = \Delta Y].$$

Is there a clean way to analyze this?

(Bonus question: are there any simple ways to decrease this probability significantly, without increasing the circuit depth of this construction?)
The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed. 

As all the values $c_{i,j}$ are public, this means that the output of the function $R_i$, and hence the function $F$ is strongly distinguishable from random (being biased towards a known bit pattern). This isn't an answer the specific question you've asked, however it would appear to be a more severe weakness than a high-probability differential would be.