The Complexity of Collision-Resistant Hashing
| 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.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.identifier.uri | https://hdl.handle.net/1813/14136 | |
| dc.language.iso | en | en_US |
| dc.title | The Complexity of Collision-Resistant Hashing | en_US |
| dc.type | report | en_US |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- removed.html
- Size:
- 606 B
- Format:
- Hypertext Markup Language
- Description:
- This item removed at the request of the author.