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 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(2q-1) and satisfies the following: If alpha is a word such that (i) vertical bar alph(alpha vertical bar >= N(m, q) (i.e., the cardinality of the alphabet of alpha is at least N(m, q)); and (ii) vertical bar alpha vertical bar(a) <= q for each a is an element of alph(alpha) (i.e., the number of occurrences of any symbol of alph(alpha) in a is at most q), then there exist a set A subset of alph(alpha) of cardinality vertical bar A vertical bar = m, an integer p is an element of {1, 2,...,q}, and permutations sigma(1), sigma(2),...,sigma(p) : {1, 2,...,m} -> {1, 2,..., m} for which pi(A)(alpha) is an element of a(sigma 1(1))(+) ... a(sigma 1(m))(+)a(sigma 2(1))(+) ... a(sigma 2(m))(+) ... a(sigma p(1))(+) ... a(sigma 1(m))(+). Here A = {a(1), a(2),..., a(m)} and pA is the projection morphism from alph(alpha)* 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10878-012-9450-6 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Keywords | DocType | Volume |
Combinatorics on words,Unavoidable regularities,Hash function,Multicollision,Security property | Journal | 26 |
Issue | ISSN | Citations |
SP4 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juha Kortelainen | 1 | 0 | 0.34 |
| Tuomas Kortelainen | 2 | 19 | 3.73 |
| Ari Vesanen | 3 | 4 | 1.85 |