Paper 2010/616

A non-uniform birthday problem with applications to discrete logarithms

Steven D. Galbraith and Mark Holmes

Abstract

We consider a generalisation of the birthday problem that arises in the analysis of algorithms for certain variants of the discrete logarithm problem in groups. More precisely, we consider sampling coloured balls and placing them in urns, such that the distribution of assigning balls to urns depends on the colour of the ball. We determine the expected number of trials until two balls of different colours are placed in the same urn. As an aside we present an amusing ``paradox'' about birthdays.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Submitted to Discrete Applied Mathematics
Keywords
birthday paradoxdiscrete logarithm problem (DLP)
Contact author(s)
s galbraith @ math auckland ac nz
History
2012-02-14: revised
2010-12-08: received
See all versions
Short URL
https://ia.cr/2010/616
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/616,
      author = {Steven D.  Galbraith and Mark Holmes},
      title = {A non-uniform birthday problem with applications to discrete logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2010/616},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/616}},
      url = {https://eprint.iacr.org/2010/616}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.