1
$\begingroup$

Assume two servers $(n=2)$ use the same domain curve parameters and same hash function $H:\{0,1\}^{*} \rightarrow G_{1}$ .
Then the hash value for the same identity falls in same result and let it be P by assuming $P \in G_{1}$. Then the probability for the same private key depends on secret value $a,b \leftarrow Z_{q}$ where q is a large prime number and (a) and (b) be the master secret value of two servers.
In this scenario, the probability of $(a=b)$ can be $\frac{1}{q}$ or calculated using birthday problem?
In elliptic curve with field order 512 bits, then q=170 bits
According to simple probability
$p(n)=\frac{1}{q}=\frac{1}{2^{170}}$, the probability does not depend on $(n)$.
According to birthday problem,
$p(n)=1-\frac{q!}{q^{n}(q-n)!}$
substituting value for (n=2) (q=$2^{170}$), then the probability will be 0.1.
Which one is correct?

$\endgroup$
1
$\begingroup$

Both are correct, you've just made an error calculating it.

Here is a simplification from my answer here:

$$\begin{eqnarray} p(n) & = & 1 - \frac{q!}{q^n\left(q-n\right)!}\\ & = & 1 - \frac{\prod^q_{i=q-n+1}i}{q^n}\\ & = & 1 - \prod^q_{i=q-n+1}\frac{i}{q} \end{eqnarray}$$

So,

$$\begin{eqnarray} p(2) & = & 1 - \prod^q_{i=q-2+1}\frac{i}{q} \\ & = & 1 - \prod^q_{i=q-1}\frac{i}{q} \\ & = & 1 - \frac{q-1}{q}\cdot \frac{q}{q} \\ & = & 1 - \frac{q-1}{q} \\ & = & 1 - (\frac{q}{q} - \frac{1}{q}) \\ & = & \frac{1}{q} \approx 0. \end{eqnarray}$$

$\endgroup$
  • $\begingroup$ $$\begin{eqnarray} & = & 1 - (\frac{q}{q} - \frac{1}{q}) \\ & = & \frac{1}{q} \approx 0. \end{eqnarray}$$ As I calculated the parenthesis first. $\frac{q-1}{q}$ That is why I got (1-0.9=0.1) $\endgroup$ – La Yate May Jun 12 '16 at 10:43
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jun 12 '16 at 14:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.