Dave
Reputation
215
Next privilege 250 Rep.
 Oct 2 awarded Yearling Oct 2 awarded Self-Learner Jul 14 awarded Popular Question Jan 16 revised Formal security of recycled random blinding in a Paillier scheme added 186 characters in body Jan 16 comment Formal security of recycled random blinding in a Paillier scheme I understand the problem of the exponential growth of multiplicative relationship, however, we are not trying to prove that such a relationship cannot happen: only that it is less likely to happen than if we chose independent $R$s (for which what you wrote is equally true). The fact that we can only consider a very restricted subset of products (those with *same* underlying set of $r_i$) would make me think that the growth is (very) sub-exponential, which is all we need... Jan 15 revised Formal security of recycled random blinding in a Paillier scheme added 1 character in body Jan 15 comment Formal security of recycled random blinding in a Paillier scheme 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). Jan 15 revised Formal security of recycled random blinding in a Paillier scheme added 695 characters in body Jan 15 comment Formal security of recycled random blinding in a Paillier scheme 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) Jan 15 revised Formal security of recycled random blinding in a Paillier scheme added 854 characters in body Jan 15 comment Formal security of recycled random blinding in a Paillier scheme 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? Jan 15 comment Formal security of recycled random blinding in a Paillier scheme 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? Jan 14 comment How bad would it be to reuse the random blinding factor in a scheme like Paillier? Here's my attempt at a more general protocol. Unlike the one above, this one seems intuitively "secure enough" to me in practice, but I'd be very interested in what can be attempted to evaluate its actual formal security level if you feel like a stab at it... Jan 14 asked Formal security of recycled random blinding in a Paillier scheme Jan 14 comment How bad would it be to reuse the random blinding factor in a scheme like Paillier? On further thought, such a variant seems like enough of a separate problem (mainly down to computing combinatorial odds, I think) to maybe warrant a separate question... Jan 14 accepted How bad would it be to reuse the random blinding factor in a scheme like Paillier? Jan 14 comment How bad would it be to reuse the random blinding factor in a scheme like Paillier? Indeed, the second equality also does seem to hold and would make single-value blinding a non-starter (not so surprisingly). I wonder if there would be any way to prove that, for a sufficiently large pool of random values, and using, say $k$ randomly picked items out of $n$ each time, we have security... Jan 14 revised How bad would it be to reuse the random blinding factor in a scheme like Paillier? edited tags Jan 14 asked How bad would it be to reuse the random blinding factor in a scheme like Paillier? Sep 9 revised Privacy-Preserving Protocols and Proofs of Security added 7 characters in body