Is there some provably secure hash function to prime numbers?
Say, a function $H: \{0, 1\}^* \rightarrow \{e: e \in \{0, 1\}^\lambda \land e$ is prime$\}$

I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).

  • 1
    Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^{128}$ or $2^{512}$ or ... prime numbers. and, link to free version of the article? – kelalaka Oct 10 at 11:37
  • 2
    Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice? – SEJPM Oct 10 at 12:59
  • 1
    What's not fulfilled by taking a standard hash $H'$ with $\lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved. – fgrieu Oct 10 at 13:02
  • 1
    @fgrieu In general I can construct collision resistant hah functions where it's easy to find inputs that map to "close" images, say differing only in the least significant bit. Those would trivially lead to collisions with high probability in your approach. (It might be fine assuming a random oracle, but it's definitely not assuming collision resistance.) – Maeher Oct 10 at 17:51
up vote 17 down vote accepted

You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).

The usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.

Generally the method of generating the prime value is available separately in math or crypto libraries that come with the runtime. For instance, Java has the BigInteger(int bitLength, int certainty, Random rnd) constructor.

Beware that the time it takes to find a prime is unknown in advance. The generation may take a long time (and in the case of Java may also take a ridiculous number of bytes from the DRBG - just tested this).

  • 2
    Note : java isProbablePrime(int certainty): may return composite number. The AKS algorithm may needed – kelalaka Oct 10 at 20:03
  • @Maarten_Bodewes I feel like the consequtive hash values will find the same prime number due to the prime number gap. Could you elobarate this point? – kelalaka Oct 10 at 20:07
  • 2
    Generally a difference in seed to a PRNG will result in a completely different random stream. So I'm not sure what you mean with comment #2. As for comment #1, yes, the Java example uses Rabin-Miller and Lucas-Lehmer to test if a number probable prime. If a more conclusive test is needed for a specific problem then a different test method should be used. – Maarten Bodewes Oct 10 at 21:02
  • Ah, hash -> CSPRNG -> prime number generator. Ok. thanks. – kelalaka Oct 10 at 21:07
  • 2
    Note that Java does a non-strong Lucas test, not a Lucas-Lehmer test. The code comments and internal function names have been wrong since at least 2002, though this doesn't impact the results. [The Lucas test as noted in the 1980 BPSW papers is a different test than the Lucas-Lehmer test which only applies to Mersenne numbers] – DanaJ Oct 12 at 0:36

I think what makes this difficult is the definition of "secure." Clearly $H(m)=2$ always outputs a prime number, but it is not considered secure.

For it to be "secure," one would expect every prime number to have an equal probability of being chosen, given a random input. Since you can enumerate the prime numbers below a certain value, the problem is isomorphic to a "normal" hash which generates an integer from 0..$\pi(2^\lambda)$ where $\pi$ is a function which counts the number of primes up to a certain value. If you can demonstrate that your normal hash generates unpredictable results with a uniform distribution, then your proof is complete.

However, finding a function for the first $\pi(2^\lambda)$ primes is tricky, especially if $\lambda$ is large.

Potentially of interest is a paper by Jones, Sato, Wada, and Weins from 1976. In it, they produced a fascinating polynomial of degree 25 in 26 variables which yields a prime number, 1, or a negative number for all non-negative integers. Interestingly, it also generates every prime number, so it is guaranteed to contain all $\pi(2^\lambda)$ primes you want.

Of course, that is a 26 variable function, and it makes no guarantees about repeating prime numbers in a non-uniform distribution. But you could in theory find a loop through these numbers which generates every prime number you want. If you could do some massaging to get it into the form of a cyclic group, you could rapidly index through it and generate such numbers efficiently.

However, I do believe that, even if creating such a cyclic group is possible, it would likely require an amount of initial effort proportional to $\pi(2^\lambda)$ at the least. The result might be nice and compact, but generating it would be abysmal.

Generating prime numbers by an equation is fascinatingly difficult. While there is, in theory, a polynomial time solution to your problem, it's not clear how to efficiently determine what that is.

  • 1
    The equation by Jones, Sato, Wada, and Weins, while interesting from a theoretic point of view, is unusable to the problem for searching for prime numbers, as almost all input variable settings will result in a negative number – poncho Oct 10 at 21:06
  • 1
    @poncho True. The challenge would be finding a loop through it which doesn't have negative numbers. I do think the reality is that this isn't a practical task, but what I liked about those equations is they at least showed that, in theory, some of these issues are bounded by polynomials. – Cort Ammon Oct 10 at 23:32
  • I'm very interested whether this diophantine representation was ever used actually. Maybe I should fork a separate question for this. Idea is having a witness in the form of two 26-tuples for an RSA modulus, that could be proven. – Vadym Fedyukovych Oct 13 at 17:04

This answer updated since new foundings

Let $H$ be a (provably) secure hash function $H:\{0,1\}^* \rightarrow \{2^h\}$, where $h$ is the output size of the $H$.

Now, using this $H$, we will construct a (provably) secure hash function to primes $H'$ as follows;

  • let $P$ be Oracle of Mathematica Prime[n] function.
  • given message $m$ output;

$$H'(m) := \text{Prime}[H(m)]$$

Since this is just a bijection, $H'$ is a (provably) secure hash function.

Note: I looked for the theory of this Prime[n] function but couldn't. The Mathematica find the $n-th$ prime very quickly. Try $\text{Prime}[2^{512}]$ at WolframAlpha.

  • 2
    One may want to note that this is ver much unpractical because of the list of size $2^{h}$ especially if $h$ should have cryptographically interesting values such as $h=256$. – SEJPM Oct 10 at 12:37
  • 1
    $i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't? – fgrieu Oct 10 at 12:52
  • 1
    This answer assumes you can find a provably secure hash function. Nobody have found such a hash function yet. – kasperd Oct 10 at 16:36
  • 1
    @kasperd, I wrote as if you gave me one, I can convert it. Martin solved my solution's weak point. – kelalaka Oct 10 at 19:16
  • 1
    It seems Mathematica's Prime[n] function stops giving exact results around 310e9. Using primecount or Perl/ntheory one can go significantly farther, but still nowhere near far enough, and 2^512 is completely infeasible. For the methods used, see for example math.stackexchange.com/a/775314/117584. The method used by the two mentioned packages is as described there: get a good estimate, get an exact prime count, then sieve the relatively small difference. One could iterate the process but our initial estimate is pretty good and sieving is pretty fast. – DanaJ Oct 12 at 0:19

A straightforward method to achieve this that springs to my mind is to use the Sieve of Eratosthenes to construct a list of all primes $p$ such that $p < 2^\lambda$. Given this list/set $P$, perform a random permutation on the list and use any hash function $H$ you like and then you could compose these parts thusly to hash some value $v$: $$ PrimeHash(v) = P[H(v)\mod |P|\ ]$$

This is obviously memory intensive, and computationally intensive, but assuming that this will be used many times, the initial complexity of the Sieve's construction may be amortized. My main motivation for bringing it up is to give a brief, intuitive, and hopefully instructive construction of the desired functionality.

  • 1
    I suspect that this will not be usable for primes of the size useful to cryptography. – Ella Rose Oct 11 at 19:29
  • Yes, I absolutely agree. As I mentioned, it was meant to be more of an instructive/intuitive exercise rather than practical proposition. – Ken Goss Oct 11 at 20:14

Relatively prime polynomials are as good as prime numbers sometimes*. In such a case, $(1 + ex) \in Z[X]$ are prime for just different $e$ produced with the hash function (collision resistance).

[*] Set equality testing is an obvious example: just compare two products of polynomials accumulating set elements. Efficient polynomial equality test is crucial, resulting in a nice proof of having a solution to specific sudoku puzzle. Polynomial graph representation and isomorphism testing is another example.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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