Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Use the notations form the Wikipedia article Paillier Cryptosystem , assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

No, it is not possible to compute $\lambda$ easily. Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability. Hence, if we believe the factorization problem is hard, we must also believe that this modified discrete log problem is hard.

One way to arrive at that is "if you can find $\lambda$ given a random instance, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using the black box, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $pq(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^\lambda = r \bmod n^2$; once you know $\lambda$, you also know that $r^{k\lambda-1} = 1 \bmod n$ (because if $(r^k)^\lambda = r \bmod n^2$, then $(r^k)^\lambda = r \bmod n$ as well). That is, the order of $r$ is a divisor of $k\lambda-1$.

Once you have that multiple of an order $x = k\lambda-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$. If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$. And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.

share|improve this answer
    
Thank you very much! BTW, if I want to use this conclusion in a paper, how should I acknowledge you, and how to make the reference? –  phan Feb 24 '13 at 18:35
1  
@phan: I don't know if the result is novel enough to merit a citation; it's taking the standard 'DLOG modulo a composite -> Factor the composite' reduction, and applying that to 'DLOG modulo the square of a composite'. However, if you believe it is warrented, why don't you acknowledge Scott Fluhrer, and this StackExchange question (I've seen sci.crypt posting cited before; I see no reason why StackExchange can't be similarly cited). –  poncho Feb 24 '13 at 22:32
    
Thank you again! –  phan Feb 26 '13 at 4:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.