Benaloh cryptosystem

The Benaloh cryptosystem was introduced in 1994 by Josh Benaloh. It is an asymmetric cryptosystem. The method is homomorphic, i.e., two encrypted messages can be added without having to decode the message before.

The method is an extension of the Goldwasser - Micali cryptosystem: whereas the latter allows encrypting individual bits, the Benaloh cryptosystem allows the encryption of larger blocks. A small error in the description was later Laurent Fousse et al. corrected.

• 4.1 Key Generation
• 4.2 encryption
• 4.3 decryption

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 you choose a block size.
• Then one generates two random prime numbers, so that, as well as apply and defined. In practice, n should be at least 1024, but have better 1536 or 2048 binary digits.
• It randomly chooses in such that for all prime divisors of the following applies: applies.

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)

To decrypt a ciphertext one then proceeds as follows:

• It sets and then looking for a so true. Is small, this can be done by trying all possible values ​​; on the other hand is great, but has only small prime divisors, the index - calculus algorithm can be used.

The fact that the decryption actually is delivering the secret message can be seen as follows. It is

Security

Under the Higher - Residuosity assumption it 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 element has in a - th root modulo or not, if and were chosen as described above.

Homomorphieeigenschaften

The Benaloh cryptosystem is additively homomorphic -. This means that the plain texts contained therein are added by multiplication of two key texts, or by exponentiation of a key text with the contained value is multiplied. In addition, the message contained can be increased by multiplying the ciphertext with order. However, there is no known way to multiply by operations on two key texts which contained messages with each other.

Complete Example

The above steps will be illustrated here with a simple example.

Key generation

First, we choose the block size, and select and. This is true

As well as

Furthermore, we choose which fulfilled.

Thus we obtain:

R = 9 n = p · q = 899 777 y = 85 147 The public key is thus given by:

The secret key is.

Encoding

Suppose you want to encrypt the message. We choose a random:

U = 175 884 The encryption is then calculated as:

C = ymur mod n = 851476 1758849 mod 899 777 = 541 197 decryption

For decryption, we first calculate:

A = c (p -1) ( q -1) / r mod n = 541197882.1108 / 9 = 487961 899777 mod b = y ( P-1) (q -1) / r mod n = 85147882.1108 / mod 9 = 899 777 494 615 A systematic search yields us now:

Y0 mod n = 4.94615 million mod 899 777 = 1 < > 487 961 y1 mod n = 494 615 <> 487 961 y2 mod n = 678 709 <> 487 961 y3 mod n = 70977 <> 487 961 y4 mod n = 283905 <> 487 961 y5 mod n = 631 022 <> 487 961 y6 mod n = 487 961 The encrypted message was therefore.

Credentials

• Asymmetric encryption algorithm