How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for?
Your aim is to have a number $y' = y + rn$ that gives an uniform distribution over any valid key modulus $n'$, so that no keys can be ruled out. For that, you need $y'$ to be uniformly distributed modulo a larger number. How large is the question.

If you have uniform samples from $[0, 2^l-1]$, according to this (pdf, page 20 talking about key generation, but should apply here) they are uniform (enough) modulo $n &lt; 2^k$ if $l = k + 64$. Hence, to have your $y'$ be uniform for keys up to $L$ bits you should draw $y'$ from $[0, 2^{L+64}-1]$.

Your approach gives even larger numbers ($2^{L+lg(n)} &gt; 2^{L-lg(n)+64}$ with a realistic $n$), so that part's covered, but it may leak the minimum size of $n$, since if $r = 2^L$, no key with $n'&lt;n$ could result in so high a number $y'$.

You should instead draw $r$ from $[0, 2^{L-lg(n)+64}-1]$, rounding the exponent so that $y'$ can reach $2^{L+64}-1$, then throw away those $r$ values that give you $y' &gt; 2^{L+64}-1$.

(You could find a better upper bound for that random number generation, but generating uniform random numbers that aren't modulo a power of two is itself tricky. At worst you'll be throwing away half the $r$ values, so that should be easy enough.)