Identity based encryption system
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
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
.
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
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
:
![{\displaystyle {\begin{aligned}r^{2}&=\left(a^{(n+5-p-q)/8}\right)^{2}\\&=\left(a^{(n+5-p-q-\Phi (n))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-(p-1)(q-1))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-n+p+q-1)/8}\right)^{2}\\&=\left(a^{4/8}\right)^{2}\\&=\pm a\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cf71c5749396d987b236525406f2efda015ad32)
Moreover, (for the case that
is a quadratic residue, same idea holds for
):
![{\displaystyle {\begin{aligned}\left({\frac {s+2r}{n}}\right)&=\left({\frac {t+at^{-1}+2r}{n}}\right)=\left({\frac {t\left(1+at^{-2}+2rt^{-1}\right)}{n}}\right)\\&=\left({\frac {t\left(1+r^{2}t^{-2}+2rt^{-1}\right)}{n}}\right)=\left({\frac {t\left(1+rt^{-1}\right)^{2}}{n}}\right)\\&=\left({\frac {t}{n}}\right)\left({\frac {1+rt^{-1}}{n}}\right)^{2}=\left({\frac {t}{n}}\right)(\pm 1)^{2}=\left({\frac {t}{n}}\right)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e92c5bea73e94c69db06021dbef7a2805422326)
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 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
- ^ 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