Cohen's cryptosystem

Cohen's cryptosystem^[1] is a public-key cryptosystem proposed in 1998 by Bram Cohen.

Key generation

In Cohen's cryptosystem, private key is a positive integer $p$.

The algorithm uses $k$ public-keys $w_0,\ldots,w_{k-1}$ defined as follows:

Generate $k$ random integers $u_0,\ldots,u_{k-1}$ chosen randomly and uniformly between $-B$ and $B$. Where $B$ is some bound.

Let $A=\lfloor\frac{p}{2k}\rfloor$ and generate $k$ random integers $v_0,\ldots,v_{k-1}$ chosen randomly and uniformly between $0$ and $A$.

Define $w_i=(u_i p+v_i)$.

Encrypting a bit

To encrypt a bit $m$ Alice randomly adds $\frac{k}{2}$ public keys and multiplies the result by either 1 (if she wishes to send a 0) or by −1 (if she wishes to send a 1) to obtain the ciphertext $c=(-1)^{m} \sum w_i$.

De-cryption

To de-crypt, Bob computes $h= c \mod p = (-1)^{m} \sum v_i$

It is easy to see that if $m=0$ then $0<h<p/2$. However, if $m=1$ then $p>h>p/2$. Hence Bob can read the bit sent by Alice on the most significant bit of h.

References

1. Bram Cohen. "Simple Public Key Encryption". Archived from the original on October 7, 2011.