TY - GEN
T1 - On the Complexity of Collision Resistant Hash Functions
T2 - 17th International Conference on Theory of Cryptography, TCC 2019
AU - Bitansky, Nir
AU - Degwekar, Akshay
N1 - Publisher Copyright:
© 2019, International Association for Cryptologic Research.
PY - 2019
Y1 - 2019
N2 - The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions. We make two contributions to this study: 1.A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way.2.New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.
AB - The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions. We make two contributions to this study: 1.A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way.2.New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.
UR - http://www.scopus.com/inward/record.url?scp=85076985101&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076985101&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-36030-6_17
DO - 10.1007/978-3-030-36030-6_17
M3 - Conference contribution
AN - SCOPUS:85076985101
SN - 9783030360290
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 422
EP - 450
BT - Theory of Cryptography - 17th International Conference, TCC 2019, Proceedings
A2 - Hofheinz, Dennis
A2 - Rosen, Alon
PB - Springer
Y2 - 1 December 2019 through 5 December 2019
ER -