Re: Is fast variant of Paillier insecure?

Hi David,

On Sep 30, 10:59 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
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?


Relevant Pages

  • Re: Is fast variant of Paillier insecure?
    ... s is a large prime dividing \lambda. ... Someone wrote to me that revealing g allows us to factor n. ... not find the attack. ... both have large random prime factors, ...
  • Re: What MEMORIAL DAY is about... one view
    ... In current times, that translates to defense against a repetition of 9/11, and for 56 months he has succeeded against a well-funded enemy that is eager to die to repeat such a "victory". ... So why not give him credit for something that he has unquestionably, unarguably, measurably, visibly, achieved? ... First, it's true that a lot of good men and women are casualties due to political decisions, but you cannot know what would have happened if Afghanistan and Iraq had not been used to enforce demands made on Islamic leaders in general to remove the infrastructure supporting terror. ... Second, I talk with experts in military and political science every week, and you are the only "expert" who thinks bin Laden would rather fight soldiers in Iraq than attack again in the United States. ...
  • Re: creationist rules
    ... repeat the first rule with variations. ... repeat second rule with a lot of capitalization. ... argument is sound, even if the attack is true, to attack the arguer ... Arguments aren't ignorant, ...
  • Re: USN Intercepts SRBM fired from Hawaii
    ... using a nuclear weapon - including terrorist groups. ... their acts - because they take the acts to Send A Message. ... I don't repeat myself to accomplish either. ... Why else would you attack? ...
  • Re: New emails show impeachable neglect by Obama!
    ... attack happening in real time on a video hook-up. ... they sent the UN Ambassador out to 5 Sunday talk shows to repeat the ... Now we know why we didn't hear directly from Obama, ... "If you raise the ceiling four feet, move the fireplace from that wall ...