Talk:Damgård–Jurik cryptosystem

Latest comment: 14 years ago by Iv in topic Simplification

Decryption using p-adics

edit

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

 

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

 

I.e. the function satisfies the equation

 

Moreover,   can be evaluated in a finite number of steps, since the terms   vanish when i is sufficiently large. 67.84.116.166 03:43, 6 September 2006 (UTC)Reply

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

Simplification

edit

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

 .

Since every (invertible) element modulo ns+1 has an order that divides   if follows that the order of   divides  . Hence   and thus

 

Generally,   is much shorter than d leading to faster decryption. Taking logarithms from   gives   and hence we can derive m. 67.84.116.166 00:35, 8 September 2006 (UTC)Reply

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.


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