VSH - Revision history

Mlamberger: /* Specification */

2008-03-11T10:16:56Z

‎Specification

Fmendel at 10:14, 11 March 2008

2008-03-11T10:14:08Z

Tnad: /* Spezification */

2008-03-10T15:07:56Z

‎Spezification

Mschlaeffer at 14:43, 10 March 2008

2008-03-10T14:43:29Z

Mschlaeffer at 14:42, 10 March 2008

2008-03-10T14:42:47Z

New page

== Spezification ==



== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

----

=== Others ===

@@ Line 9: / Line 9: @@
 <bibtex>
-@MISC{nistContiniLS05,
+@inproceedings{eurocryptContiniLS06,
-   author = {Scott Contini and Arjen Lenstra and Ron Steinfeld},
+   author = {Scott Contini and Arjen K. Lenstra and Ron Steinfeld},
-   title = {VSH, an Efficient and Provable Collision Resistant Hash Function},
+   title = {VSH, an Efficient and Provable Collision-Resistant Hash Function},
-   howpublished = {NIST - First Cryptographic Hash Workshop, October 31-November 1},
+   booktitle = {EUROCRYPT},
-   year = {2005},
+  year = {2006},
-   abstract = {We introduce VSH, very smooth hash, a new $S$-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an $S$-bit composite integer $n$. By very smooth, we mean that the smoothness bound is some fixed polynomial function of $S$. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in $S$. VSH is theoretically pleasing because it requires only $O(\frac{1}{S})$ multiplications modulo the $S$-bit composite $n$ per message-bit (as opposed to $\Omega(\frac{1}{\mbox{log}S})$ multiplications for previous provably secure hashes). It is also practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the diffculty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.},
+   pages = {165-182},
-   url = {http://csrc.nist.gov/groups/ST/hash/documents/LENSTRA_vsh.pdf},
+   abstract = {We introduce VSH, very smooth hash, a new S-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an S-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of S. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in S. VSH is theoretically pleasing because it requires just a single multiplication modulo the S-bit composite per Ω(S) message-bits (as opposed to O(logS) message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.},
+}
 </bibtex>

← Older revision		Revision as of 10:14, 11 March 2008
Line 45:		Line 45:

	=== Others ===		=== Others ===
		+
		+	<bibtex>
		+	@inproceedings{indocryptSaarinen06,
		+	author = {Markku-Juhani Olavi Saarinen},
		+	title = {Security of VSH in the Real World},
		+	booktitle = {INDOCRYPT},
		+	year = {2006},
		+	pages = {95-103},
		+	url = {http://dx.doi.org/10.1007/11941378_8},
		+	editor = {Rana Barua and Tanja Lange},
		+	publisher = {Springer},
		+	series = {LNCS},
		+	volume = {4329},
		+	isbn = {3-540-49767-6},
		+	abstract = {In Eurocrypt 2006, Contini, Lenstra, and Steinfeld proposed a new hash function primitive, VSH, very smooth hash. In this brief paper we offer commentary on the resistance of VSH against some standard cryptanalytic attacks, including preimage attacks and collision search for a truncated VSH. Although the authors of VSH claim only collision resistance, we show why one must be very careful when using VSH in cryptographic engineering, where additional security properties are often required.},
		+	}
		+	</bibtex>

← Older revision		Revision as of 15:07, 10 March 2008
Line 1:		Line 1:
−	== ~~Spezification~~ ==	+	== Specification ==

	<!--		<!--

@@ Line 5: / Line 5: @@
 * max. message length: < 2<sup>64</sup> bits
 * compression function: 512-bit message block, 160-bit chaining variable
 -->
 == Cryptanalysis ==