Unavoidable regularities in long words with bounded number of symbol occurrences

Juha Kortelainen (), Tuomas Kortelainen and Ari Vesanen
Additional contact information
Juha Kortelainen: University of Oulu
Tuomas Kortelainen: University of Oulu
Ari Vesanen: University of Oulu

Journal of Combinatorial Optimization, 2013, vol. 26, issue 4, No 4, 670-686

Abstract: Abstract Traditionally in combinatorics on words one studies unavoidable regularities that appear in sufficiently long strings over a fixed size alphabet. Inspired by permutation problems originating from information security, another viewpoint is taken in this paper. We focus on combinatorial properties of long words in which the number of occurrences of any symbol is restricted by a fixed given constant. More precisely, we show that for all positive integers m and q there exists the least positive integer N(m,q) which is smaller than $m^{2^{q-1}}$ and satisfies the following: If α is a word such that (i) |alph(α)|≥N(m,q) (i.e., the cardinality of the alphabet of α is at least N(m,q)); and (ii) |α| a ≤q for each a∈alph(α) (i.e., the number of occurrences of any symbol of alph(α) in α is at most q), then there exist a set A⊆alph(α) of cardinality |A|=m, an integer p∈{1,2,…,q}, and permutations σ 1,σ 2,…,σ p :{1,2,…,m}→{1,2,…,m} for which $$\pi_A(\alpha)\in a_{\sigma_1(1)}^+\cdots a_{\sigma_1(m)}^+a_{\sigma _2(1)}^+\cdots a_{\sigma_2(m)}^+\cdots a_{\sigma_p(1)}^+\cdots a_{\sigma_p(m)}^+ .$$ Here A={a 1,a 2,…,a m } and π A is the projection morphism from alph(α)∗ into A ∗. The second part of the paper considers information security. We give an introduction to (generalized iterated) hash functions and their security properties; finally we demonstrate how our combinatorial results are connected to constructing multicollision attacks on these functions.

Keywords: Combinatorics on words; Unavoidable regularities; Hash function; Multicollision; Security property (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9450-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:4:d:10.1007_s10878-012-9450-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9450-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().