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?

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

TL;DR: Any (pseudo-) random value from the desired range has a high chance of being invertible.

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.


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.