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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Just two servers are enough to have a "possibility" of identical keys. $\endgroup$– fkraiemCommented Apr 20, 2016 at 6:10
-
$\begingroup$ fkraiem. Please explain it to me. $\endgroup$– La Yate MayCommented Apr 20, 2016 at 6:24
-
$\begingroup$ Well, what if $s = b$? $\endgroup$– fkraiemCommented Apr 20, 2016 at 6:25
-
$\begingroup$ The probability for s=b is high or low? $\endgroup$– La Yate MayCommented Apr 20, 2016 at 6:25
-
$\begingroup$ I do not know what it mean for a probability to be "hard" or "easy". $\endgroup$– fkraiemCommented Apr 20, 2016 at 6:26
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
10
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$.
-
$\begingroup$ ArtjomB. Can that probability cause weak security? $\endgroup$ Commented Apr 20, 2016 at 9:59
-
2$\begingroup$ 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. $\endgroup$– fgrieu ♦Commented Apr 20, 2016 at 10:03
-
$\begingroup$ @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. $\endgroup$ Commented Apr 20, 2016 at 10:08
-
$\begingroup$ fgrieu. What about the case of IBE servers that are not well-behaving? In such cases, security risk? $\endgroup$ Commented Jun 11, 2016 at 15:44
-
$\begingroup$ @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. $\endgroup$ Commented Jun 11, 2016 at 15:50