Cocks IBE scheme

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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+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
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$ with $\textstyle m = \left(\frac{t}{n}\right)$ ,
computes $\textstyle c = t \pm at^{-1} \mod n$ and
sends $\textstyle c$ to the user.

Decrypt

To decrypt a ciphertext $\textstyle c$ for user $\textstyle ID$ , he

computes $\textstyle \alpha = c + 2r$ and
computes $\textstyle m = \left(\frac{\alpha}{n}\right)$ .

Note that if the encrypting entity does not know whether $\textstyle ID$ has the square root $\textstyle r$ of $\textstyle a$ or $\textstyle -a$ , it has to send $\textstyle c$ both for $\textstyle +$ and for $\textstyle -$ . Thus, the amount of data to transmit doubles. Therefore, it would be practical to make this information public available.

Correctness

First note that since $\textstyle p \equiv q \equiv 3 \mod n$ ( $\textstyle \Rightarrow \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 128 * 1024 bit = 16 KByte, which is only acceptable for environments in which session keys change infrequently.

References

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

Retrieved from "http://en.wikipedia.org/wiki/Cocks_IBE_scheme"