Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
- 講者Eli Goldin 先生 (紐約大學)
邀請人：鐘楷閔 - 時間2023-07-04 (Tue.) 10:15 ~ 12:00
- 地點資訊所新館101演講廳
摘要
Suppose we have two hash functions $h_1$ and $h_2$, but we trust the security of only one of them. To mitigate this worry, we wish to build a hash combiner $C^{h_1, h_2}$ which is secure so long as one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash function outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08) showed no (noticeably) shorter combiner for collision resistance is possible.
In this work, we revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many interesting applications of cryptographic hash functions anyway. We argue the right formulation of the ``hash combiner'' is to build what we call random oracle (RO) combiners, utilizing stronger assumptions for stronger constructions.
Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner $$[@BackSlash]tilde{C}_{z_1, z_2}^{h_1,h_2}(M) = h_1(M, [@BackSlash]z_1) [@BackSlash]xor h_2(M, z_2),$$ where $z_1, z_2$ are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound.
On the negative side, we show that one cannot generically apply the composition theorem to further replace ``monolithic'' hash functions $h_1$ and $h_2$ by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Finally, despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where $h_1$ and $h_2$ are replaced by iterative Merkle-Damgård hashes applied to a fixed-length compression function. Thus, we can still subvert the concatenation barrier for collision-resistance combiners while utilizing practically small fixed-length components underneath.
In this work, we revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many interesting applications of cryptographic hash functions anyway. We argue the right formulation of the ``hash combiner'' is to build what we call random oracle (RO) combiners, utilizing stronger assumptions for stronger constructions.
Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner $$[@BackSlash]tilde{C}_{z_1, z_2}^{h_1,h_2}(M) = h_1(M, [@BackSlash]z_1) [@BackSlash]xor h_2(M, z_2),$$ where $z_1, z_2$ are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound.
On the negative side, we show that one cannot generically apply the composition theorem to further replace ``monolithic'' hash functions $h_1$ and $h_2$ by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Finally, despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where $h_1$ and $h_2$ are replaced by iterative Merkle-Damgård hashes applied to a fixed-length compression function. Thus, we can still subvert the concatenation barrier for collision-resistance combiners while utilizing practically small fixed-length components underneath.