Loading AI tools
From Wikipedia, the free encyclopedia
The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 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][2][3]
Like many public key cryptosystems, this scheme works in the group where n is a product of two large primes. This scheme is homomorphic and hence malleable.
Given block size r, a public/private key pair is generated as follows:
The public key is then , and the private key is .
To encrypt message :
To decrypt a ciphertext :
To understand decryption, first notice that for any and we have:
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 for all . For larger values of r, the Baby-step giant-step algorithm can be used to recover m in 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 .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.