Benaloh cryptosystem requires $\gcd(r, (q-1))=1$ which is impossible if $q>2$ (since it needs to be a large prime) and $r=2$. This confuses me, since Benaloh is referred to as an "extension" or "generalization" of Goldwasser-Micali cryptosystem, but even though they're extremely close, Benaloh doesn't seem to work at $r=2$ when Goldwasser-Micali specifically works at $r=2$. Is there a way to make changes to these cryptosystems so that we can "generalize" Goldwasser-Micali in a way it also works for $r=2$ (i.e. works for all prime numbers* $r$)?

  • [*] I said prime since Benaloh's original cryptosystem doesn't work for composite $r$s, as pointed out and fixed by Fousse et al. Prime $r$ is sufficient for my uses, but I'd like to generalize for all primes including $2$.

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.