Use of eCommons for rapid dissemination of COVID-19 research
In order to maximize the discoverability of COVID-19 research, and to conform with repository best practices and the requirements of publishers and research funders, we provide special guidance for COVID-19 submissions.
The Complexity of Collision-Resistant Hashing
|dc.contributor.author||Tseng, Wei-Lung Dustin|
|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. 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.||en_US|
|dc.title||The Complexity of Collision-Resistant Hashing||en_US|