1
$\begingroup$

In certificateless identity-based cryptography, selecting secret value $$x_i \in Z_p$$ and declaring public key of individual users such as $$Pub_i=g^{x_i}$$ $g$ is public parameter.
I think there will be some kind of collision in selecting secret value.
In security proof, they make assumption that secret value cannot be allowed to attackers.
Is it enough?

$\endgroup$
2
$\begingroup$

I think there will be some kind of collision in selecting secret value.

What sort of collision could there be (that has a nontrivial probability of actually happening)?

If $p$ is the order of $g$, then $Pub_i = Pub_j$ only if $x_i = x_j$. And, if $p$ is large (e.g. at least 256 bits), and we assume that $x_i, x_j$ are selected randomly and independently (that is, no one participant is allowed to peak at any of the other's secret, and they all have good entropy), then the probability of $x_i = x_j$ happening is $< 2^{-256}$, that is, mindboggling unlikely.

In fact, if we have, say 7 billion participants, and each one selects an $x_n$ randomly, the probability of there exists two different participants selecting the same value is $< 2^{-191}$, still mindboggling unlikely.

This does assume that the entropy of each participant is good; something that tends to be ignored in security proofs, but cannot be ignored when implementing the system.

In security proof, they make assumption that secret value cannot be allowed to attackers. Is it enough?

They also assume (and they ought to make it explicit) that the discrete log problem is hard; that is, given the value $g^{x_i}$, it's hard to recover $x_i$. If the group was small enough that someone would have a nontrivial probability of obtaining $x_i$, by guessing it (and computing $g^{x}$ to verify), well, that'd mean that the discrete log problem would be tractable.

$\endgroup$
  • $\begingroup$ By $2^{-256}$ you probably mean $2^{-128}$ because of the birthday problem. Also, by "nontrivial probability" you probably mean non-negligible probability. $\endgroup$ – Artjom B. Sep 16 '16 at 18:30
  • $\begingroup$ @ArtjomB.: actually, I mean $2^{-256}$; if you have a population of $2^{128}$; then the expected number of internal collisions is approximately 1; however the collision probability for two individuals who each do a single trial is, in fact, $2^{-256}$ $\endgroup$ – poncho Sep 16 '16 at 18:39
  • $\begingroup$ @poncho. How to calculate collision probability in $n$ trials for matching with any one of $m$ user? Any security weakness for large value of $m$ and $n$? $\endgroup$ – myat Sep 21 '16 at 8:11
  • $\begingroup$ @poncho. $\frac{mn}{2^{256}}$? $\endgroup$ – myat Sep 21 '16 at 8:13
  • $\begingroup$ @myat: if you have 1 trial with m users, the probability of a collision between any two of those users will be approximately $m^2/2^{257}$ (assuming $m << 2^{128})$. So, if you have n such trials, then the approximate probability of a collision happening in any of those trials would be about $n m^2 / 2^{257}$. You can do the math; I believe that for realistic $n, m$ values, this is still negligible. $\endgroup$ – poncho Sep 22 '16 at 14:43

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.