Cocks IBE scheme

The PKG chooses:

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

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

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

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

1. chooses random $\backslash textstyle\; t\_1$ with $\backslash textstyle\; m\; =\; \backslash left(\backslash frac\{t\_1\}\{n\}\backslash right)$,
2. chooses random $\backslash textstyle\; t\_2$ with $\backslash textstyle\; m\; =\; \backslash left(\backslash frac\{t\_2\}\{n\}\backslash right)$, different from $\backslash textstyle\; t\_1$,
3. computes $\backslash textstyle\; c\_1\; =\; t\_1\; +\; at\_1^\{-1\}\; \backslash pmod\; n$ and $c\_2=\; t\_2\; -\; at\_2^\{-1\}\; \backslash pmod\; n$ and
4. sends $\backslash textstyle\; s=(c\_1,\; c\_2)$ to the user.

To decrypt a ciphertext $s=(c\_1,\; c\_2)$ for user $ID$, he

1. computes $\backslash alpha\; =\; c\_1\; +\; 2r$ if $r^2=a$ or $\backslash alpha\; =\; c\_2\; +\; 2r$ otherwise, and
2. computes $m\; =\; \backslash left(\backslash frac\{\backslash alpha\}\{n\}\backslash 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.

First note that since $\backslash textstyle\; p\; \backslash equiv\; q\; \backslash equiv\; 3\; \backslash pmod\; 4$ (i.e. $\backslash left(\backslash frac\{-1\}\{p\}\backslash right)\; =\; \backslash left(\backslash frac\{-1\}\{q\}\backslash right)\; =\; -1$) and $\backslash textstyle\; \backslash left(\backslash frac\{a\}\{n\}\backslash right)\; \backslash Rightarrow\; \backslash left(\backslash frac\{a\}\{p\}\backslash right)\; =\; \backslash left(\backslash frac\{a\}\{q\}\backslash right)$, either $\backslash textstyle\; a$ or $\backslash textstyle\; -a$ is a quadratic residue modulo $\backslash textstyle\; n$.

Therefore, $\backslash textstyle\; r$ is a square root of $\backslash textstyle\; a$ or $\backslash textstyle\; -a$: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

: $$

\begin{align}

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

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

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

: $$

\begin{align}

\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^2t^{-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{align}

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

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.

Category:Identity-based cryptography