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

Bram Cohen Bram Cohen is an American computer programmer, best known as the author of the peer-to-peer (P2P) BitTorrent protocol in 2001, as well as the first file sharing program to use the protocol, also known as BitTorrent. He is also the co-founder of ...

Key generation

In Cohen's cryptosystem,

private key Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

is a

positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

p

. The

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

uses

k

public-keys

w_0,\ldots,w_

defined as follows: Generate

k

random

integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

u_0,\ldots,u_

chosen randomly and uniformly between

-B

and

B

. Where

B

is some bound. Let

A=\lfloor\frac\rfloor

and generate

k

random integers

v_0,\ldots,v_

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

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 In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...

c=(-1)^ \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

Public-key cryptography