When I read about DLP, I found that there are groups where the computation is easy. I found that it is known that computing discrete logarithms in the subgroup generated by 1 + N is easy. For example : $ (1+N)^{x} = 1+ xN $. Is this correct? And what is the mathematical foundation of this computation? Why is considered as easy compared to the other groups?

  • 1
    $\begingroup$ subgroup of which group? $\endgroup$ – kelalaka May 25 at 20:12
  • 4
    $\begingroup$ If we are in $\Bbb Z_N$, it holds $(1+N)^x=1=1+x\,N$ making the generated group rather boring. Thus it's essential to state what base ring (or other algebraic structure) is used. $\endgroup$ – fgrieu May 25 at 20:45
  • 1
    $\begingroup$ This is true in the Paillier group and the property is exploited in the decryption procedure. $\endgroup$ – Occams_Trimmer May 25 at 21:42
  • $\begingroup$ Occams_Trimmer, could you please provide me more details? $\endgroup$ – sof May 25 at 22:25
  • $\begingroup$ The Wikipedia entry (Background section) is quite detailed. $\endgroup$ – Occams_Trimmer May 25 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.