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: 
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.
**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.