Amplifying Collision Resistance: A Complexity-Theoretic Treatment Export

@misc{citeulike:3138370, abstract = {Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. We measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. The goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. We provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense.}, author = {Canetti, Ran and Rivest, Ron and Sudan, Madhu and Trevisan, Luca and Vadhan, Salil and Wee, Hoeteck}, citeulike-article-id = {3138370}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.6405}, posted-at = {2008-08-20 03:13:42}, priority = {2}, title = {Amplifying Collision Resistance: A Complexity-Theoretic Treatment}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.6405} }

TY - ELEC ID - citeulike:3138370 L3 - citeulike-article-id:3138370 N2 - Abstract. We initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. We measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. The goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. We provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense. TI - Amplifying Collision Resistance: A Complexity-Theoretic Treatment AU - Canetti, Ran AU - Rivest, Ron AU - Sudan, Madhu AU - Trevisan, Luca AU - Vadhan, Salil AU - Wee, Hoeteck UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.6405 ER -