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.

1 Protocol
2 Security
3 Problems
4 References

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^{\frac{n%2B5-p-q}{8}} \mod n$ (which fulfils either $\textstyle r^2 = a \mod n$ or $\textstyle r^2 = -a \mod 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 %2B at_1^{-1} \mod 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 %2B 2r$ if $r^2=a$ or $\alpha = c_2 %2B 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 \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%2B5-p-q}{8}}\right)^2 \\ &= \left(a^{\frac{n%2B5-p-q - \Phi\left(n\right)}{8}}\right)^2 \\ &= \left(a^{\frac{n%2B5-p-q - (p-1)(q-1)}{8}}\right)^2 \\ &= \left(a^{\frac{n%2B5-p-q - n%2Bp%2Bq-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%2B2r}{n}\right) &= \left(\frac{t %2B at^{-1} %2B2r}{n}\right) = \left(\frac{t\left(1%2Bat^{-2} %2B2rt^{-1}\right)}{n}\right) \\ &= \left(\frac{t\left(1%2Br^2t^{-2} %2B2rt^{-1}\right)}{n}\right) = \left(\frac{t\left(1%2Brt^{-1}\right)^2}{n}\right) \\ &= \left(\frac{t}{n}\right) \left(\frac{1%2Brt^{-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

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