Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
Please expand your question with more detail, it's hard to tell what you're asking for. Also, what does the size of the project have to do with anything? –  pg1989 Apr 16 at 3:21
    
possible duplicate of How can I generate large prime numbers for RSA? –  rath Apr 16 at 3:50
2  
@gurghet I think the question is how to deterministically and efficiently map a given interger to a prime such that you can safely accumulate it in an RSA based accumulator? –  DrLecter Apr 16 at 5:16
3  
Hashing to primes is easy. Just seed a PRNG with the hash of the input and use it to generate a prime with any standard algorithm. –  CodesInChaos Apr 16 at 7:09
1  
Welcome to Cryptography Stack Exchange. From your answer, it seems like you have some more needs which are not clearly stated in the question. Maybe you could expand your question a bit? –  Paŭlo Ebermann Apr 18 at 13:50

1 Answer 1

up vote 1 down vote accepted

Thank you for your answers but I think I found a better method.

  1. Take the hash of your input $h(x)$, preferably with random oracle approximation
  2. Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
  3. Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
  4. Write to memory: $H(x)=p$

Done!


notes:

  1. The random oracle makes collisions infeasible

  2. 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)

share|improve this answer
    
What is $k$? Why the universal hashing function? I don't see how this is "better" than the standard PRNG method CodesInChaos suggested in the comments. –  Thomas Apr 16 at 7:46
    
Why $h(x)$? If this works there are only $k$ bits to play with in step 2. Thus only $2^k$ tests in the worst case. –  gurghet Apr 16 at 7:52
    
k is just a small int. The random oracle protects me from collisions @Thomas –  gurghet Apr 16 at 7:53
    
@gurghet Again, what advantage does this scheme have over using a PRNG? You can't claim it's "better" without giving any explanation, you should elaborate so future people reading this can understand why. –  Thomas Apr 16 at 8:24
2  
You state without reference "Universal hashing gives high density of primes with high probability". I fail to see why, and doubt it. And I fail to see why it would matter, for the input of the universal hash is prime in your method, not the output. -- Trying $p$ until $f(p)=h(x)$ is expected to require $2^{w-1}$ steps where $w$ is the output width of $h$, and thus impractical. -- The method outlined by CodesInChaos seems just fine to me. –  fgrieu Apr 16 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.