Talk:Damgård–Jurik cryptosystem

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{\pmod {n^{s+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){\pmod {n^{s+1}}}$ can be evaluated in a finite number of steps, since the terms $(kn)^{i}/i{\pmod {n^{s+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)

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 n^s+1 has an order that divides $\lambda n^{s}$ if follows that the order of $r^{n^{s}}$ divides $\lambda$. 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, $\lambda$ is much shorter than d leading to faster decryption. Taking logarithms from $g^{\lambda 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 $\lambda$. The reason why it may be advisible to choose d different from $\lambda$ 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.

Is there somewhere an implementation of this crypto-system ? Especially of the threshold version that allows self-tallying, dispute-free and have perfect ballot secrecy ? If none exist, I would like to discuss with someone more knowledgeable than I in the domain of cryptography on the feasibility of various voting software thanks to it. --Iv (talk) 23:42, 24 March 2010 (UTC)