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}$

  • 2
    $\begingroup$ Are you asking what "o.w." might mean ("otherwise")? Or, are you asking for the value what would appear in place of "?" ? $\endgroup$ – poncho Jan 5 '19 at 20:45
  • 2
    $\begingroup$ 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 $\endgroup$ – poncho Jan 5 '19 at 20:52
  • 1
    $\begingroup$ Thanks a lot, $r_i$s are from a uniformly distributed set, and we want to compute what value apear in place of '?'. $\endgroup$ – rafael Jan 5 '19 at 21:48
  • 1
    $\begingroup$ 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. $\endgroup$ – kodlu Jan 6 '19 at 1:41
  • 1
    $\begingroup$ 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$? $\endgroup$ – poncho Jan 7 '19 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.