Unavoidable regularities in long words with bounded number of symbol occurrences (Q386431)

Motivated by information security applications, the authors study the structure of permutations in sufficiently long words over an alphabet of a fixed size. They focus on combinatorial properties when the number of occurrences of each symbol is bounded by a fixed constant. In particular, they study the types of unavoidable regularities that can appear under these conditions. They also show how their results in combinatorics on words are connected to the construction of muticollision attacks on generalized iterated hash functions. For the Proceedings version see Lect. Notes Comput. Sci. 6842, 519--530 (2011; Zbl 1295.68177).