Cocks IBE scheme
Encyclopedia
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
.
wants to obtain his private key, he contacts the PKG through a secure channel. The PKG
/
) 
for 
, the user
for user 
, he
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.
(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 
):
, 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).
is the square of 
or 
), 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.
Clifford Cocks
Clifford Christopher Cocks, CB, is a British mathematician and cryptographer at GCHQ.He invented the widely-used encryption algorithm now commonly known as RSA, about three years before it was independently developed by Rivest, Shamir, and Adleman at MIT...
in 2001 . The security of the scheme is based on the hardness of the quadratic residuosity problem
Quadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
.
Setup
The PKG chooses:- a public RSA-modulus
, 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 for user , he
- computes
if 
or 
otherwise, and - 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 (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 is the square of or ), 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.