RSA Hash accumulator for arbitrary values


#23

So I have reinvented the wheel here. The original version of the Hash Accumulator is equivalent to Vector Commitment scheme as described in paragraph 3.2 of the below paper from Catalano and Fiore.

They describe a nice trick in paragraph 3.3 where the prime for an index is based on a random number generator. Per index they sample multiple random numbers, the first random number that is a prime, is the prime for the index. The verifier can do the same, so the verifier does not have to store all primes.
Downside is that the verifier has to check a lot of numbers for primality what could be burdensome. But we could combine this prime generation method with the trick described in this post above. Now the verifier has to generate one random number and check whether the generated number is one of the pre-committed primes.
This way the verifier can efficiently verify that a prime corresponds with a given index without storing all the primes.