I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers? Obviously I'd like it to be collision resistant and all that, but this project is huge, I'm alone and I'm confident someone else in the field will pick up from there. Also, primality tests are linear in n or what? Thanks
Thank you for your answers but I think I found a better method.
- Take the hash of your input $h(x)$, preferably with random oracle approximation
- Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
- Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
- Write to memory: $H(x)=p$
The random oracle makes collisions infeasible
Universal hashing gives high density of primes with high probability (there is a theorem out there but the principle is that, for a given prime, I have multiple hash outputs, so the probability that one of them is my input increases. See: Gennaro et al. - Secure hash-and-sign signatures without the Random Oracle, lemma 2)