Cohen's cryptosystem

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

Key generation

In Cohen's cryptosystem, private key is a positive integer [math]\displaystyle{ p }[/math].

The algorithm uses [math]\displaystyle{ k }[/math] public-keys [math]\displaystyle{ w_0,\ldots,w_{k-1} }[/math] defined as follows:

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

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

Define [math]\displaystyle{ w_i=(u_i p+v_i) }[/math].

Encrypting a bit

To encrypt a bit [math]\displaystyle{ m }[/math] Alice randomly adds [math]\displaystyle{ \frac{k}{2} }[/math] 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 [math]\displaystyle{ c=(-1)^{m} \sum w_i }[/math].

De-cryption

To de-crypt, Bob computes [math]\displaystyle{ h= c \mod p = (-1)^{m} \sum v_i }[/math]

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