2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ the possibility of two users choosing the same $r$ may not be negligible - just this is not enough - one of those 2 users will have to know which of the other has the same $r$ $\endgroup$
    – user93353
    Aug 27, 2022 at 6:35
  • $\begingroup$ How big is your $r$? For typical public key schemes the domain of $r$ is huge, curve25519 has $r$ of 256 bits. If you're sampling $r$ from a cryptographically secure PRG then getting the same $r$ is negligible. $\endgroup$
    – lamba
    Aug 27, 2022 at 6:42
  • $\begingroup$ Funnily enough, for Elliptic Curves the best algorithm for solving the DLP is actually a disguised collision search (Pollard Rho or vOW). If you are sampling r so that g^r is uniformly distributed (I.e. r sampled uniformly at random from Z_|G|) then an algorithm that just generates users will find a collision after asymptotically the same number of steps as it takes solving the DLP. With the difference that in the first case you have to store a laaarge table of users and in Pollard Rho instead use constant memory. Both cases are O(sqrt|G|) time complexity $\endgroup$
    – WizardOfMenlo
    Aug 27, 2022 at 20:28
  • $\begingroup$ This is the same question as if two people accidentally have the same cryptographic hash somehow right? $\endgroup$
    – qwr
    Aug 28, 2022 at 3:34
  • 1
    $\begingroup$ There are only about $2^{33}$ people on Earth. In cryptography, that is generally considered a small number. $\endgroup$
    – Ilmari Karonen
    Aug 28, 2022 at 9:57

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Keyword: birthday problem? $\endgroup$
    – qwr
    Aug 28, 2022 at 3:35

Your Answer

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

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