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.

Protocol

Setup

The PKG chooses:

a public RSA-modulus $\textstyle n=pq$ , where $\textstyle p,q,\,p\equiv q\equiv 3{\bmod {4}}$ are prime and kept secret,
the message and the cipher space $\textstyle {\mathcal {M}}=\left\{-1,1\right\},{\mathcal {C}}=\mathbb {Z} _{n}$ and
a secure public hash function $\textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}$ .

Extract

When user $\textstyle ID$ wants to obtain his private key, he contacts the PKG through a secure channel. The PKG

derives $\textstyle a$ with $\textstyle \left({\frac {a}{n}}\right)=1$ by a deterministic process from $\textstyle ID$ (e.g. multiple application of $\textstyle f$ ),
computes $\textstyle r=a^{(n+5-p-q)/8}{\pmod {n}}$ (which fulfils either $\textstyle r^{2}=a{\pmod {n}}$ or $\textstyle r^{2}=-a{\pmod {n}}$ , see below) and
transmits $\textstyle r$ to the user.

Encrypt

To encrypt a bit (coded as $\textstyle 1$ / $\textstyle -1$ ) $\textstyle m\in {\mathcal {M}}$ for $\textstyle ID$ , the user

chooses random $\textstyle t_{1}$ with $\textstyle m=\left({\frac {t_{1}}{n}}\right)$ ,
chooses random $\textstyle t_{2}$ with $\textstyle m=\left({\frac {t_{2}}{n}}\right)$ , different from $\textstyle t_{1}$ ,
computes $\textstyle c_{1}=t_{1}+at_{1}^{-1}{\pmod {n}}$ and $c_{2}=t_{2}-at_{2}^{-1}{\pmod {n}}$ and
sends $\textstyle s=(c_{1},c_{2})$ to the user.

Decrypt

To decrypt a ciphertext $s=(c_{1},c_{2})$ for user $ID$ , he

computes $\alpha =c_{1}+2r$ if $r^{2}=a$ or $\alpha =c_{2}+2r$ otherwise, and
computes $m=\left({\frac {\alpha }{n}}\right)$ .

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 $\textstyle p\equiv q\equiv 3{\pmod {4}}$ (i.e. $\left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1$ ) and $\textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)$ , either $\textstyle a$ or $\textstyle -a$ is a quadratic residue modulo $\textstyle n$ .

Therefore, $\textstyle r$ is a square root of $\textstyle a$ or $\textstyle -a$ :

{\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}}

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

{\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}}

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 $\textstyle n$ , make the choice of $\textstyle t$ uniform and random and moreover include some authenticity checks for $\textstyle t$ (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 $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 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

[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

[1]

Fahrer / Team für die Suche eingeben: