Reputation
200
Next privilege 250 Rep.
View close votes
Badges
9
Impact
~1k people reached

  • 0 posts edited
  • 0 helpful flags
  • 4 votes cast
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
Sep
9
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.
Sep
9
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.