Talk:Damgaard-Jurik cryptosystem

From Wikipedia, the free encyclopedia

[edit] Decryption using p-adics

It seems that Damgaard and Jurik have reinvented some known results in p-adics. In particular the last step of the decryption requires to solve the equation

(1 + n)x = 1 + kn(mod ns + 1)

for the unknown x. It is well known that in the p-adic ring \mathbb Z_n a logarithm can be defined as

\log(1+kn) = \sum_{i=1}^{\infty} (-1)^{i+1}\frac{(kn)^i}{i}.

I.e. the function satisfies the equation

log((1 + kn)(1 + mn)) = log(1 + kn) + log(1 + mn).

Moreover, log(1 + kn)(mod ns + 1) can be evaluated in a finite number of steps, since the terms (kn)i / i(mod ns + 1) vanish when i is sufficiently large. 67.84.116.166 03:43, 6 September 2006 (UTC)

A nice description of the decryption, i.e., of what is called recursive application of Pallier encryption in the text, is still missing. The mathematical insights you mention above could prove valuable there. You may also want to have a look at: Dario Catalano, Phong Q. Nguyen, Jacques Stern: The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm . ASIACRYPT 2002: 299-310 134.58.253.131 07:18, 6 September 2006 (UTC)

[edit] Simplification

Maybe, I'm missing something but this cryptosystem looks more complicated than necessary. The ciphertext is

c=g^m \cdot r^{n^s} \mod n^{s+1} .

Since every (invertible) element modulo ns+1 has an order that divides λns if follows that the order of r^{n^s} divides λ. Hence \left(r^{n^s}\right)^{\lambda}\equiv 1\pmod{n^{s+1}} and thus

c^\lambda \equiv g^{\lambda m}\pmod{n^{s+1}}.

Generally, λ is much shorter than d leading to faster decryption. Taking logarithms from gλm gives \lambda m \mod n^{s} and hence we can derive m. 67.84.116.166 00:35, 8 September 2006 (UTC)

In step 4 of the key generation, it says that d could be λ. The reason why it may be advisible to choose d different from λ is, as far as I know, related to it's use for obtaining the corresponding threshold cryptosystem. Homomorphic threshold cryptosystems are for instance used for constructing electronic voting schemes.