title: Cohen's cryptosystem
text: # 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 $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_{i}p+v_{i})$.
  
  ## Encrypting a bit
  
  To encrypt a bit $m$ Alice randomly 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=1$ then $p>h>p/2$. Hence Bob can read the bit sent by Alice on the most significant bit of h.
  
  