0
$\begingroup$

In order to use RSA accumulator the elements must be primes. Is there examples of collision resistant hash functions with prime domain?

$\endgroup$
0
$\begingroup$

You can use Hash(element:nonce) then increment nonce until the result is prime. Check section 7 "Hashing To Primes" of paper "Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains"

Hash() can be SHA256 for example.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Suppose you have a PPT algorithm $M(1^n;r)$ that given the length of your target prime and the randomness $r\in\{0,1\}^{\rho(n)}$ finds a prime of length $n$. Suppose further $M$ is secure in the sense that if you feed it a properly random input $r$ it will output an unpredictable, random prime suitable for use in say RSA. Most cryptographic libraries have an implementation of this.

Suppose further you have a PRG $G:\{0,1\}^l\to\{0,1\}^{p(l)}$ that given a properly random string as input outputs a (much) longer random-looking string as output. This is e.g. realized by using something like AES-CTR with the input being the key and using a fixed nonce.

Then take any hash function that can reasonably be modelled as a random oracle $O:\{0,1\}^*\to\{0,1\}^l$, e.g. SHA3. The defining feature of a random oracle is that you get fresh randomly drawn values as output for every fresh input value.

Now construct your hash as follows: $P_n(x)=M(1^n;G(O(x)))$. Assuming you can securely generate RSA keys this will also be secure (as long as $x$ is unnpredictable).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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