# 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:

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

2. $\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).

• Yes, that's what I meant by "every possible products", above... Although there's also the fact that this would itself quickly become a combinatorially expensive task. However, we could probably use the fact that $R_aR_b = R_cR_d$ would require (with overwhelming odds) $a+b=c+d$, which considerably reduce the number of products that can be eligible. $1000 \choose 20$ is in the order of $10^{41}$, which gives a lot of margin... Would it be sufficient, do you think, to prove that no such products of Rs are likely to be equal? – Dave Jan 15 '15 at 1:25
• @Dave, I think some of your details are a bit off there: there's no reason that $R_a R_b = R_c R_d$ would require $a+b=c+d$. – D.W. Jan 15 '15 at 9:25
• I might be missing something, but if you are comparing the products of different numbers of random values ($\Pi_{i=1..n}r_i$ and $\Pi_{i=1..m}r_i$, with $n \ne m$), your chance for an equality are strictly the same as with any two random values. In fact, I think you should only consider cases where the underlying sets of $k * (a+b)$ and $k * (c+d)$ random values are identical (this requirement would obviously greatly affect the number of products that can be considered, and therefore the probability of collision) – Dave Jan 15 '15 at 11:09
• I have edited my question again to provide what should be a valid proof of that statement. It seems to me that we should not be considering any possible collisions that happen with the same probability as two random values (which we would be if the sets were not identical). – Dave Jan 15 '15 at 11:27
• @Dave, for a fixed subset of the $R$'s, the chances of a collision are the same. Now count the number of such subsets. You'll find that there are exponentially many subsets, so once you sign a reasonably large number of messages, the probability that there exists some such multiplicative relationship is close to 1. – D.W. Jan 15 '15 at 19:28

Suppose an adversary can collect all $k$ ciphertexts created for some unknown plaintext. It is clear that product of all $r_i$ is an invariant under any permutation. So this adversary would multiply ciphertexts collected, reducing to previous question with repeated $r$. To avoid such an attack, one needs non-standard assumption(s) on capability of the adversary.

• Indeed, the product of $R_i$ would be an invariant, but I do not see how you would (easily) obtain two such identical products and reduce to the previous case. Would you care to give a specific example? – Dave Jan 15 '15 at 3:06