Cocks IBE scheme

Protocol

Setup

The PKG chooses:

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

Extract

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

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

Encrypt

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

1. chooses random ${\displaystyle t_1}$ with ${\displaystyle m=\left(\frac{t_1}{n}\right)}$,
2. chooses random ${\displaystyle t_2}$ with ${\displaystyle m=\left(\frac{t_2}{n}\right)}$, different from ${\displaystyle t_1}$,
3. computes ${\displaystyle c_1=t_1+a{t}_1^{-1}(\mathrm{mod}n)}$ and ${\displaystyle c_2=t_2-a{t}_2^{-1}(\mathrm{mod}n)}$ and
4. sends ${\displaystyle 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 p\equiv q\equiv 3(\mathrm{mod}4)}$ (i.e. ${\displaystyle \left(\frac{-1}{p}\right)=\left(\frac{-1}{q}\right)=-1}$) and ${\displaystyle \left(\frac{a}{n}\right)\Rightarrow \left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)}$, either ${\displaystyle a}$ or ${\displaystyle -a}$ is a quadratic residue modulo ${\displaystyle n}$.

Therefore, ${\displaystyle r}$ is a square root of ${\displaystyle a}$ or ${\displaystyle -a}$:

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

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 a}$ is a quadratic residue, same idea holds for ${\displaystyle -a}$):

${\displaystyle \begin{array}{cc}\left(\frac{s+2r}{n}\right)& =\left(\frac{t+a{t}^{-1}+2r}{n}\right)=\left(\frac{t\left(1+a{t}^{-2}+2r{t}^{-1}\right)}{n}\right)\\ & =\left(\frac{t\left(1+r^2{t}^{-2}+2r{t}^{-1}\right)}{n}\right)=\left(\frac{t{\left(1+r{t}^{-1}\right)}^2}{n}\right)\\ & =\left(\frac{t}{n}\right){\left(\frac{1+r{t}^{-1}}{n}\right)}^2=\left(\frac{t}{n}\right)(\pm 1{)}^2=\left(\frac{t}{n}\right)\end{array}}$