Title: Randomized Stopping Times and Provably Secure Pseudorandom Permutation Generators
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 [15] 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.
Publication Year: 2017
Publication Date: 2017-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot