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},\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.