Cocks IBE scheme is an Identity based encryption system proposed by Clifford Cocks in 2001 [1]. The security of the scheme is based on the hardness of the quadratic residuosity problem.

## Protocol

### Setup

The PKG chooses:

1. a public RSA-modulus ${\displaystyle \textstyle n = pq}$, where ${\displaystyle \textstyle p,q,\,p \equiv q \equiv 3 \mod 4}$ are prime and kept secret,
2. the message and the cipher space ${\displaystyle \textstyle \mathcal{M} = \left\{-1,1\right\}, \mathcal{C} = \mathbb{Z}_n}$ and
3. a secure public hash function ${\displaystyle \textstyle f: \left\{0,1\right\}^* \rightarrow \mathbb{Z}_n}$.

### Extract

When user ${\displaystyle \textstyle ID}$ wants to obtain his private key, he contacts the PKG through a secure channel. The PKG

1. derives ${\displaystyle \textstyle a}$ with ${\displaystyle \textstyle \left(\frac{a}{n}\right) = 1}$ by a determistic process from ${\displaystyle \textstyle ID}$ (e.g. multiple application of ${\displaystyle \textstyle f}$),
2. computes ${\displaystyle \textstyle r = a^{\frac{n+5-p-q}{8}} \mod n}$ (which fulfils either ${\displaystyle \textstyle r^2 = a \mod n}$ or ${\displaystyle \textstyle r^2 = -a \mod n}$, see below) and
3. transmits ${\displaystyle \textstyle r}$ to the user.

### Encrypt

To encrypt a bit (coded as ${\displaystyle \textstyle 1}$/${\displaystyle \textstyle -1}$) ${\displaystyle \textstyle m \in \mathcal{M}}$ for ${\displaystyle \textstyle ID}$, the user

1. chooses random ${\displaystyle \textstyle t}$ with ${\displaystyle \textstyle m = \left(\frac{t}{n}\right)}$,
2. computes ${\displaystyle \textstyle c_1 = t + at^{-1} \mod n }$ and ${\displaystyle c_2= t - at^{-1}}$ and
3. sends ${\displaystyle \textstyle s=(c_1, c_2)}$ to the user.

### Decrypt

To decrypt a ciphertext ${\displaystyle s=(c_1, c_2)}$ for user ${\displaystyle ID}$, he

1. computes ${\displaystyle \alpha = c_1 + 2r}$ if ${\displaystyle r^2=a }$ or ${\displaystyle \alpha = c_2 + 2r}$ otherwise, and
2. computes ${\displaystyle m = \left(\frac{\alpha}{n}\right)}$.

Note that here we are assuming that the encrypting entity does not know whether ${\displaystyle ID}$ has the square root ${\displaystyle r}$ of ${\displaystyle a}$ or ${\displaystyle -a}$. In this case we have to send a ciphertext for both cases. As soon as this information is known to the encrypting entity, only one element needs to be sent.

### Correctness

First note that since ${\displaystyle \textstyle p \equiv q \equiv 3 \mod n}$ (i.e. ${\displaystyle \left(\frac{-1}{p}\right) = \left(\frac{-1}{q}\right) = -1}$) and ${\displaystyle \textstyle \left(\frac{a}{n}\right) \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)}$, either ${\displaystyle \textstyle a}$ or ${\displaystyle \textstyle -a}$ is a quadratic residue modulo ${\displaystyle \textstyle n}$.

Therefore, ${\displaystyle \textstyle r}$ is a square root of ${\displaystyle \textstyle a}$ or ${\displaystyle \textstyle -a}$:

{\displaystyle \begin{align} r^2 &= \left(a^{\frac{n+5-p-q}{8}}\right)^2 \\ &= \left(a^{\frac{n+5-p-q - \Phi\left(n\right)}{8}}\right)^2 \\ &= \left(a^{\frac{n+5-p-q - (p-1)(q-1)}{8}}\right)^2 \\ &= \left(a^{\frac{n+5-p-q - n+p+q-1}{8}}\right)^2 \\ &= \left(a^{\frac{4}{8}}\right)^2 \\ &= \pm a \\ \end{align} }

Moreover (for the case that ${\displaystyle \textstyle a}$ is a quadratic residue, same idea holds for ${\displaystyle \textstyle -a}$):

{\displaystyle \begin{align} \left(\frac{s+2r}{n}\right) &= \left(\frac{t + at^{-1} +2r}{n}\right) = \left(\frac{t\left(1+at^{-2} +2rt^{-1}\right)}{n}\right) \\ &= \left(\frac{t\left(1+r^2t^{-2} +2rt^{-1}\right)}{n}\right) = \left(\frac{t\left(1+rt^{-1}\right)^2}{n}\right) \\ &= \left(\frac{t}{n}\right) \left(\frac{1+rt^{-1}}{n}\right)^2 = \left(\frac{t}{n} \left(\pm 1\right)\right)^2 = \left(\frac{t}{n}\right) \\ \end{align} }

## Security

It can be shown that breaking the scheme is equivalent to solving the quadratic residuosity problem , which is suspected to be very hard. The common rules for choosing a RSA modulus hold: Use a secure ${\displaystyle \textstyle n}$, make the choice of ${\displaystyle \textstyle t}$ uniform and random and moreover include some authenticity checks for ${\displaystyle \textstyle t}$ (otherwise, an adaptive chosen ciphertext attack can be mounted by altering packets that transmit a single bit and using the oracle to observe the effect on the decrypted bit).

## Problems

A major disadavantage of this scheme is that it can encrypt messages only bit per bit - therefore, it is only suitable for small data packets like a session key. To illustrate, consider a 128 bit key that is transmitted using a 1024 bit modulus. Then, one has to send 2 * 128 * 1024 bit = 32 KByte (when it is not known whether ${\displaystyle r}$ is the square of ${\displaystyle a}$ or ${\displaystyle -a}$), which is only acceptable for environments in which session keys change infrequently.

This scheme does not preserve key-privacy, i.e. a passive adversary can recover meaningful information about the identity of the recipient observing the ciphertext.

## References

1. Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001