# Possibility for same Private Key Generation in identity-based encryption

In private key generation of IBE scheme, private key is generated as follows: $SK_{ID}=s.H(ID)$
Suppose two servers use the same curve domain parameters. If PKG on server A generates private key $SK_{ID}=s.H(ID)$
PKG on server B generates private key $SK_{ID}=b.H(ID)$
for the same ID.
If there are more than 100000 servers, will there be possibility for generating same private key?

• Just two servers are enough to have a "possibility" of identical keys. – fkraiem Apr 20 '16 at 6:10
• fkraiem. Please explain it to me. – La Yate May Apr 20 '16 at 6:24
• Well, what if $s = b$? – fkraiem Apr 20 '16 at 6:25
• The probability for s=b is high or low? – La Yate May Apr 20 '16 at 6:25
• I do not know what it mean for a probability to be "hard" or "easy". – fkraiem Apr 20 '16 at 6:26

I assume $s$ and $b$ are the main master secret key components of two IBE servers.

If $s=b$, then $SK_{ID,s}=SK_{ID,b}$ provided that the curve parameters and the hash function $H$ are the same. Now, the question is what's the probability of two IBE servers generating the same master secret key components. This depends on the actual scheme and the field it is defined over.

In IBE, mostly pairing-based groups are used. We usually have $s,b\in \mathbb{Z}_{r}$ where the curve is defined over $\mathbb{F}_q$. For example, $r$ is set to be a solinas prime for Type A pairing in PBC. The default values for Type A pairing are $|q|=512$ and $|r|=160$. So, the probability of at least two of $n$ servers generating the same master secret key is essentially the Birthday Problem and can be computed as such:

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

The probability is roughly $3\cdot 10^{-39}$ in your case. Here's the groovy script I calculated it with. The result is $3\cdot 10^{-42}$ under the assumption that $|r|=170$.

• ArtjomB. Can that probability cause weak security? – La Yate May Apr 20 '16 at 9:59
• The simpler approximation $p(n)\approx{n(n-1)\over2r}$ also gives $\approx3\cdot 10^{-42}$. This is negligibly low compared to the risk of destruction of human life on earth by a comet during the forthcoming year (which is considerably more than $10^{-9}$). It would follow that the short answer is: no, there is no practical risk that well-behaving IBE servers accidentally generate the same master secret key components. – fgrieu Apr 20 '16 at 10:03
• @LaYateMay No, it's incredibly unlikely to generate the same parameters. If you have doubt, then require that every IBE server generates their own curve parameters. – Artjom B. Apr 20 '16 at 10:08
• fgrieu. What about the case of IBE servers that are not well-behaving? In such cases, security risk? – La Yate May Jun 11 '16 at 15:44
• @LaYateMay If the servers are not well-behaving all bets are off. They can do anything they want including talking to each other and co-ordinate the same MSK generation. – Artjom B. Jun 11 '16 at 15:50