Cohen's cryptosystem

Cohen's cryptosystem

{{cite web|title=Simple Public Key Encryption |url=http://bramcohen.com/simple_public_key.html |author=Bram Cohen |url-status=dead |archiveurl=https://web.archive.org/web/20111007060226/http://bramcohen.com/simple_public_key.html |archivedate=October 7, 2011 }} is a public-key cryptosystem proposed in 1998 by Bram Cohen.

Key generation

In Cohen's cryptosystem, a 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 m=1$ then $p>h>p/2$ . Hence Bob can read the bit sent by Alice on the most significant bit of h.

References

Category:Public-key cryptography