Goldwasser–Micali cryptosystem

The Goldwasser - Micali cryptosystem was introduced in 1982 by Shafrira Goldwasser and Silvio Micali. It is an asymmetric cryptosystem to encrypt individual bits. The method is homomorphic, ie two encrypted messages can be added, without decrypting the messages previously.

The method was later extended by Josh Benaloh to Benaloh cryptosystem, with the longer message can also be encrypted.

Method

In the following, we describe the key generation, and the algorithms for encryption and decryption of messages.

Generation of public and private key

The key pair is generated as follows:

• First, we generated two random prime numbers, and defined. In practice, n should be at least 1024, but have better 1536 or 2048 binary digits.
• It randomly chooses in, so that a quadratic non- residue modulo and Jacobi symbol has. Such can be found, for example, efficiently by putting it randomly selects and checks whether the Legendre symbol satisfied, and otherwise, restarts. Is a Blum number, ie. , So you can choose.

The public key consists of the private key from.

Encrypting messages

To encrypt a message, the procedure is as follows:

• First you choose a random.
• The encrypted message is then given by.

Decrypt messages ( decoding)

For descrambling a ciphertext to check whether or not a quadratic residue modulo remainder:

• Gilt and so is one, otherwise.

The correctness of the decryption can be seen by noting that an element iff a is a quadratic residue modulo in when there is a quadratic residue modulo and modulo. Again, this is according to Euler's criterion exactly the case if and to apply.

Security

Under the quadratic residue assumption can be shown that the method is semantically secure against chosen - plaintext attacks. This assumption states that for a composite module can not be checked efficiently whether an item in a square root modulo has or not, if elected as described above.

Homomorphieeigenschaften

The Goldwasser - Micali cryptosystem is additively homomorphic -. This means that the plain texts contained therein are modulo 2 added by multiplication of two key texts. However, there is no known way to multiply by operations on two key texts which contained messages with each other.

Credentials

• Asymmetric encryption algorithm