I am reading the paper about Damgård–Jurik cryptosystem.

In the proof, I found this equation

$c^d = (g^mr^{n^s})^d = (\boxed{(1+n)^{j m}x^m}r^{n^s})^d = \boxed{(1+n)^{j md\pmod{n^s}}}(\boxed{x^m}r^{n^s})^{d\pmod{\lambda}}$,

where $g=(1+n)^{j x}\pmod{n^{s+1}}$, $n=pq$ is an RSA module number, $\lambda$ is the least common multiple of $(p − 1)$ and $(q − 1)$, and $\lambda|d$.

I don't know why $((1+n)^{j m}x^mr^{n^s})^d = {(1+n)^{j md\pmod{n^s}}}({x^m}r^{n^s})^{d\pmod{\lambda}}$ holds, can anyone tell me? Thank you!

  • 1
    $\begingroup$ I'm not sure about the second part, but $(1+n)^{n^s}=1$ mod $n^{s+1}$ $\endgroup$ – Florian Bourse Jul 5 '18 at 12:57

The simple answer is that the element $(n+1)$ is of order $n^s$, i.e. $(n+1)^{n^s} \equiv 1 \bmod n^{s+1}$. Thus the first part can be written as $(1+n)^{jmd \bmod n^s}$.

For the other part it is $(x^mr^{n^s})^d$, it is written in that way so that it is easier to see the setting that $d \equiv 0 \bmod \lambda$ ensures this part $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$. To see why, note that $x^\lambda \equiv 1 \bmod n^{s+1}$ and also $(r^{n^s})^\lambda \equiv 1 \bmod n^{s+1}$. The explaination is as the following:

  • We know that $x\in H$ where $H=\{g^{n^s} \bmod n^{s+1}|g\in Z_{n^{s+1}}^*\}$ is a subgroup of $Z_{n^{s+1}}^*$, we know $r \in Z_{n}^*$ and $Z_{n}^*$ is a subgroup of $Z_{n^{s+1}}^*$ (thus $r$ is also in $Z_{n^{s+1}}^*$).
  • We know the exponent (the least common multiple of the orders of all elements of the group) of $Z_{n^{s+1}}^*$ is $n^s\lambda$ (see here, $\lambda$ in the paper is a shorthand for $\lambda(n)$). In other words, $a^{n^s\lambda}\equiv 1 \bmod n^{s+1}$ holds for any element $a$ in $Z_{n^{s+1}}^*$
  • Therefore, $x^\lambda=g^{n^s\lambda}\equiv 1 \bmod n^{s+1}$, and $r^{n^s\lambda}\equiv 1 \bmod n^{s+1}$

It thus follows that if $d\equiv 0 \bmod \lambda$ (i.e. $d = k\lambda $ for some k), then $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$.

| improve this answer | |
  • $\begingroup$ Sir, can you please tell me why $(x^mr^{n^s})^d\mod{n^{s+1}} =({x^m}r^{n^s})^{d\pmod{\lambda}}$ in detail? Thank you $\endgroup$ – Felix LL Jul 9 '18 at 12:39
  • $\begingroup$ see the added explanation above. $\endgroup$ – Changyu Dong Jul 9 '18 at 14:32

Your Answer

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

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