=Paper=
{{Paper
|id=None
|storemode=property
|title=On Existence of Robust Combiners for Cryptographic Hash Functions
|pdfUrl=https://ceur-ws.org/Vol-584/paper10.pdf
|volume=Vol-584
|dblpUrl=https://dblp.org/rec/conf/itat/Rjasko09
}}
==On Existence of Robust Combiners for Cryptographic Hash Functions==
https://ceur-ws.org/Vol-584/paper10.pdf
On existence of robust combiners for cryptographic hash functions?
Michal Rjaško
Department of Computer Science, Faculty of Mathematics, Physics and Informatics,
Comenius University, Bratislava
rjasko@dcs.fmph.uniba.sk
Abstract. A (k, l)-robust combiner for collision resistant combination remains secure. For collision resistance
hash functions is a construction, which takes l hash func- we can achieve this by concatenation. Let H1 , H2 :
tions and combines them so that if at least k of the compo- {0, 1}∗ → {0, 1}v be some hash functions. We can con-
nents are collision resistant, then so is the resulting com- struct a hash function H, where
bination. A black-box (k, l)-robust combiner is robust com-
biner, which takes its components as black-boxes. A trivial H(M ) = H1 (M )||H2 (M ).
black-box combiner is concatenation of any (l−k +1) of the
hash functions. Boneh and Boyen [1] followed by Pietrzak Note, that if (M, M 0 ) is a pair of colliding messages
[3] proved, that for collision resistance we cannot do much for H, then this pair collides also for H1 and H2 .
better that concatenation, i.e. there does not exist black box Therefore if at least one of the H1 and H2 is collision
(k, l)-robust combiner for collision resistance, whose output resistant, then H is collision resistant too. However
is significantly shorter that the output of the trivial com- this approach has one important disadvantage – the
biner. In this paper we analyze whether robust combiners output length of H is twice as large as the output of
for other hash function properties (e.g. preimage resistance underlying hash functions H1 and H2 , what can lead
and second preimage resistance) exist.
to problems with practical implementation, mainly on
Key words: Cryptographic hash function, robust com-
biner, preimage resistance, second preimage resistance
devices with small amount of memory as smart-cards.
Thus the question is, whether one can construct
a secure combiner with output shorter than the con-
1 Introduction catenation. Boneh and Boyen in [1] proved the first
negative result in this direction, in particular that
Cryptographic hash functions play important role in there does not exist secure combiner for collision resis-
the current cryptography. In the last few years, many tant hash functions with output shorter than concate-
attacks on popular hash functions believed to be se- nation, with an assumption, that the combiner queries
cure (e.g. SHA1, MD5) have been proposed. Within each hash function exactly once. This result was gen-
these attacks arises a question, whether we are able eralized by Pietrzak [3], where the author proved that
to construct a secure hash function. A hash function the secure combiners for collision resistance with sig-
is a function H : {0, 1}∗ → {0, 1}v , which maps mes- nificantly shorter output than concatenation do not
sages (strings of 0 and 1) of arbitrary length to strings exist. The later work consider a (k, l)-robust combin-
of fixed length – called images. Practically useful hash ers for collision resistant, which are secure if at least k
functions must guarantee several security properties: of the l components are secure.
they should be collision resistant, what means that it In this paper we follow the work of Pietrzak [3] and
is hard to find two different messages which map to prove the similar results for other important proper-
the same image. Other important properties of hash ties of hash functions – second preimage resistance and
functions are preimage resistance (for given image, it is preimage resistance. We define a (k, l) combiner for
hard to find its preimage, i.e. a message which maps to preimage resistance and second preimage resistance
that image) and second-preimage resistance (for given and for these definitions we prove the impossibility
message, it is hard to find another message, which results similar to one from [3].
maps to the same image). For formal definitions of the Organization In the section 2 we start by some
properties mentioned above or other notions of hash useful notation and continue with the formal defini-
function security we refer to the works [4], [5]. tions of (k, l) combiners for collision resistance, preim-
Natural way how to construct secure hash func- age resistance and second-preimage resistance. In the
tion is to combine several known (regarded to be se- section 3 we prove the negative results, namely in the
cure) hash functions in such a way, that if one of Theorem 1 we prove that secure combiner for preim-
the combined functions appears to be insecure, the age resistance with output significantly shorter than
?
This paper was supported by VEGA grant number concatenation does not exists and in the Theorem 2
1/0266/09 and by Comenius University grant number we prove the similar result for second-preimage resis-
UK/365/2009. tance.
72 Michal Rjaško
2 Preliminaries The security of combiner (with respect to some se-
curity notion) is determined by the number how many
In this section we formally define a combiner of l hash of the candidate hash functions need to be secure in
functions for three notions of hash function security order to guarantee that the resulting combiner is se-
– collision resistance, preimage resistance and second cure. By (k, l)-combiner (C, P ) we denote the com-
preimage resistance. The definition of the combiner biner (C, P ), which is secure, if at least k of the l
for collision resistance is from [1], the other definitions candidate hash functions are secure.
(i.e. for preimage and second-preimage resistance) are We expect from all candidate hash functions Hi to
slight modification of the former one. have the same output length v. We assume this just
$ for simplicity, our results can be easily extended for
We start with some basic notation. We write M ←S
for the experiment of choosing random element from variable output length of these candidate hash func-
the distribution S. If S is a finite set, then M is chosen tions.
uniformly from S. Concatenation of finite strings M1 In this paper we deal only with black box combin-
and M2 we denote by M1 ||M2 or simply M1 M2 . ers, what means that the combination algorithm (C)
An oracle turing machine T with oracle access to has only black box (i.e. oracle) access to the candi-
turing machines T1 , . . . , Tl is a turing machine, which date hash functions. It does not know the structure of
accepts inputs via input tape, performs some compu- underlying primitives H1 , . . . , Hl .
tation and replies via output tape. During the com- We start by formal definition of the combiner for
putation it can write on some additional “oracle” in- collision resistance from [3].
put tapes t1 , . . . , tl and recieves responses via oracle
output tapes t01 , . . . , t0l – connections to the turing ma- 2.1 Combiner for collision resistance
chines T1 , . . . , Tl . Whenever T writes some input on
tape ti , the turing machine Ti is run on that input and A collision resistant (k, l)-combiner for l hash func-
T recieves the output on tape t0i . We call such a opera- tions H1 , . . . , Hl is a pair (C, P ) of oracle turing ma-
tion a query to oracle Ti . All queries are performed in chines C and P , where
unit time (i.e. computation of Ti is not counted into
the running time of T ). By T T1 ,...,Tl we denote that – C : {0, 1}m → {0, 1}n has oracle access to hash
the oracle turing machine T has oracle access to the functions H1 , . . . , Hi and performs the “combina-
turing machines T1 , . . . , Tl . tion” of hash functions. On input it takes a mes-
Let λ be some parameter. In this section, and later, sage of fixed length m and outputs an image of
by Hi we denote a function mapping from {0, 1}∗ to fixed length n. The output of C on an input M
{0, 1}v , where i = 1 . . . l and v = p(λ) for some polyno- and with oracle access to H1 , . . . , Hl is denoted as
mial p. In general, a combiner of l hash functions Hi , C H1 ,...,Hl (M ).
i = 1, . . . , l for some notion of hash function security – P is an oracle machine, which provides a “proof”
is a pair (C, P ), where of security for C. It takes as input a pair of mes-
sages (M, M 0 ) and outputs two vectors
– C : {0, 1}m → {0, 1}n does the “combination”
(m = pm (λ) and n = pn (λ) for some polynomi- W = (w1 , . . . , wl ) and W0 = (w10 , . . . , wl0 ).
als pm , pn ), i.e. it is an oracle turing machine with
oracle access to H1 , . . . , Hl . It behaves as a stan- The role of the algorithm P is to transform the
dard hash function (i.e. it takes some message on collision in C to collisions in at least l − k + 1 of the
input and outputs a hash of the message – string underlying hash functions H1 , . . . , Hl . If such a P ex-
of fixed length), but during the computation it can ists, which transforms collisions in C to collisions in Hi
query any of its oracles. for all compatible H1 , . . . , Hl , then we consider C as
– P provides a proof of the security for C. It is an al- a collision resistant (k, l) combiner. Now, we formally
gorithm, which transforms the “ability” of break- define what was discussed above.
ing the C (with respect to the particular security We say that P k succeeds on H1 , . . . , Hl , M and
property) to the ability of breaking the candidates. M 0 if:
∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 :
We note that both C and P should be efficient –
they run in a time that is polynomial in the security (∀j ∈ J) : (wj , wj0 ) is a collision for Hj
parameter λ (and thus it is polynomial also in m, n (i.e. Hj (wj ) = Hj (wj0 ))
or v). The oracle turing machine C is the same for
combiners of all security notions. On the other hand, Let Coll[k]
AdvP [(H1 , . . . , Hl ), M, M 0 ]
P needs to be modified when going from one security
notion to another. denote the probability that P k-succeeds.
Combiners for cryptographic hash functions 73
We say that (C, P ) is ε-secure (k, l)-Coll-combiner, 3. A message M = f (Y ), is given to P (note
if for all H1 , . . . , Hl and all collisions (M, M 0 ) in C we that C H1 ,...,Hl (M ) = Y ), if f (Y ) = ⊥, then
have: the game ends and P fails.
Coll[k]
4. P continues (still can query H1 , . . . , Hl ) and
AdvP [(H1 , . . . , Hl ), M, M 0 ] ≥ 1 − ε outputs a vector W = (w10 , . . . , wl0 ).
We consider (C, P ) to be secure (k, l)-Coll-combiner,
We note, that the function f , which parametrizes
if ε is negligible in the security parameter λ.
the Pre-Comb game can be understood as a deter-
For example, a secure (1, 2)-combiner for collision
ministic “device”, which finds preimages in C (it need
resistance can look like follows:
not to be efficient). An algorithm P from a secure
– C H1 ,H2
(M ) = H1 (M )||H2 (M ) preimage resistant combiner should win the Pre-Comb
– P H1 ,H2 0
(M, M ) = (M, M ), (M, M )0 game for all possible functions f (or at least for non-
negligible part of such functions, however in this paper
The turing machine C just passes its input to the can- we consider combiners to be secure if they win for all
didates and returns the concatenation of their output. possible f s).
Note that collision in C implies collision in both H1 We say that P k succeeds on H1 , . . . , Hl , y1 , . . . , yl
and H2 . In more detail, if (M, M 0 ) is a collision for and f if:
such a C, then (M, M 0 ) is also a collision in both H1
and H2 . Thus P has easy work – it copies its input to
∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 :
the output. It is easy to see, that for all H1 , H2 and
0
all collisions (M, M ) in C is
(∀j ∈ J) : wj0 is preimage of yj on Hj
Coll[1]
AdvP [(H1 , H2 ), M, M 0 ] = 1.
(i.e. Hj (wj0 ) = yj )
Therefore (C, P ) is 0-secure (1, 2)-Coll-combiner.
Let
2.2 Combiner for preimage resistance Pre[k]
AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ]
The combiner for preimage resistance is similar to one
denote the probability that P k-succeeds.
for collision resistance. Only difference is in the al-
Finally, (C, P ) is ε-secure (k, l)-Pre-combiner, if for
gorithm P , which provides “a proof of the security“.
all H1 , . . . , Hl , all images y1 , . . . , yl and all possible f
Algorithm P is given on its input challenge images
we have:
y1 , . . . , yl of H1 , . . . , Hl , for which it has to find preim-
ages. It plays a game, in which it chooses an image of C Pre[k]
for which it gets a preimage. AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] ≥ 1 − ε
A preimage resistant combiner for l hash functions
We say (C, P ) is secure (k, l)-Coll-combiner, if ε is neg-
H1 , . . . , Hl is a pair (C, P ) of oracle turing machines C
and P , where ligible in the security parameter λ.
For example consider the following (1, 2)-combiner
– C : {0, 1}m → {0, 1}n is the same as in the colli- for preimage resistance:
sion resistant combiner.
– P is an oracle turing machine, which provides – C H1 ,H2 (M1 ||M2 ) = H1 (M1 ) || H2 (M2 ) – C gets
a “proof” of security for C. It plays the following a message on its input, divides it into two parts
game. Let f : {0, 1}n → {0, 1}m ∪ {⊥} be a func- of roughly equal length and passes these two parts
tion, such that for all Y ∈ {0, 1}n is f (Y ) = M , to H1 and H2 .
for which C H1 ,...,Hl (M ) = Y . If such a M does not – P – given images y1 , y2 on input, P computes the
exists, then f (Y ) = ⊥. image Y = y1 ||y2 and returns it in the second step
of the Pre-Comb game. In turn P receives a mes-
Pre-Combf game: sage M , where C H1 ,H2 (M ) = Y . Finally P divides
m
1. Messages w1 , . . . , wl ∈ {0, 1} are chosen at the message M into two parts w1 and w2 (exactly
random, then images y1 = H1 (w1 ), . . . , yl = as C divides its input) and returns (w1 , w2 ).
Hl (wl ) are computed and given to P on its
input. Since C H1 ,H2 (w1 ||w2 ) = H1 (w1 )||H2 (w2 ), we can see
2. P with oracle access to H1 , . . . , Hl outputs that H1 (w1 ) = y1 and H2 (w2 ) = y2 . Thus (C, P ) is
some image Y ∈ {0, 1}n . 0-secure (1, 2)-Pre-combiner.
74 Michal Rjaško
2.3 Combiner for second-preimage resistance It is easy to see,
Here we define a combiner for second-preimage re- C H1 ,H2 (M 0 ) = H1 (M 0 )||H2 (M 0 )
sistance. Again, only difference from combiners for = H1 (M )||H2 (M )
preimage or collision resistance is in the algorithm P .
= C H1 ,H2 (M ),
A second-preimage resistant combiner for l hash
functions H1 , . . . , Hl is a pair (C, P ) of oracle turing thus H (M 0 ) = H (M ), H (M 0 ) = H (M ).
1 1 2 2
machines C and P , where
– C : {0, 1}m → {0, 1}n is the same as in the case of 3 Impossibility proofs
preimage resistant or collision resistant combiner.
– P is an oracle turing machine, which provides Boneh and Boyen [1] followed by Pietrzak [3] showed,
a “proof” of security for C. It plays the following that there does not exist a collision resistant (k, l)
game. Let f : {0, 1}m → {0, 1}m ∪ {⊥} be a func- combiner with short output. In this section we prove
tion, such that for all M ∈ {0, 1}m is f (M ) = M 0 , the similar results for preimage resistance and second-
for M 0 6= M and C H1 ,...,Hl (M ) = C H1 ,...,Hl (M 0 ).
preimage resistance.
If such a M 0 does not exist, then f (M ) = ⊥. The impossibility result for preimage resis-
tant combiners is given in the Theorem 1, and in the
Sec-Combf game: Theorem 2 is given the impossibility result for second-
1. Message w ∈ {0, 1}m is chosen at random and preimage resistance.
given to P on its input. We start by notation used in the rest of this paper.
2. P with oracle access to H1 , . . . , Hl outputs Let (C, P ) be some combiner and let:
some message M ∈ {0, 1}m .
3. P is given a message M 0 = f (M ) (M 0 6= M – Wi (M ) be the set of oracle queries to Hi made
and C H1 ,...,Hl
(M ) = C H1 ,...,Hl 0
(M )). while evaluating C H1 ,...,Hl on the message M
4. P continues (still can query H1 , . . . , Hl ) and – Vi (M ) = {Hi (M ); M ∈ Wi (M )} be the set of
0 0
outputs a vector (w1 , . . . , wl ). corresponding answers.
– wi,j (M ) be the j-th query to Hi made while eval-
We say that P k succeeds on H1 , . . . , Hl , w and f uating C H1 ,...,Hl (M ) and vi,j (M ) be the corre-
if: sponding answer.
∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : To simplify the presentation we will assume that
(∀j ∈ J) : wj0 is second-preimage of w on Hj P can output only messages that it has queried during
the game. Note that we can assume this without loss
(i.e. Hj (wj0 ) = Hj (w) and wj0 6= wj ) of generality.
Now, let Theorem 1. Let (C, P ) be a (k, l)-combiner for pre-
image resistance, where C can make at most qC oracle
Sec[k]
AdvP [(H1 , . . . , Hl ), w, f ] queries. Suppose, that
denote the probability that P k-succeeds. n < (v − lg(qC ))(l − k + 1) − l
Finally, (C, P ) is ε-secure (k, l)-Sec-combiner, if for
all H1 , . . . , Hl , all messages w and all possible f we Then there exist y1 , . . . , yl , H1 , . . . , Hl and f , such that
have: Pre[k]
AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] is negl. in λ
Sec[k]
AdvP [(H1 , . . . , Hl ), w, f ] ≥ 1 − ε
Proof. Let H1 , . . . , Hl : {0, 1}∗ → {0, 1}v be all uni-
And we say (C, P ) is secure (k, l)-Coll-combiner, if ε is formly random hash functions. Let qP be the total
negligible in the security parameter λ. number of queries that P makes in the Pre-Comb game
Consider the following example of secure (1, 2) and let y1 , . . . , yl be the challenge images that P gets
combiner for second-preimage resistance: in the first step of the game. From the fact, that P runs
in a polynomial time we have that qP = p(λ) for some
– C H1 ,H2 (M ) = H1 (M )||H2 (M ) polynomial p. Therefore the probability that P queries
– P – on input w in the second step of the Sec-Comb any Hi with some message w, such that Hi (w) = yi ,
game P returns a message M = w. In turn P is negligible in λ. To see this only a simple idea is
receives a message M 0 6= M , where C H1 ,H2 (M 0 ) = needed. All of the Hi s are random thus the probabil-
C H1 ,H2 (M ). Finally P returns a vector (M 0 , M 0 ). ity that P gets output yi for some i = 1, . . . , l in one
Combiners for cryptographic hash functions 75
query is l/2v . The probability that P queries yi for query each Hi with qi distinct inputs. Now we follow
some i in qP queries is therefore the same steps as Pietrzak [3] did in the proof of the
similar theorem for collision resistant combiner.
l l
qP v = p(λ) p0 (λ) ,
2 2 Pr[E2 ] ≤ Pr[AH1 ,...,Hl finds l − k + 1 preimages]
X
what is negligible in λ. ≤ Pr[∀i ∈ J : A finds preimage for yi ]
Thus P ’s only chance to win is in the message M J⊆{1,...,l}
|J|=l−k+1
it gets as a preimage for the image Y chosen in the X Y qi
second step of the Pre-Comb game. We show, that if ≤
n < (v − lg(qC ))(l − k + 1) − l, then there exist images 2v
J⊆{1,...,l} i∈J
y1 , . . . , yl , and a function f such that for all images Y |J|=l−k+1
which P can output in the second step, evaluating of X l−k+1
qC
C(f (Y )) does not present a preimage for at least k of <
2v(l−k+1)
the y1 , . . . , yl . This means, that for such H1 , . . . , Hl , J⊆{1,...,l}
|J|=l−k+1
y1 , . . . , yl and f is µ ¶ l−k+1 l−k+1
l − k + 1 qC 2l qC
Pre[k] ≤ v(l−k+1)
< v(l−k+1)
AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] l 2 2
negligible in λ, what we want to prove. When we put everything together:
Let H1 , . . . , Hl be as defined above (independent
random hash functions) and let Y ∈ {0, 1}n be some lg(Pr[E1 ]) ≥ lg(2−n ) = −n
image of C H1 ,...,Hl . Consider the following random ex-
periment. First, images y1 , . . . , yl ∈ {0, 1}v are chosen and
at random and then a message M ∈ {0, 1}m is ran- µ l l−k+1 ¶
2 qC
domly chosen. Now consider the following events: lg(Pr[E2 ]) < lg v(l−k+1)
2
E1 ⇐⇒ C H1 ,...,Hl (M ) = Y = (−(v − lg(qC ))(l − k + 1) + l).
E2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k :
Thus if n < (v − lg(qC ))(l − k + 1) − l we have Pr[E1 ] >
∀j ∈ J : yj ∈ Vj (M ) Pr[E2 ], what we wanted to prove.
Note that if Pr[E1 ] > Pr[E2 ]. then Pr[E1 ∧¬E2 ] > 0, ¤
what means, that there exist images y1 , . . . , yl ∈ {0, 1}v
such that for each Y ∈ {0, 1}n there exists a message The condition n < (v−lg(qC ))(l−k+1)−l gives the
M ∈ {0, 1}m for which C H1 ,...,Hl (M ) = Y and the lower bound how short can be the output of a secure
evaluation of C H1 ,...,Hl (M ) does not present preim- (k, l)-Pre-combiner. It looks rather unnatural, how-
ages for y1 , . . . , yl . In other words, it means that there ever if C is allowed to query each Hi exactly once
exist images y1 , . . . , yl and a function f 1 for which the and we consider only (1, l)-combiners (what means,
theorem holds. that a combiner is secure if at least one of the candi-
We know that for particular Y and randomly cho- dates is secure) then the condition can be rewritten to
sen M is n < (v − 1)l.
We note, that this lower bound need not to be
Pr[C H1 ,...,Hl (M ) = Y ] ≥ 2−n . optimal – maybe there exists a higher lower bound. We
leave such an analysis for future work. Similar analysis
Thus for collision resistant combiners can be found in the
Pr[E1 ] ≥ 2−n . work [2].
To find Pr[E2 ], let qi be the number of queries to Hi
Pl Theorem 2. Let (C, P ) be a (k, l)-combiner for
made by C (note that i=1 qi = qC ). The Pr[E2 ] can
2nd-preimage resistance, where C makes at most
be upper bounded by the probability that the best or-
qC oracle queries. Suppose, that
acle algorithm AH1 ,...,Hl , which is allowed to query Hi
at most qi times finds a preimage for at least l − k + 1
n < (v − lg(qC ))(l − k + 1) − l + 1
of yi (A can evaluate C H1 ,...,Hl and then A’s success
probability is equal to Pr[E2 ]). Since Hi are all inde- Then there exist w, H1 , . . . , Hl and f , for which
pendent random functions, the best A can do is to
Sec[k]
1
for each Y we set f (Y ) to the corresponding message M AdvP [(H1 , . . . , Hl ), w, f ] is negligible in λ
76 Michal Rjaško
Proof. The proof is very similar to one in the Theo-
rem 1, therefore we provide just a sketch of the proof. µl−k+1 ¶
Let H1 , . . . , Hl be all independent random hash func- 2l qC
lg(Pr[E2 ]) < lg
tions. We claim, that the probability where P queries 2v(l−k+1)
a second-preimage of w for at least one of the Hi is = −(v − lg(qC ))(l − k + 1) + l.
negligible. This is due the fact, that P runs in a poly-
nomial time and therefore it can make at most polyno- Thus if n < (v − lg(qC ))(l − k + 1) − l + 1 we have
mial number of queries, what is not enough for winning Pr[E1 ] > Pr[E2 ], what we wanted to prove.
against random functions (for more formal discussion ¤
see the similar part in the proof of the Theorem 1).
Therefore we only need to prove that if n < (v −
lg(qC ))(l − k + 1) − l + 1, then there exist a message w 4 Conclusion
and a function f , where for all messages M that P can
output in the second step of the Sec-Comb game eval- We proved that combiners for preimage resistance and
uation of C(f (M )) does not present a second preimage second-preimage resistance with output (significantly)
of w for at least k of the H1 , . . . , Hl . shorter than concatenation do not exist. Our results
Thus let H1 , . . . , Hl be as defined above and let are similar to ones for collision resistance from [1]
M ∈ {0, 1}m be some message. Consider the random and [3]. In particular, we showed that one can not cre-
experiment, where w ∈ {0, 1}m and M 0 ∈ {0, 1}m are ate a secure (k, l)-combiner (for some mentioned secu-
chosen uniformly at random. We define the following rity notion) of l arbitrary hash functions, with output
events E1 and E2 : shorter than concatenation of l − k + 1 candidates.
These results are, however, too strict in a point,
E1 ⇐⇒ M 0 6= M ∧ C H1 ,...,Hl (M ) = C H1 ,...,Hl (M 0 ) that we want from a combiner to work for all l-tuples
E2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k : (∀j ∈ J)(∃i) : of (compatible) hash functions and that the al-
vj,i (M 0 ) = Hj (w) ∧ wj,i (M 0 ) 6= w gorithm P providing the proof of combiner’s security
must succeed with non-negligible probability on all
In other words, E1 is the event when M 0 is the possible inputs. Such a condition is not very practi-
second-preimage of M in the sense of C H1 ,...,Hl and cally relevant – one can think of creating a combiner,
E2 means that the evaluation of C H1 ,...,Hl (M 0 ) does which combines only hash functions from some subset
presents at least l − k + 1 second-preimages for w. of all hash functions (e.g. set of functions computable
Again, if we prove that Pr[E1 ] > Pr[E2 ], then Pr[E1 ∧ in polynomial time). Another way how to weaken the
¬E2 ] > 0, what means that for each M the above restrictions on combiners is to allow the algorithm P
w1 , . . . , wl and M 0 exist and therefore there exists to fail on negligible part of inputs. We leave the analy-
a function f (we set f (M ) := M 0 ) for which the the- sis of such “weaker” combiners for a future work.
orem holds (together with w1 , . . . , wl ).
Now, since m > n
References
Pr[E1 ] = 2−n − 2−m ≥ 2−n−1
1. D. Boneh and X. Boyen: On the impossibility of ef-
Now, let qi be the maximum number of queries ficiently combining collision resistant hash functions.
to Hi made by C. We can upper bound Pr[E2 ] by the LNCS, 4117, 2006.
probability that the best oracle algorithm A which can 2. R. Canetti, R. Rivest, M. Sudan, L. Trevisan, S. Vad-
query each Hi at most qi times finds second-preimage han and H. Wee: Amplifying collision resistance:
of w for at least l−k+1 of the Hi s. However H1 , . . . , Hl a complexity-theoretic treatment. LNCS, 4622, 2007.
3. K. Pietrzak: Non-trivial black-box combiners for
are all independent random functions, thus the best A
collision-resistant hash-functions don’t exist. LNCS,
can do is to query each Hi on qi distinct inputs dif-
4515, 2007.
ferent from w. If we follow the steps as in the corre- 4. P. Rogaway and T. Shrimpton: Cryptographic hash-
sponding part of the proof of the Theorem 1 we get function basics: definitions, implications, and separa-
l−k+1 tions for preimage resistance, second-preimage resis-
2l qC tance, and collision resistance. In Fast Software Encryp-
Pr[E2 ] < v(l−k+1)
2 tion, LNCS, Springer, 3017, 2004, 371–388.
5. M. Rjaško: Properties of cryptographic hash functions.
When we put everything together:
Mikulášska Kryptobesı́dka, 2008.
lg(Pr[E1 ]) ≥ lg(2−n−1 ) = −n − 1
and