World Library  
Flag as Inappropriate
Email this Article

Benaloh cryptosystem

Article Id: WHEBN0006144390
Reproduction Date:

Title: Benaloh cryptosystem  
Author: World Heritage Encyclopedia
Language: English
Subject: Naccache–Stern cryptosystem, Homomorphic encryption, Station-to-Station protocol, Efficient Probabilistic Public-Key Encryption Scheme, Integrated Encryption Scheme
Publisher: World Heritage Encyclopedia

Benaloh cryptosystem

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1994 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.[1]


  • Scheme Definition 1
    • Key Generation 1.1
    • Message Encryption 1.2
    • Message Decryption 1.3
    • Security 1.4
  • References 2

Scheme Definition

Like many public key cryptosystems, this scheme works in the group (\mathbb{Z}/n\mathbb{Z})^* where n is a product of two large primes. This scheme is homomorphic and hence malleable.

Key Generation

Given block size r, a public/private key pair is generated as follows:

  1. Choose large primes p and q such that r \vert (p-1), \operatorname{gcd}(r, (p-1)/r)=1, and \operatorname{gcd}(r, (q-1))=1
  2. Set n=pq, \phi=(p-1)(q-1)
  3. Choose y \in \mathbb{Z}^*_n such that y^{\phi/r} \not \equiv 1 \mod n.
Note: If r is composite, it was pointed out by Fousse et al. in 2011[2] that the above conditions (i.e., those stated in the original paper) are insufficient to guarantee correct decryption, i.e., to guarantee that D(E(m)) = m in all cases (as should be the case). To address this, the authors propose the following check: let r=p_1p_2\dots p_k be the prime factorization of r. Choose y \in \mathbb{Z}^*_n such that for each factor p_i, it is the case that y^{\phi/p_i}\ne 1\mod n.
  1. Set x=y^{\phi/r}\mod n

The public key is then y,n, and the private key is \phi,x.

4.7 Program flowchart- - - - - - - -51 CHAPTER FIVE SUMMARY, RECOMMENDATION. AND CONCLUSIONS 5.1 Summary- - - - - - - - - -53 5.2 Conclusion- - - - - - - - - -54 5.3 Recommendation- - - - - - - -55 REFERENCES- - - - - - - - - -58 APPENDIX- - - - - - - - - -61 LIST OF FIGURES x

Message Encryption

To encrypt message m\in\mathbb{Z}_r:

  1. Choose a random u \in \mathbb{Z}^*_n
  2. Set E_r(m) = y^m u^r \mod n

Message Decryption

To decrypt a ciphertext c\in\mathbb{Z}^*_n:

  1. Compute a=c^{\phi/r}\mod n
  2. Output m=\log_x(a), i.e., find m such that x^m\equiv a \mod n

To understand decryption, first notice that for any m\in\mathbb{Z}_r and u\in\mathbb{Z}^*_n we have:

a = (c)^{\phi/r} \equiv (y^m u^r)^{\phi/r} \equiv (y^{m})^{\phi/r}(u^r)^{\phi/r} \equiv (y^{\phi/r})^m(u)^{\phi} \equiv (x)^m (u)^0 \equiv x^m \mod n

To recover m from a, we take the discrete log of a base x. If r is small, we can recover m by an exhaustive search, i.e. checking if x^i\equiv a \mod n for all 0\dots (r-1). For larger values of r, the Baby-step giant-step algorithm can be used to recover m in O(\sqrt{r}) time and space.


The security of this scheme rests on the Higher residuosity problem, specifically, given z,r and n where the factorization of n is unknown, it is computationally infeasible to determine whether z is an rth residue mod n, i.e. if there exists an x such that z \equiv x^r \mod n.


  1. ^
  2. ^
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.