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?
1 Answer
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}$$
-
$\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$ Commented Jun 12, 2016 at 10:43
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$– e-sushiCommented Jun 12, 2016 at 14:56