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:

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

Extract

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

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

Encrypt

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

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

Decrypt

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

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

Note that here we are assuming that the encrypting entity does not know whether ${\displaystyle ID}$ has the square root ${\displaystyle r}$ of ${\displaystyle a}$ or ${\displaystyle -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 ${\displaystyle \textstyle p\equiv q\equiv 3{\pmod {4}}}$ (i.e. ${\displaystyle \left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1}$) and ${\displaystyle \textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)}$, either ${\displaystyle \textstyle a}$ or ${\displaystyle \textstyle -a}$ is a quadratic residue modulo ${\displaystyle \textstyle n}$.

Therefore, ${\displaystyle \textstyle r}$ is a square root of ${\displaystyle \textstyle a}$ or ${\displaystyle \textstyle -a}$ ^[2] :

${\displaystyle {\begin{aligned}r^{2}&\equiv \left(a^{(n+5-p-q)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{(p*q+4+1-p-q)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{((p-1)(q-1)+4)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{0.5}*a^{((p-1)(q-1))/8}\right)^{2}\mod {n}\\&\equiv a*a^{(p-1)/2}*a^{(q-1)/2}\mod {n}\\&\equiv {\begin{cases}a\mod {n}&|a{\text{ is a quadratic residue}}\mod {n}\\-a\mod {n}&|-a{\text{ is a quadratic residue}}\mod {n}\end{cases}}\end{aligned}}}$

Where the last step is the result of a combination of Euler's Criterion and the Chinese remainder theorem.

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

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

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

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
2. Prager, S. (2011). The Cocks IBE Scheme: The Legendre Symbol and Quadratic Reciprocity (Undergraduate honors thesis, University of Redlands). Retrieved from https://inspire.redlands.edu/cas_honors/502