Proof of Storage

因为公司有一个合作项目牵涉到，这几天抽空看了一下proof of storage的paper，复习了一下本科学的密码学的内容，觉得还是一个很有意思的topic。其中一个reference挺难找的，记在这里吧。下面讨论的原理还是基于大整数的分解问题。

 

http://diswww.mit.edu/bloom-picayune/crypto/13190

 

Adi Shamir once proposed the following hash function:

     Let n = p*q be the product of two large primes, such that
     factoring n is believed to be infeasible.

     Let g be an element of maximum order in Z_n^* (i.e. an
     element of order lambda(n) = lcm(p-1,q-1)).

     Assume that n and g are fixed and public; p and q are secret.

     Let x be an input to be hashed, interpreted as a
     non-negative integer.  (Of arbitrary length; this may be
     considerably larger than n.)

     Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

     hash(x) = hash(x')

which implies that

     x - x' = k * lambda(n)

for some k.  That is a collision implies that you can find a
multiple of lambda(n).  Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

         Cheers,
         Ron Rivest


Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel [phone], Fax [phone], Email <[e-mail]>