Cohen's cryptosystem is a public-key cryptosystem proposed in 1998 by Bram Cohen.
In Cohen's cryptosystem, private key is a positive integer p .
The algorithm uses k public-keys w 0 , … , w k − 1 defined as follows:
Generate k random integers u 0 , … , u k − 1 chosen randomly and uniformly between − B and B . Where B is some bound.
Let A = ⌊ p 2 k ⌋ and generate k random integers v 0 , … , v k − 1 chosen randomly and uniformly between 0 and A .
Define w i = ( u i p + v i ) .
To encrypt a bit m Alice randomly adds 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 ∑ w i .
To de-crypt, Bob computes h = c mod p = ( − 1 ) m ∑ 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.
