4
$\begingroup$

I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is expected to have collision in $\sqrt{\frac{\pi}{2}\times 2^n}$ iterations. I can't find it, anyone has the reference?

$\endgroup$
  • 6
    $\begingroup$ hal.archives-ouvertes.fr/inria-00075445/document $\endgroup$ – SEJPM May 18 '17 at 12:26
  • $\begingroup$ boss, thanks. Is it that trivial? why the downvote $\endgroup$ – Antonis Paragas May 18 '17 at 12:58
  • $\begingroup$ @AntonisParagas don't take the down-votes personally. Many people are too lazy to answer / comment to correct you. For me - what do you mean "expected to have collision"? Though - nice reading from SEJPM $\endgroup$ – gusto2 May 18 '17 at 13:36
  • $\begingroup$ Dropped an upvote... for whatever that's worth. $\endgroup$ – e-sushi May 18 '17 at 14:14
  • $\begingroup$ haha cheers, i was just wondering if it was out of line or something $\endgroup$ – Antonis Paragas May 18 '17 at 14:44
5
$\begingroup$

The paper you are looking for is:

"Random Mapping Statistics" by Flajolet and Odlyzko, first published in Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434.

It is freely available via SpringerLink and via Archives-Ouvertes (PDF).

The relevant statistic you are looking for is probably the rho-length, which specifies the specifies the average length of a cycle to be $\sqrt{\pi n/2}$ where $n=2^k$ in your case.

The abstract reads as:

Random mappings from a finite set into itself are either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the analysis of algorithms at large. This paper introduces a general framework in which the analysis of about twenty characteristic parameters of random mappings is carried out: These parameters are studied systematically through the use of generating functions and singularity analysis. In particular, an open problem of Knuth is solved, namely that of finding the expected diameter of a random mapping. The same approach is applicable to a larger class of discrete combinatorial models and possibilities of automated analysis using symbolic manipulation systems (“computer algebra”) are also briefly discussed.

$\endgroup$

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.