Benaloh cryptosystem

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.

cheme Definition

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

Key Generation

A public/private key pair is generated as follows:

*Choose a blocksize "r".
*Choose large primes "p" and "q" such that "r" divides ("p"-1) and gcd("q"-1,r) = 1.
*Set "n" = "pq"
*Choose y in (mathbb{Z}/nmathbb{Z})^* such that y^{(p-1)(q-1)/r} ot equiv 1 mod n.

The public key is then "y","n", and the private key is the two primes "p","q".

Message Encryption

To encrypt a message "m", where "m" is taken to be an element in mathbb{Z}/rmathbb{Z}

*Choose a random u in (mathbb{Z}/nmathbb{Z})^*
*Set E_r(m) = y^m u^r mod n

Message Decryption

To understand decryption, we first notice that for any "m","u" we have

:(y^m u^r)^{(p-1)(q-1)/r} equiv y^{m(p-1)(q-1)/r} u^{(p-1)(q-1)} equiv y^{m(p-1)(q-1)/r} mod n

Since "m" < "r" and y^{(p-1)(q-1)/r} ot equiv 1 mod n, we can conclude that (y^m u^r)^{(p-1)(q-1)/r} equiv 1 mod n if and only if "m" = 0.

So if z = y^m u^r mod n is an encryption of "m", given the secret key "p","q" we can determine whether "m"=0. If "r" is small, we can decrypt "z" by doing an exhaustive search, i.e. decrypting the messages "y"-"i"z for "i" from 1 to "r". By precomputing values, using the Baby-step giant-step algorithm, decryption can be done in time O(sqrt{r}).

ecurity

The security of this scheme rests on an extension of the Quadratic 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 "r"th residue mod "n", i.e. if there exists an "x" such that z equiv x^r mod n.

References

[http://research.microsoft.com/crypto/papers/dpe.ps Original Paper] (ps)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia

  • Naccache-Stern cryptosystem — Note: this is not to be confused with the Naccache Stern knapsack cryptosystem.The Naccache Stern cryptosystem is a homomorphic Public key cryptosystem whose security rests on the higher residuosity problem.The Naccache Stern cryptosystem was… …   Wikipedia

  • McEliece cryptosystem — In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance… …   Wikipedia

  • Cramer–Shoup cryptosystem — The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the… …   Wikipedia

  • Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… …   Wikipedia

  • Damgård–Jurik cryptosystem — The Damgård–Jurik cryptosystem[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ns + 1 where n is an RSA modulus and s a (positive) natural number. Paillier s scheme is the special case with s = 1. The order φ(ns + …   Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

  • Okamoto–Uchiyama cryptosystem — The Okamoto–Uchiyama cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group , where n is of the form p2q and p and q are large primes. Contents 1 Scheme definition 1.1 Key generation …   Wikipedia

  • Homomorphic encryption — is a form of encryption where one can perform a specific algebraic operation on the plaintext by performing a (possibly different) algebraic operation on the ciphertext. Depending on one s viewpoint, this can be seen as a positive or negative… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”