Cocks IBE scheme

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.

Contents

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 = (c1,c2) for user ID, he

  1. computes α = c1 + 2r if r2 = a or α = c2 + 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

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Clifford Cocks — Born 28 December 1950 Prestbury, Cheshire, United Kingdom Nationality British Fields …   Wikipedia

  • Clifford Cocks — Clifford Christopher Cocks, CB,[1] (* 28. Dezember 1950[2]) ist ein britischer Mathematiker und Kryptographer am GCHQ, der den weit verbreiteten Verschlüsselungsalgorithmus, der nun unter RSA bekannt ist, erfand; und das etwa drei Jahre bevor er… …   Deutsch Wikipedia

  • Public-key cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”