Question: 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](http://groups.csail.mit.edu/cis/pubs/lysyanskaya/cl02a.pdf) Strong-RSA Dynamic Accumulators).

Answer: 
Another (naive) solution:

Take you favourite (cryptographic) hash function $H$. For an element $x \in \{0,1\}^\*$, define $H'(x)$ as the first prime number in the $H$-orbit of $x$. That is, 

\begin{align\*}
& n\_x := \min \{n:\ H^{(n)}(x) \text{ is prime} \} ; \\
& H' (x) := H^{(n\_x)}(x),
\end{align\*}
where $H^{(n)}(x)$ is the $n$-fold iteration $(H\circ ... \circ H)(x)$. The function $H'$ is collision and pre-image resistant assuming $H$ is, and it attains prime values. However, it is not *very* efficiently computable. 

Runtime analysis (in the random oracle model): by the [Prime number theorem](https://en.wikipedia.org/wiki/Prime_number_theorem), the expectation of $n\_x$ (regardless of x) is the number of bits. That is, if you are using SHA-256, then in expectation it would take you 256 guesses to find a prime number. To check primality, you can use the probabilistic [Miller-Rabin](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) that runs in $\log^2(x)$, or the deterministic [AKS](https://en.wikipedia.org/wiki/AKS_primality_test) algorithm that (conjecturely) runs in $\log^6(x)$.
**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](https://www.wolframalpha.com/input/?i=Prime%5B2%5E512%5D) $\text{Prime}[2^{512}]$ at WolframAlpha.