Paper 2016/1049

Randomized stopping times and provably secure pseudorandom permutation generators

Michal Kulis, Pawel Lorek, and Filip Zagorski

Abstract

Conventionally, key-scheduling algorithm (KSA) of a cryptographic scheme runs for predefined number of steps. We suggest a different approach by utilization of randomized stopping rules to generate permutations which are indistinguishable from uniform ones. We explain that if the stopping time of such a shuffle is a Strong Stationary Time and bits of the secret key are not reused then these algorithms are immune against timing attacks. We also revisit the well known paper of Mironov~\cite{Mironov2002} which analyses a card shuffle which models KSA of RC4. Mironov states that expected time till reaching uniform distribution is $2n H_n - n$ while we prove that $n H_n+ n$ steps are enough (by finding a new strong stationary time for the shuffle). Nevertheless, both cases require $O(n \log^2 n)$ bits of randomness while one can replace the shuffle used in RC4 (and in Spritz) with a better shuffle which is optimal and needs only $O(n \log n)$ bits.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. Proceedings of Mycrypt 2016: Paradigm-shifting Crypto
Contact author(s)
filip zagorski @ pwr edu pl
History
2016-11-07: received
Short URL
https://ia.cr/2016/1049
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1049,
      author = {Michal Kulis and Pawel Lorek and Filip Zagorski},
      title = {Randomized stopping times and provably secure pseudorandom permutation generators},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1049},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1049}},
      url = {https://eprint.iacr.org/2016/1049}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.