Cryptography
- discrete-logarithm
- Updated Mon, 26 Sep 2022 18:24:11 GMT
-
How to prevent the solution of a discrete logarithm problem from being found in a collision way by accident
Suppose there is a popular system that is widely used by a huge amount of people. Its security protocol provides a finite group with a generator $g$, and users need to choose a random number $r$ and calculate $h=g^r$ in a certain phase. This is commonly seen in many schemes.
Since this system is widely used by many people, the possibility of two users choosing the same $r$ may not be negligible. In that case, a user may accidentally find the random number used by another person and cause some security problems.
Is this problem worth being considered? If so, is there any way to prevent it? Or, am I wrong that the probability of finding such a collision is actually negligible?
Solution
Even if all users are aware of the $h$ values of all others, avoiding collisions is not difficult, you just need to make sure the probability will be negligible.
We simply need to ensure the size of the finite group is noticeably larger than the number of usages squared.
We commonly do this over Prime fields $Z_p$ or over elliptic curves. In the former we use thousands of bits and in the latter typical sizes are hundreds of bits.
Even a modest group with order $2^{200}$ would not provide collisions even after billions of attempts. If we have $2^{33}$ attempts, one for every man woman and child on the planet we would consider collisions likely with groups of order the square of that $2^{66}$ if we go slightly larger probabilities are still possible but with lower probability. When we get to hundreds of bits this probability becomes negligble.
we can aproximate collision probability with the following formula: 1 - e-k2/2n+1 When we have k elements and a group of size $2^n$ clearly this shrinks rapidly with $n$
So to your question, secure cryptographic implementations prevent accidental collisions by using a sufficiently large group where the probability of collisions is entirely negligble even under heavy usage.