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

edit

Setup

edit

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

edit

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   (e.g. multiple application of  ),
  2. computes   (which fulfils either   or  , see below) and
  3. transmits   to the user.

Encrypt

edit

To encrypt a bit (coded as  / )   for  , the user

  1. chooses random   with  ,
  2. chooses random   with  , different from  ,
  3. computes   and   and
  4. sends   to the user.

Decrypt

edit

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

edit

First note that since   (i.e.  ) and  , either   or   is a quadratic residue modulo  .

Therefore,   is a square root of   or  :

 

Moreover, (for the case that   is a quadratic residue, same idea holds for  ):

 

Security

edit

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   (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

edit

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 (when it is not known whether   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

edit
  1. ^ Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues Archived 2007-02-06 at the Wayback Machine, Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001