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

permutationsgeneralized iterated hash functionsmulticollision attacksunavoidable regularities

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Intricacies of simple word equations: an example
• Local and global cyclicity in free semigroups
• Multicollision Attacks on Some Generalized Sequential Hash Functions
• Multicollision attacks and generalized iterated 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)

• On Long Words Avoiding Zimin Patterns
• 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

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)