Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Cocks IBE scheme
open-in-new
<h2 id="protocol">Protocol</h2> <h3>Setup</h3> <p>The PKG chooses: </p> <ol><li>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,</li> <li>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</li> <li>a secure public hash function f : { 0 , 1 } ∗ → Z n {\displaystyle \textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}} .</li></ol> <h3>Extract</h3> <p>When user I D {\displaystyle \textstyle ID} wants to obtain his private key, he contacts the PKG through a secure channel. The PKG </p> <ol><li>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} ),</li> <li>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</li> <li>transmits r {\displaystyle \textstyle r} to the user.</li></ol> <h3>Encrypt</h3> <p>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 </p> <ol><li>chooses random t 1 {\displaystyle \textstyle t_{1}} with m = ( t 1 n ) {\displaystyle \textstyle m=\left({\frac {t_{1}}{n}}\right)} ,</li> <li>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}} ,</li> <li>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</li> <li>sends s = ( c 1 , c 2 ) {\displaystyle \textstyle s=(c_{1},c_{2})} to the user.</li></ol> <h3>Decrypt</h3> <p>To decrypt a ciphertext s = ( c 1 , c 2 ) {\displaystyle s=(c_{1},c_{2})} for user I D {\displaystyle ID} , he </p> <ol><li>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</li> <li>computes m = ( α n ) {\displaystyle m=\left({\frac {\alpha }{n}}\right)} .</li></ol> <p>Note that here we are assuming that the encrypting entity does not know whether I D {\displaystyle ID} has the <a href="/facts/Quadratic_residue/rHD2uQdQ">square root</a> 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. </p> <h3>Correctness</h3> <p>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 <a href="/facts/Quadratic_residue/rHD2uQdQ">quadratic residue</a> modulo n {\displaystyle \textstyle n} . </p><p>Therefore, r {\displaystyle \textstyle r} is a square root of a {\displaystyle \textstyle a} or − a {\displaystyle \textstyle -a} :<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> 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}}} <p>Where the last step is the result of a combination of <a href="/facts/Euler%27s_Criterion/JkbpqqB1">Euler's Criterion</a> and the <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a>. </p><p>Moreover, (for the case that a {\displaystyle \textstyle a} is a quadratic residue, same idea holds for − a {\displaystyle \textstyle -a} ): </p> ( 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}}} <h2 id="security">Security</h2> <p>It can be shown that breaking the scheme is equivalent to solving the <a href="/facts/Quadratic_residuosity_problem/b8B2ptVQ">quadratic residuosity problem</a>, 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 <a href="/facts/Adaptive_chosen_ciphertext_attack/SCKGPjI6">adaptive chosen ciphertext attack</a> can be mounted by altering packets that transmit a single bit and using the <a href="/facts/Random_oracle/wK7MhxDq">oracle</a> to observe the effect on the decrypted bit). </p> <h2 id="problems">Problems</h2> <p>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 <i>a</i> or −<i>a</i>), which is only acceptable for environments in which session keys change infrequently. </p><p>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. </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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 <a href="http://www.cesg.gov.uk/site/ast/idpkc/media/ciren.pdf" target="_blank">http://www.cesg.gov.uk/site/ast/idpkc/media/ciren.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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 <a href="https://inspire.redlands.edu/cas_honors/502" target="_blank">https://inspire.redlands.edu/cas_honors/502</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>