Name
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 restritced 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 m2q-1 and satifies the following: If a 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 πA(α) ∈ aσ1(1)+...aσ1(m)+aσ2(1)+...aσ2(m)+...aσp(1)+...aσp(m)+. Here A = {a1, a2, . . . , am} and πA is the projection morphism from alph(α)* into A*. Finally, we demonstrate how problems such as the one above are connected to constructing multicollision attacks on so called generalized iterated hash functions. |
Year | DOI | Venue |
|---|---|---|
2011 | https://doi.org/10.1007/s10878-012-9450-6 | Journal of Combinatorial Optimization |
Keywords | DocType | Volume |
Combinatorics on words,Unavoidable regularities,Hash function,Multicollision,Security property | Conference | 26 |
Issue | ISSN | Citations |
4 | 1382-6905 | 1 |
PageRank | References | Authors |
0.36 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juha Kortelainen | 1 | 63 | 13.05 |
| Tuomas Kortelainen | 2 | 19 | 3.73 |
| Ari Vesanen | 3 | 4 | 1.85 |