Dave
Reputation
Next privilege 250 Rep.
 Jan16 revised Formal security of recycled random blinding in a Paillier scheme added 186 characters in body Jan16 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... Jan15 revised Formal security of recycled random blinding in a Paillier scheme added 1 character in body Jan15 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). Jan15 revised Formal security of recycled random blinding in a Paillier scheme added 695 characters in body Jan15 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) Jan15 revised Formal security of recycled random blinding in a Paillier scheme added 854 characters in body Jan15 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? Jan15 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? Jan14 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... Jan14 asked Formal security of recycled random blinding in a Paillier scheme Jan14 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... Jan14 accepted How bad would it be to reuse the random blinding factor in a scheme like Paillier? Jan14 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... Jan14 revised How bad would it be to reuse the random blinding factor in a scheme like Paillier? edited tags Jan14 asked How bad would it be to reuse the random blinding factor in a scheme like Paillier? Sep9 revised Privacy-Preserving Protocols and Proofs of Security added 7 characters in body Sep9 comment Privacy-Preserving Protocols and Proofs of Security Sorry, I should have written out all the constraints, but generally, if you do obfuscation, you want to avoid the field limit, so you would add $r ∈ [0, n-x[$ (for example II). That is definitely not uniformly distributed. Not sure what you mean otherwise: Homomorphic scheme allow scalar multiplication and many obfuscation schemes might require more than simple addition. Sep9 comment Privacy-Preserving Protocols and Proofs of Security This is mainly what I was told when discussing such protocols with people in the field. This is also the general impression I get from literature (where the typical "proof of security" for obfuscation is that the obfuscated value is uniformly distributed). I realise this is a weak source and it sounds like a lazy upper bound to me, which is precisely why I'd love some hard reference to what defines proper obfuscation security in such a context. Sep9 revised Privacy-Preserving Protocols and Proofs of Security added 368 characters in body