Goldwasser-Micali cryptosystem

The Goldwasser – Micali cryptosystem was introduced in 1982 by Shafrira Goldwasser and Silvio Micali . It is an asymmetrical cryptosystem for encrypting individual bits . The method is additive-homomorphic , i.e. That is, two encrypted messages can be added without first decrypting the messages.

The process was later expanded by Josh Benaloh to the Benaloh cryptosystem , which can also be used to encrypt longer messages.

Procedure

In the following we describe the key generation and the algorithms for encrypting and decrypting messages.

Generation of the public and private key

The key pair is generated as follows:

First you generate two random prime numbers , and define them . In practice, n should have at least 1024, but better 1536 or 2048 binary digits . ${\ displaystyle p, q}$ ${\ displaystyle n = pq}$

One randomly chooses in such that a quadratic non- remainder is modulo and has Jacobi symbol . This can be found efficiently, for example, by choosing it at random and checking whether the Legendre symbol satisfies, and otherwise starting over. Is a Blum number, i. h., so one can choose. ${\ displaystyle y}$ ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$ ${\ displaystyle y}$ ${\ displaystyle n}$ ${\ displaystyle \ left ({\ frac {y} {n}} \ right) = + 1}$ ${\ displaystyle y}$ ${\ displaystyle \ left ({\ frac {y} {p}} \ right) = \ left ({\ frac {y} {q}} \ right) = - 1}$ ${\ displaystyle n}$ ${\ displaystyle p \ equiv q \ equiv 3 \ mod 4}$ ${\ displaystyle y = n-1}$

The public key consists of , the private key consists of . ${\ displaystyle (n, y)}$ ${\ displaystyle (p, q)}$

Encrypt messages

To encrypt a message , proceed as follows: ${\ displaystyle m \ in \ {0.1 \}}$

First you choose a random one . ${\ displaystyle u \ in (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$
The encrypted message is then given through . ${\ displaystyle c = y ^ {m} u ^ {2} \ mod n}$

Decrypting messages (decoding)

For decrypting a ciphertext , it is checked whether a quadratic residue or not residue modulo is: ${\ displaystyle c \ in (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$ ${\ displaystyle c}$ ${\ displaystyle n}$

Applies and , as one sets , otherwise it is . ${\ displaystyle c ^ {(p-1) / 2} \ equiv 1 \ mod p}$ ${\ displaystyle c ^ {(q-1) / 2} \ equiv 1 \ mod q}$ ${\ displaystyle m = 0}$ ${\ displaystyle m = 1}$

The correctness of the decryption can be seen by observing that an element in is a quadratic remainder modulo if and only if it is a quadratic remainder modulo and modulo . According to Euler's criterion , this is the case if and is true. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$ ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle c ^ {(p-1) / 2} \ equiv 1 \ mod p}$ ${\ displaystyle c ^ {(q-1) / 2} \ equiv 1 \ mod q}$

safety

Under the square remainder assumption, it can be shown that the method is semantically secure against selected plaintext attacks . This assumption means that for a composite module it cannot be efficiently checked whether an element has a square root modulo or not, if selected as described above . ${\ displaystyle n}$ ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z})}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Homomorphism properties

The Goldwasser – Micali cryptosystem is additive homomorphic. This means that by multiplying two key texts, the plain texts contained therein are added modulo 2. However, there is no known way to multiply the messages contained by operations on two key texts.

credentials

↑ Shafrira Goldwasser and Silvio Micali : Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information ( English , PDF) Accessed February 1, 2019.

[1] Shafrira Goldwasser and Silvio Micali : Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information ( English , PDF) Accessed February 1, 2019.