# 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(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?

.

**Follow-Ups**:**Re: Is fast variant of Paillier insecure?***From:*Kristian Gjøsteen

- 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):