• Images
• Videos
• Documents
• Books
• Articles

Protocol

Setup

The PKG chooses:

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

Extract

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

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

Encrypt

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

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

Decrypt

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

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

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

Therefore, r {\displaystyle \textstyle r} is a square root of a {\displaystyle \textstyle a} or − a {\displaystyle \textstyle -a} :²

r 2 ≡ ( a ( n + 5 − p − q ) / 8 ) 2 mod n ≡ ( a ( p ∗ q + 4 + 1 − p − q ) / 8 ) 2 mod n ≡ ( a ( ( p − 1 ) ( q − 1 ) + 4 ) / 8 ) 2 mod n ≡ ( a 0.5 ∗ a ( ( p − 1 ) ( q − 1 ) ) / 8 ) 2 mod n ≡ a ∗ a ( p − 1 ) / 2 ∗ a ( q − 1 ) / 2 mod n ≡ { a mod n | a  is a quadratic residue mod n − a mod n | − a  is a quadratic residue mod n {\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 a {\displaystyle \textstyle a} is a quadratic residue, same idea holds for − a {\displaystyle \textstyle -a} ):

( s + 2 r n ) = ( t + a t − 1 + 2 r n ) = ( t ( 1 + a t − 2 + 2 r t − 1 ) n ) = ( t ( 1 + r 2 t − 2 + 2 r t − 1 ) n ) = ( t ( 1 + r t − 1 ) 2 n ) = ( t n ) ( 1 + r t − 1 n ) 2 = ( t n ) ( ± 1 ) 2 = ( t n ) {\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 n {\displaystyle \textstyle n} , make the choice of t {\displaystyle \textstyle t} uniform and random and moreover include some authenticity checks for t {\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 r {\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 http://www.cesg.gov.uk/site/ast/idpkc/media/ciren.pdf ↩

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 https://inspire.redlands.edu/cas_honors/502 ↩