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.
The algorithm uses public-keys defined as follows:
Generate random integers chosen randomly and uniformly between and. Where is some bound.
Let and generate random integers chosen randomly and uniformly between and.
Define.

Encrypting a bit

To encrypt a bit Alice randomly adds public keys and multiplies the result by either 1 or by −1 to obtain the ciphertext.

De-cryption

To de-crypt, Bob computes
It is easy to see that if then. However, if then. Hence Bob can read the bit sent by Alice on the most significant bit of h.