Unavoidable regularities in long words with bounded number of symbol occurrences

DOI10.1007/S10878-012-9450-6MaRDI QIDQ386431zbMATH OpenOpenAlexFDO

Authors Juha Kortelainen, Tuomas Kortelainen, Ari Vesanen

Publication date 9 December 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-012-9450-6

zbMATH Keywords

generalized iterated hash functionsmulticollision attackspermutationsunavoidable regularities

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15) Cryptography (94A60)

Review text

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).

Recommendations

• Unavoidable regularities in long words with bounded number of symbol occurrences
• Unavoidable regularities and factor permutations of words
• On Unavoidable Sets of Word Patterns
• Tower-type bounds for unavoidable patterns in words
• Unavoidable sets of words of uniform length
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• On the number of words with restrictions on the number of symbols
• Words with unbounded periodicity complexity
• On long words avoiding Zimin patterns
• On Long Words Avoiding Zimin Patterns

Cites work

• Advances in Cryptology – CRYPTO 2004
• Binary equality sets are generated by two words
• Breaking the ICE – Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions
• Constructing an Ideal Hash Function from Weak Ideal Compression Functions
• Herding, second preimage and Trojan message attacks beyond Merkle-Damgård
• scientific article; zbMATH DE number 3578341 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1259068 (Why is no real title available?)
• scientific article; zbMATH DE number 3435566 (Why is no real title available?)
• Intricacies of simple word equations: an example
• Local and global cyclicity in free semigroups
• Multicollision attacks and generalized iterated hash functions
• Multicollision Attacks on Some Generalized Sequential Hash Functions
• On highly palindromic words
• On the relation between periodicity and unbordered factors of finite words
• Rational languages and the Burnside problem
• Some applications of a theorem of Shirshov to language theory
• The Ehrenfeucht-Silberger Problem

Cited in

(3)

• Combinatorics on words in information security: unavoidable regularities in the construction of multicollision attacks on iterated hash functions
• Unavoidable regularities in long words with bounded number of symbol occurrences
• On Long Words Avoiding Zimin Patterns

This page was built for publication: Unavoidable regularities in long words with bounded number of symbol occurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386431)