Misplaced Pages

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Cohen's cryptosystem" – news · newspapers · books · scholar · JSTOR (June 2010)

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

Key generation

In Cohen's cryptosystem, a private key is a positive integer ${\displaystyle p}$.

The algorithm uses ${\displaystyle k}$ public-keys ${\displaystyle w_{0},\ldots ,w_{k-1}}$ defined as follows:

Generate ${\displaystyle k}$ random integers ${\displaystyle u_{0},\ldots ,u_{k-1}}$ chosen randomly and uniformly between ${\displaystyle -B}$ and ${\displaystyle B}$. Where ${\displaystyle B}$ is some bound.

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

Define ${\displaystyle w_{i}=(u_{i}p+v_{i})}$.

Encrypting a bit

To encrypt a bit ${\displaystyle m}$ Alice randomly adds ${\displaystyle {\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 ${\displaystyle c=(-1)^{m}\sum w_{i}}$.

De-cryption

To de-crypt, Bob computes ${\displaystyle h=c\mod p=(-1)^{m}\sum v_{i}}$

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

References

1. Bram Cohen. "Simple Public Key Encryption". Archived from the original on October 7, 2011.

• Public-key cryptography