Formal security of recycled random blinding in a Paillier scheme This question is a follow-up/variant on a previous question.

Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the costly exponentiation of standard re-encryption:

$c \gets c \cdot r^n \mod n^2$ (with $r \in \mathbb{Z}_n$ random)

We could pre-compute a large pool of exponentiated values $r_i^n, i=1...p$, then for each re-encryption, take the last re-encrypted ciphertext and multiply it by $k$ randomly chosen $r^n_{\sigma(1)}, ..., r^n_{\sigma(k)}$.

What would be the security (both practical and theoretical) of such a method?

The size of ${p}\choose{k}$ for manageably high values (say $p = 1000$ and $k = 20$) makes the odds of two blinding random variables $R = \Pi_{i=1..k} r_{\sigma(i)}$ being equal, negligibly low in general (and even more so if we only consider successive pairs of such values).

An attacker could possibly raise their chance of finding a collision by comparing every possible products of the resulting ciphertexts together, but even assuming all ciphertexts available to them are indeed generated from this method and setting aside the very large computing cost, the chances of any two products being equal still seem negligibly low.

Am I missing any other possible attack vector? Does a formal security proof seem achievable?

Edit: Possible proof outline


Estimate (comparatively small) chance of accidental collision between $R^{(i)}(c)$ and $R^{(j)}(c')$, respectively $i^{th}$ and $j^{th}$ re-encryption of ciphers $c$ and $c'$ (maybe treating separately cases $c = c'$ and $c = c'$).
Estimate chance of accidental collision between any two products of $R^{(i)}$: $\Pi_{i = 1...m} R^{(a_i)}$ and $\Pi_{j = 1...n} R^{(b_j)}$, which requires:


$\{a_i\}_i \cap \{b_j\}_j = 0$ (any case where that is not true could be reduced to the previous case)
$\Sigma_i a_i = \Sigma_j b_j$



The main part would therefore be to compute the number of $a_i$ and $b_j$ verifying conditions 1 and 2, given a maximum number of re-encryptions $s$ of a maximum total number of plaintexts $t$. This seems achievable.

Does that seem like a sufficient proof, however?

Edit 2: Actually, condition 2 above could be made even stronger. If we note $r^(i)_1, \dots, r^(i)_k$, the $k$ random values selected by the $i^{th}$ re-encryption, for a collision to be more likely than between two random values, we must have:

$\{r^{(a_1)}_1,\dots,r^{(a_1)}_k,r^{(a_2)}_1,\dots,r^{(a_2)}_k,\dots,r^{(a_n)}_k\} = \{r^{(b_1)}_1,\dots,r^{(b_1)}_k,r^{(b_2)}_1,\dots,r^{(b_2)}_k,\dots,r^{(b_m)}_k\}$

Proof ad absurdum: if there is one value $r^{(i)}_j$ in one set but not the other, then the product of the values in that set is $C * r^{(i)}_j$, with $r^{(i)}_j$ statistically independent from the other set and, for all purposes the two sets are statistically independent.

Edit 3: in all the above, it would probably make computations easier to use a draw with replacement instead (and therefore consider $n^k$ combinations instead of $n\choose k$).
You have to worry not just about a pair of blinding values being equal, but more complex relationships between them.  Thus, finding a proof of security for this approach looks non-trivial to me.

Let me elaborate.  Suppose $R_j$ is the $j$th blinding variable you use.  If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely.  However, that's not the only potential problem.  If there exist indices $a,b,c,d$ such that $R_a R_b = R_c R_d$, then you might also have a problem, and this happens with higher problem.  At least, this will be a difficulty for a proof of security, as this relationship is detectable by an adversary and allows some kinds of distinguishing attacks.  If you make $k$ and $n$ large enough, you can rule out even this kind of multiplicative relationship, but you might still have to worry about higher-order multiplicative relationships, and it's not entirely clear to me how you'd address this challenge.

Perhaps you can deal with this somehow and prove something with some additional insights, but I think the above phenomenom will be a non-trivial complication.



You subsequently revised the question to propose a proof strategy.  Your revised proof strategy won't work.  It requires showing that there's unlikely to be a collision between products of the $R$'s.  However,  you won't be able to show that, because it's not true: if you consider products of very large size, it's overwhelmingly likely that some such collision does exist.  You can't avoid that by choosing $k$ and $n$ to be larger.  So, the proof strategy you suggest in the revised question isn't going to work.  This is more delicate than you might have realized, and it's not clear to me how to prove that your idea is secure (or whether a proof is possible).