Cocks IBE scheme


Cocks IBE scheme is an identity based encryption system proposed by Clifford Cocks in 2001. 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, where are prime and kept secret,
  2. the message and the cipher space and
  3. a secure public hash function.

    Extract

When user wants to obtain his private key, he contacts the PKG through a secure channel. The PKG
  1. derives with by a deterministic process from ,
  2. computes and
  3. transmits to the user.

    Encrypt

To encrypt a bit for, the user
  1. chooses random with,
  2. chooses random with, different from ,
  3. computes and and
  4. sends to the user.

    Decrypt

To decrypt a ciphertext for user, he
  1. computes if or otherwise, and
  2. computes.
Note that here we are assuming that the encrypting entity does not know whether has the square root of or. 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 and, either or is a quadratic residue modulo.
Therefore, is a square root of or :
Moreover, :

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, make the choice of uniform and random and moreover include some authenticity checks for .

Problems

A major disadvantage 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, 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.