3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ You need those conditions to be sure that $r^2 \not | \phi(n)$ $\endgroup$
    – ddddavidee
    Jan 14, 2016 at 21:40
  • $\begingroup$ why is this important here? $\endgroup$
    – user28082
    Jan 14, 2016 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, 2016 at 22:16

1 Answer 1

-1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ sorry i dont understand your answer. Could you please explain what do you mean by preliminary among them? $\endgroup$
    – user28082
    Jan 15, 2016 at 22:57
  • $\begingroup$ it's mean they have to be prime between them e.g 9 and 26 are prime between them. $\endgroup$ Jan 17, 2016 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, 2016 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$ Jan 19, 2016 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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