Crypto graphy block chain VSH method - new

VSH Method in cryptocurrency

1. VSH, an efficient and provable
collision resistant hash function
Scott Contini
1
, Arjen K. Lenstra
2
, Ron Steinfeld
1
1
Macquarie University
2
Lucent Technologies Bell Laboratories, Technical Univ. Eindhoven

2. As usual in crypto, we cheat
•Efficient means:
much faster than previous provable hashes
(preliminary result: 25  slower than SHA-1)
•Provable means:
finding collisions provably reducible to
NMSRVS: ‘non-trivial modular squareroot
of very smooth number’
(factoring experience: NMSRVS looks very hard)

3. Previous factoring based hash
•Hard to factor composite n
•Bit b: f
x
(b) = x
b
(1 if bit is off, x if bit is on)
•Bitstring B, bit b:
H
2
(B||b) = (H
2
(B)
2
 f
2
(b) ) mod n
 message m: H
2(m) = 2
m
mod n
•Slow: a squaring modulo n per message-bit
•H
2
-collision reveals information about (n)
•H
x
(x > 2) same security as H
2
(and marginally slower)

4. Speeding it up?
•Goal: a modular squaring per k message-bits
for a blocklength k substantially larger than 1
•Easy to achieve (with p(i) the i
th
prime):
–Use H
p(1) for first bit, (k+1)
th
bit, (2k+1)
th
bit, …
–Use H
p(2) for second bit, (k+2)
nd
bit, (2k+2)
nd
bit, …
–…
–Use H
p(k) for k
th
bit, 2k
th
bit, 3k
th
bit, …
–Multiply results: VSH = H
2
 H
3


…  H
p(k)
Very Smooth Hash: product of k known hashes
(this is not the way VSH was constructed)

5. Why Faster?
•As in multi-exponentiation: share the squarings
•Let b be a k-bit string, b = b(1)||b(2)||…||b(k), then:
f(b) = p(1)
b(1)
 p(2)
b(2)
 …  p(k)
b(k)

with k (130) such that 
1ik p(i) < n (1024 bit)
•Bitstring B of length multiple of k:
VSH(B||b) = (VSH(B)
2
 f(b) ) mod n
•Cost per k message-bits: computation of f(b),
plus one modular squaring and multiplication
 VSH about k/3 times faster than H
2

6. Security?
•Need p(k+1) & length before first block
•Collision does not reveal (n), but non-trivial
modular sqrt of very smooth number (NMSRVS):
x
2
 
1ik+1 p(i)
e(i)
mod n
(‘relation’ in factoring, with much larger k)
•k + t + 1 collisions lead to:
t independent 50% chances to factor n
•Owner of factorization can create collisions
(that reveal the factorization)

7. Conclusion
•VSH: Very Smooth Hash,
O(1) modular multiplies per logn message-bits
•Easy invertibility for short messages can be fixed
•k = O((logn)
c
), asymptotically: if collisions can be
found faster than factoring, then collision finder
can be turned into faster factoring algorithm
•1024-bit RSA security: >1MB/sec on 1GHz PIII
•Spin-offs: prov sec random trapdoor hash, etc.
•See eprint.iacr.org/2005/193