Re: Is fast variant of Paillier insecure?



Hi David,

On Sep 30, 10:59 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
wrote:
Amit wrote:
Let p, q be primes and let n=p*q. Let \lambda=LCM(p-1, q-1) such that
s is a large prime dividing \lambda.
Let g be such that order of g in Z*_{n^2} is s*n.

Someone wrote to me that revealing g allows us to factor n. I could
not find the attack. Is this true?

Let h = g^n (mod n). Then h has order s.

1. If s is such that s | p-1 but s does not divide q-1, then
gcd(h-1, n) = q
So in this case, knowledge of g allows to factor n. I suspect
this is probably the case that your correspondent is referring to,
because this is the most natural interpretation of the question
you asked.

2. If s | p-1, s | q-1, and (p-1)/s and (q-1)/s are both small,
and s is known, then the following procedure can be used to factor
n. Pick x randomly, let l = s * k! where k is an upper bound on
max((p-1)/s, (q-1)/s), and check whether x^s = 1 (mod n). If so,
then repeatedly replace s with s/2 until x^s != 1 (mod n), and at
that point gcd(x-1, n) reveals a factor of n with probability at
least 1/2. Repeat this procedure until n is factored.

Yes, these are the two attacks I was looking for. Thanks.
The fact that fast Pailler is insecure seems to be well known to
cryptographers. I wonder why its not mentioned properly in the
literature for us novices.. perhaps I need to look harder.


3. If s | p-1, s | q-1, s is secret, and (p-1)/s and (q-1)/s
both have large random prime factors, I'm not sure what happens.
This smells like something where bad things could happen, so I
certainly wouldn't use this in a real system, though I don't have
an attack.

This case seems interesting due to a richer algebraic structure.
Perhaps it can be used to construct something useful.
(i.e., to have three more (large) primes s, r, t such that s*r | p-1,
s*t | q-1,and keeping s, r, t secret (of course))

Kristian, what did you mean when you said 'There are other minor
applications of such moduli'? Can you describe some application?

.