Cocks IBE scheme

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

Extract

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

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

Encrypt

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

1. chooses random $\textstyle t_1$ with $\textstyle m = \left(\frac{t_1}{n}\right)$,
2. chooses random $\textstyle t_2$ with $\textstyle m = \left(\frac{t_2}{n}\right)$, different from $\textstyle t_1$,
3. computes $\textstyle c_1 = t_1 + at_1^{-1} \mod n$ and $c_2= t_2 - at_2^{-1}$ and
4. sends $\textstyle s=(c_1, c_2)$ to the user.

Decrypt

To decrypt a ciphertext s = (c₁,c₂) for user ID, he

1. computes α = c₁ + 2r if r² = a or α = c₂ + 2r otherwise, and
2. computes $m = \left(\frac{\alpha}{n}\right)$.

Note that here we are assuming that the encrypting entity does not know whether ID has the square root r of a or − 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 $\textstyle p \equiv q \equiv 3 \mod n$ (i.e. $\left(\frac{-1}{p}\right) = \left(\frac{-1}{q}\right) = -1$) and $\textstyle \left(\frac{a}{n}\right) \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$, either $\textstyle a$ or $\textstyle -a$ is a quadratic residue modulo $\textstyle n$.

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

$\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 $\textstyle a$ is a quadratic residue, same idea holds for $\textstyle -a$):

$\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 $\textstyle n$, make the choice of $\textstyle t$ uniform and random and moreover include some authenticity checks for $\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 r is the square of a or − 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