Cocks IBE scheme is an
identity based encryption ID-based encryption, or identity-based encryption (IBE), is an important primitive of ID-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user ...
system proposed by
Clifford Cocks
Clifford Christopher Cocks (born 28 December 1950) is a British mathematician and cryptographer.
In 1973, while working at the United Kingdom Government Communications Headquarters (GCHQ), he invented a public-key cryptography algorithm equiv ...
in 2001.
[Clifford Cocks]
An Identity Based Encryption Scheme Based on Quadratic Residues
, ''Proceedings of the 8th IMA International Conference on Cryptography and Coding'', 2001 The security of the scheme is based on the hardness of the
quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
.
Protocol
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 deterministic 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
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
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 The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
, 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
An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
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 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
Identity-based cryptography