# Is there any pseudorandom function that outputs $n$ prime number of ring $Z_{N}$ where $N$ is Paillier public key

Let's assume $N$ is Paillier encryption public key, where $N=pq$ and $p,q$ are strong prime numbers.

I have a set of plaintext $p_i$ whose domain is $N$. I want to deterministically generate a series of pseudorandom values $r_i$ that have multiplicative inverse. So $r_i$ should be distributed uniformly random over $N$ or its subfield.

I want to blind each plaintext as $b_i=p_i\cdot r_i \bmod N$. So given $b_i$ a semi-honest adversary cannot learn anything about $p_i$.

Question: Is there any way to construct a pseudorandom function that outputs uniformly random values over $N$ (or its subfield) and has multiplicative inverse with a high probability?

• I can't do the maths right now, but any random value should have super high probability of being invertible. – SEJPM Aug 5 '16 at 12:37
• @SEJPM In that ring? – user153465 Aug 5 '16 at 12:51
• @SEJPM $\phi(N)$: the number of invertible elements? – user153465 Aug 5 '16 at 13:11

To understand this, first remember the criterion for a value $x$ to be multiplicatively invertible in $\mathbb Z_n$: $$\gcd(n,x)=1$$
Now remember how many such values exist, exactly: $$\varphi(n)=(p-1)(q-1)=pq-p-q+1$$
Now assume these non-invertible values are distributed somewhat uniformly over the set of all integers smaller than $n$. Then the chance that a value is invertible is exactly $$\Pr[x\in \mathbb Z_n:\exists x^{-1}]=\frac{\varphi(n)}{n}=\frac{pq-p-q+1}{pq}=1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq}$$
Now remember that $p,q$ are large (otherwise the encryption could be broken), then $1/p,1/q$ and $1/(pq)$ are negligible and thus the probability of an integer being invertible is nearly 1.
As for constructing such values: Just generate bit strings of the appropriate size and discard them until they fit your limitations (e.g. $\leq n$), usually you will have to discard none or one integers this way.