Re: Is fast variant of Paillier insecure?
 From: Amit <amitabh123@xxxxxxxxx>
 Date: Wed, 1 Oct 2008 05:38:42 0700 (PDT)
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(p1, q1) 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  p1 but s does not divide q1, then
gcd(h1, 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  p1, s  q1, and (p1)/s and (q1)/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((p1)/s, (q1)/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(x1, 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  p1, s  q1, s is secret, and (p1)/s and (q1)/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  p1,
s*t  q1,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?
.
 FollowUps:
 Re: Is fast variant of Paillier insecure?
 From: Kristian Gjøsteen
 Re: Is fast variant of Paillier insecure?
 Prev by Date: Re: need help4 little,quick and efficiant free anti virse
 Next by Date: Re: Is fast variant of Paillier insecure?
 Previous by thread: Re: Is fast variant of Paillier insecure?
 Next by thread: Re: Is fast variant of Paillier insecure?
 Index(es):
Relevant Pages
