Protocol Cocks IBE scheme
1 protocol
1.1 setup
1.2 extract
1.3 encrypt
1.4 decrypt
1.5 correctness
protocol
setup
the pkg chooses:
extract
when user
i
d
{\displaystyle \textstyle id}
wants obtain private key, contacts pkg through secure channel. pkg
encrypt
to encrypt bit (coded
1
{\displaystyle \textstyle 1}
/
−
1
{\displaystyle \textstyle -1}
)
m
∈
m
{\displaystyle \textstyle m\in {\mathcal {m}}}
i
d
{\displaystyle \textstyle id}
, user
decrypt
to decrypt ciphertext
s
=
(
c
1
,
c
2
)
{\displaystyle s=(c_{1},c_{2})}
user
i
d
{\displaystyle id}
, he
note here assuming encrypting entity not know whether
i
d
{\displaystyle id}
has square root
r
{\displaystyle r}
of
a
{\displaystyle a}
or
−
a
{\displaystyle -a}
. in case have send ciphertext both cases. information known encrypting entity, 1 element needs sent.
correctness
first note 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}
) ,
(
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}
quadratic residue modulo
n
{\displaystyle \textstyle n}
.
therefore,
r
{\displaystyle \textstyle r}
square root of
a
{\displaystyle \textstyle a}
or
−
a
{\displaystyle \textstyle -a}
:
r
2
=
(
a
(
n
+
5
−
p
−
q
)
/
8
)
2
=
(
a
(
n
+
5
−
p
−
q
−
Φ
(
n
)
)
/
8
)
2
=
(
a
(
n
+
5
−
p
−
q
−
(
p
−
1
)
(
q
−
1
)
)
/
8
)
2
=
(
a
(
n
+
5
−
p
−
q
−
n
+
p
+
q
−
1
)
/
8
)
2
=
(
a
4
/
8
)
2
=
±
a
{\displaystyle {\begin{aligned}r^{2}&=\left(a^{(n+5-p-q)/8}\right)^{2}\\&=\left(a^{(n+5-p-q-\phi (n))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-(p-1)(q-1))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-n+p+q-1)/8}\right)^{2}\\&=\left(a^{4/8}\right)^{2}\\&=\pm a\end{aligned}}}
moreover, (for case
a
{\displaystyle \textstyle a}
quadratic residue, same idea holds
−
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}}}
Comments
Post a Comment