# Computing a probability

Let $$(w_1,\cdots,w_l) \in (\{0,1\}^\lambda)^l$$, and $$r_1,\cdots,r_l$$ are chosed as uniformly random from $$Z^*_q$$ such that $$r_1+\cdots+r_l=0$$ and $$q$$ is a large prime number. Also, Let $$F$$is a pseudorandom function with key $$k$$. What value apear in place "?" in below relation (in o.w. part )?

$$Pr[F_k(w_1)\cdot r_1+\cdots+F_k(w_l)\cdot r_l=0] := \begin{cases} 1 & \text{if } (w_1=w_2=\cdots=w_l) \\ ? & \text{o.w.} \end{cases}$$

• Are you asking what "o.w." might mean ("otherwise")? Or, are you asking for the value what would appear in place of "?" ? – poncho Jan 5 at 20:45
• Also, is the computed probability over a uniformly distributed set of $r_i$ values (constrained by the specified relations), or are you looking for a relation that would hold for any set of $r_i$ values that satisfy the relation? If the latter, then we can come up with a second case ($r_1 = r_3 = 1, r_2 = r_4 = q-1$, $w_1 = w_2 \ne w_3 = w_4$ where the probability is 1 – poncho Jan 5 at 20:52
• Thanks a lot, $r_i$s are from a uniformly distributed set, and we want to compute what value apear in place of '?'. – rafael Jan 5 at 21:48
• The answer will depend very heavily on $q,$ namely its factorisation. And you have a $k$ in your definition of a random function. What is this $k$?Please enter your comments above directly into the question so it is more readable. – kodlu Jan 6 at 1:41
• It appears to be bounded by a value that is slightly larger than $2/q$, but I couldn't come up with an exact derivation. BTW: are the $r_i$ values actually chosen from $\mathbb{Z}^*_q$ (that is, the value 0 is excluded)? Or, are they chosen from $\mathbb{Z}_q$? – poncho Jan 7 at 14:47