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_ip + v_i).

Encrypting a bit

To encrypt a bit m Alice randomly adds 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 = 0 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". http://bramcohen.com/simple_public_key.html.