I recently discovered the benaloh cryptosystem. I am working with the system as it is discribed in the following link: https://en.wikipedia.org/wiki/Benaloh_cryptosystem

However I need some help in order to understand why we need \begin{equation} {gcd(r,(p-1)/r)} \end{equation}

As far as I understand the condition \begin{equation} r \mid (p-1) \end{equation} guarantees the existence of the subgroup of order (p-1)/r which contains the r-residues.

The third condition

\begin{equation} {gcd(r,(q-1))} \end{equation}

allows us to say that there are

\begin{equation} \mid \mathbb{Z}_n^* \mid /r \end{equation} r-residues mod n.

what does the other condition add?

  • $\begingroup$ You need those conditions to be sure that $r^2 \not | \phi(n)$ $\endgroup$ – ddddavidee Jan 14 '16 at 21:40
  • $\begingroup$ why is this important here? $\endgroup$ – user28082 Jan 14 '16 at 22:10
  • $\begingroup$ otherwise your secret key $x$ would be a $r$-residue. and the decryption would not work. I'll try to write down the whole in a complete answer during next weekend. $\endgroup$ – ddddavidee Jan 14 '16 at 22:16

$gcd(r,(p-1)/r)$ needs to be $1$ in Benaloh cryptosystem that mean that $(r)$ and $(p-1)$ are preliminary among them.

  • 1
    $\begingroup$ sorry i dont understand your answer. Could you please explain what do you mean by preliminary among them? $\endgroup$ – user28082 Jan 15 '16 at 22:57
  • $\begingroup$ it's mean they have to be prime between them e.g 9 and 26 are prime between them. $\endgroup$ – Rafik Hamza Jan 17 '16 at 21:31
  • $\begingroup$ then what you say is not true. $gcd(r,(p−1)/r)$ only says that $r$ and $(p-1)/r$ are prime between them. But surely not that $r$ and $p-1$ are prime between them (which is not the case by the way). This doesn't seem to be an answer to my initial question why we need this condition. $\endgroup$ – user28082 Jan 17 '16 at 22:23
  • $\begingroup$ yep, i got you , u want to know why this condition is set up, the authors of this algorithm set this condition which is gcd(r,(p−1)/r)=gcd(r,p−1)=1 maybe u have just to read the exect article. for all what i know, it's necessary for the algorithm to work correctly, u may want to see the work of "Benaloh's Dense Probabilistic Encryption Revisited" arxiv.org/pdf/1008.2991.pdf $\endgroup$ – Rafik Hamza Jan 19 '16 at 20:58

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.