ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

On the Speed of VSH

Speaker: Sebastiaan de Hoogh
Date, Time: Mon, 17 Sep 2007 10:00

Some important security schemes, such as Digital Signature Schemes, rely on cryptographic hash functions that are collision resistant. It is known that the most common hash functions, such as SHA1 and MD5, do not satisfy this property. Moreover, as cryptanalysts are advancing the methods for finding collisions for this type of hash functions, one might consider hash functions that are provable collision resistant. In 2005, Contini, Steinfeld and Lenstra introduced the Very Smooth Hash (VSH) that is the first provable collision resistant hash function (based on the hardness to factor large numbers) that is getting close to being practical. One of the problems of VSH is that it has a relatively long running time with respect to the common hash functions.

In this talk, we will show how to improve the speed of VSH by about 75% by means of smart implementations and by means of using a less conservative security assumption. In addition, we will present an implementation of VSH based on trapdoor information that makes VSH three times faster. Lastly, we show that advances in integer factorization are less of a problem for VSH than they are for RSA. Specifically, increasing the size of the modulus results in only a linear slowdown for VSH, as opposed to a cubic (in practice) slowdown for RSA.

Back to the top of this page