Cohen's cryptosystem

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

In Cohen's cryptosystem, a private key is a positive integer ${\displaystyle p}$.

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

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

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

Define ${\displaystyle w_{i}=(u_{i}p+v_{i})}$.

To encrypt a bit ${\displaystyle m}$ Alice randomly adds ${\displaystyle {\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 ${\displaystyle c=(-1)^{m}\sum w_{i}}$.

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

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