Benaloh cryptosystem

The Benaloh cryptosystem was introduced by Josh Benaloh in 1994 . It is an asymmetrical cryptosystem . The method is homomorphic ; That is, two encrypted messages can be added without first decrypting the messages.

The method is an extension of the Goldwasser-Micali cryptosystem : while the latter only enables individual bits to be encrypted, the Benaloh cryptosystem allows larger blocks to be encrypted. A small mistake in the description was later made by Laurent Fousse et al. corrected.

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 choose a block size . ${\displaystyle r}$
• Then we generate two random prime numbers such that , as well as , and define . In practice, n should have at least 1024, but better 1536 or 2048 binary digits . ${\displaystyle p,q}$ ${\displaystyle r|(p-1)}$ ${\displaystyle \operatorname {ggT} ((p-1)/r,r)=1}$ ${\displaystyle \operatorname {ggT} (q-1,r)=1}$ ${\displaystyle n=pq}$
• One randomly chooses in such that for all prime divisors of : applies. ${\displaystyle y}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle y^{(p-1)(q-1)/s}\not \equiv 1\mod n}$

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

Encrypt messages

To encrypt a message , proceed as follows: ${\displaystyle m\in (\mathbb {Z} /r\mathbb {Z} )}$

• 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^{r}\mod n}$

Decrypting messages (decoding)

To decrypt a ciphertext then the procedure is as follows: ${\displaystyle c\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

• You set and and then search so that applies. If small, this can be done by trying out all possible values; if , on the other hand, is large, but only has small prime divisors , the index calculus algorithm can be used. ${\displaystyle a=c^{(p-1)(q-1)/r}\mod n}$ ${\displaystyle b=y^{(p-1)(q-1)/r}\mod n}$ ${\displaystyle m}$ ${\displaystyle a=b^{m}\mod n}$ ${\displaystyle r}$ ${\displaystyle r}$

That the decryption actually delivers the secret message again can be seen as follows. It applies

${\displaystyle a=c^{(p-1)(q-1)/r}=(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}=b^{m}\mod n}$

safety

Under the higher residual assumption, it can be shown that the method is semantically secure against attacks with selected plain texts . This assumption means that it is not possible to efficiently check for a composite module whether an element in a -th root has modulo or not, if and as described above . ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n}$

Homomorphism properties

The Benaloh cryptosystem is additive homomorphic. This means that by multiplying two key texts the plain texts contained therein are added, or by exponentiating a key text with the contained value is multiplied. In addition, the message contained can with by multiplying the ciphertext to be enlarged. However, there is no known way to multiply the messages contained by operations on two key texts. ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle y^{w}}$ ${\displaystyle w}$

Complete example

The steps outlined above are illustrated here using a small example.

Key generation

First we choose the block size , then choose and . This applies ${\displaystyle r=9}$ ${\displaystyle p=883}$ ${\displaystyle q=1.019}$

${\displaystyle \operatorname {ggT} ((p-1)/r,r)=\operatorname {ggT} (882/9,9)=\operatorname {ggT} (98,9)=1}$

such as

${\displaystyle \operatorname {ggT} (q-1,r)=\operatorname {ggT} (1018,9)=1}$.

We also choose which one fulfills. ${\displaystyle y=85.147}$ ${\displaystyle 85.147^{882\cdot 1018/3}\equiv 70.977\not \equiv 1\mod (883\cdot 1019)}$

With this we get:

r = 9
n = p·q = 899777
y = 85.147

The public key is given by: ${\displaystyle (r,n,y)=(9,899.777,85.147).}$

The secret key is . ${\displaystyle (p,q)=(883,1.019)}$

Encryption

Suppose you want to encrypt the message . To do this, we choose a random one  : ${\displaystyle m=6}$ ${\displaystyle u\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

u = 175.884

The encryption results in:

c = ymur mod n = 851476 1758849 mod 899777 = 541197

Decryption

For decryption we first calculate:

a = c(p-1)(q-1)/r mod n = 541197882·1018/9 mod 899777 = 4077
b = y(p-1)(q-1)/r mod n =  85147882·1018/9 mod 899777 = 887550

A systematic search now gives us:

y0 mod n = 8875500 mod 899777 = 1 <> 4077
y1 mod n = 887550 <> 4077
y2 mod n = 136547 <> 4077
y3 mod n = 425943 <> 4077
y4 mod n = 803992 <> 4077
y5 mod n = 553318 <> 4077
y6 mod n = 4077

The encrypted message therefore read . ${\displaystyle m=6}$

Individual evidence

1. ↑ Josh Benaloh: Dense Probabilistic Encryption. (PS) Retrieved June 13, 2012 . 
2. ↑ Laurent Fousse, Pascal Lafourcade, and Mohamed Alnuaimi: Benaloh's Dense Probabilistic Encryption Revisited . August 18, 2010, arxiv : 1008.2991 (English).