2
$\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 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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