 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:
 a public RSAmodulus , where are prime and kept secret,
 the message and the cipher space and
 a secure public hash function .
Extract
When user wants to obtain his private key, he contacts the PKG through a secure channel. The PKG
 derives with by a determistic process from (e.g. multiple application of ),
 computes (which fulfils either or , see below) and
 transmits to the user.
Encrypt
To encrypt a bit (coded as /) for , the user
 chooses random with ,
 chooses random with , different from ,
 computes and and
 sends to the user.
Decrypt
To decrypt a ciphertext s = (c_{1},c_{2}) for user ID, he
 computes α = c_{1} + 2r if r^{2} = a or α = c_{2} + 2r otherwise, and
 computes .
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 (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
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
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 keyprivacy, 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
Categories:
Wikimedia Foundation. 2010.