Cohen's cryptosystem

Cohen's cryptosystem is a public-key cryptosystem proposed in 1998 by Bram Cohen.

Key generation

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

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

Generate $k$ random integers $u_0,\dots ,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,\dots ,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=cmodp=(-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.