dc.contributor.author Pass, Rafael dc.contributor.author Tseng, Wei-Lung Dustin dc.contributor.author Venkitasubramaniam, Muthuramakrishnan dc.date.accessioned 2009-10-24T20:07:11Z dc.date.available 2009-10-24T20:07:11Z dc.date.issued 2009-10-24T20:07:11Z dc.identifier.uri https://hdl.handle.net/1813/14136 dc.description Item removed from eCommons on 2010-02-21 at the request of the author. en_US dc.description.abstract A long-standing open problem on the intersection of Complexity Theory and Cryptography is whether the security of cryptographic primitives can be based on the worst-case hardness of NP. We show that, unless coNP \$\subseteq\$ AM, collision-resistant hash functions---one of the most central cryptographic primitives---cannot be based on the worst-case hardness of NP using any randomized Turing reduction; previously such separations were established only for restricted (e.g. non-adaptive) types of reductions. en_US Under an average-case strengthening of the assumption that coNP \$\not\subseteq\$ AM, we furthermore rule out generic---but potentially non-black-box---constructions of collision-resistant hash functions from one-way functions (using Turing reductions); as far as we know, this yields the first non-black-box separation between cryptographic primitives. dc.language.iso en en_US dc.title The Complexity of Collision-Resistant Hashing en_US dc.type report en_US
﻿