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:

a public RSA-modulus $\textstyle n = pq$ , where $\textstyle p,q,\,p \equiv q \equiv 3 \mod 4$ are prime and kept secret,
the message and the cipher space $\textstyle \mathcal{M} = \left\{-1,1\right\}, \mathcal{C} = \mathbb{Z}_n$ and
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

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$ ),
computes $\textstyle r = a^{(n+5-p-q)/8} \bmod n$ (which fulfils either $\textstyle r^2 = a \bmod n$ or $\textstyle r^2 = -a \bmod n$ , see below) and
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

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

Decrypt

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

computes $\alpha = c_1 + 2r$ if $r^2=a$ or $\alpha = c_2 + 2r$ otherwise, and
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 \bmod 4$ (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^{(n+5-p-q)/8}\right)^2 \\ &= \left(a^{(n+5-p-q - \Phi(n))/8}\right)^2 \\ &= \left(a^{(n+5-p-q - (p-1)(q-1))/8}\right)^2 \\ &= \left(a^{(n+5-p-q - n+p+q-1)/8}\right)^2 \\ &= \left(a^{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}\right)(\pm 1)^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

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