$H_{1}:\\{0,1\\}^{*}\rightarrow\mathbb{G}_{1},H_{2}:\mathbb{G}_{2}\rightarrow\\{0,1\\}^{n}$,
$H_{3}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{q}^{*}$, and
$H_{4}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$. KGC selects an element
$s_{0}\in\mathbb{Z}_{q}^{*}$ known as a master secret key, computes public key
$P_{0}=s_{0}P$, and sends $P_{0}$ to $CPC^{1}$.

On given parameters $pp$, $CPC^{i}$ selects its secret key
$s_{i}\in\mathbb{Z}_{q}^{*}$, and compute its public key $P_{i}=s_{i}P$ and
sets systems public key as $Y_{i}=s_{i}Y_{(i-1)}$. $CPC^{i}$ sends $Y_{i}$ to
$CPC^{i+1}$. $CPC^{i}$ can verify correctness of $Y_{i-1}$ using
$e(Y_{i-1},P_{i})\overset{?}{=}e(Y_{i},P)$, where $Y_{0}=P_{0}$. Now,
$CPC^{n}$ sets the system public key as $Y=Y_{n}=s_{n}s_{n-1}s_{0}P$ and sends
it to the KGC. It is noted the system’s public key is derived sequentially
using each secret key of CPC. Now, KGC publishes the parameter
$pp=<q,e,P,P_{0},\mathbb{G}_{1},\mathbb{G}_{2},H_{1},H_{2},H_{3},H_{4},Y,P_{1},..P_{n}>$
and the parameter $s_{0}$ is kept secret.

  2. 2.

KeyGeneration: On given identity $ID$, the user’ private key $S_{ID}$ is
computed as follows.

     * •

KeyIssuing. User picks an element $x\in\mathbb{Z}_{q}^{*}$, computes $X=xP$,
$D_{ID}=xQ_{ID}$, where $Q_{ID}=H_{1}(ID)$, $ID$ is his identity, and sends
$<X,ID,D_{ID}>$ to the KGC. KGC validates the user identity along with other
receiving parameters, using $e(Q_{ID},X)\overset{?}{=}e(D_{ID},P)$, computes
the blinded partial private key $D_{0}=s_{0}D_{ID}$ and $X_{0}=s_{0}X$, and
sends $<D_{0},X_{0}>$ to the user. The user validates the parameter
$<D_{0},X_{0}>$ using $e(D_{ID},X_{0})\overset{?}{=}e(D_{0},X)$.

     * •

KeySecuring. On receiving parameter $<D_{0},X_{0}>$, user sends
$<ID,D_{i-1},X_{i-1}>$ to $CPC^{i}$, ($i=1,2,..,n$) and asks it for the key
protection. $CPC^{i}$ checks the correctness of parameters using
$e(Q_{ID},X_{i-1})\overset{?}{=}e(D_{i-1},P)$ and compute $D_{i}=s_{i}D_{i-1}$
and $X_{i}=s_{i}X_{i-1}$, and send $D_{i}$ to the user. The user verifies the
correctness of the blinded partial private key using
$e(D_{i},P)\overset{?}{=}e(D_{i-1},P_{i})$. Finally, user gets
$D_{n}=s_{n}D_{n-1}$ from the last $CPC^{n}$.

     * •

KeyExtraction. User retrieves private key
$d_{ID}=x^{-1}D_{n}=s_{0}s_{1}....Q_{ID}$ that can be verified using
$e(d_{ID},P)\overset{?}{=}e(Q_{I}D,Y)$.

  3. 3.

Encryption: On given message $M\in\\{0,1\\}^{n}$, $pp$ and recipient identity
$ID$, sender chooses an element $z\in\\{0,1\\}^{n}$, sets $r=H_{3}(z,M)$,
$g=e(Q_{ID},Y)$, where $Q_{ID}=H_{1}{ID}$, and outputs the ciphertext
$C=<U,V,W>=<rP,zH_{2}(g^{r}),MH_{4}(z)>$ .

  4. 4.

Decryption: On given ciphertext $C=<U,V,W>$ and private key $S_{ID}$, receiver
sets $g^{\prime}=e(U,d_{ID})$ and $z^{\prime}=V\oplus H_{2}(g^{\prime})$. Now,
recipient extracts message $M=W\oplus H_{4}(z^{\prime})$ and sets
$r^{\prime}=H_{3}(z^{\prime},M)$. The recipient accepts the message $M$ is
valid if $U=r^{\prime}P$ otherwise $M$ is invalid.

This completes the full description of our ESKI-IBE scheme.

###  3.3 Proposed Escrow-free ID-based Signature Scheme

Here, we construct the proposed EF-IBS scheme based on the idea of the
proposed ESKI scheme. The proposed EF-IBS scheme involves of four randomized
PPT algorithms: Setup, keyGeneration, Signing and Verification. They are
defined as follows.

  1. 1.

Setup: The KGC considers the security parameter $k$ and two groupas
$\mathbb{G}_{1}$ (additive group) and $\mathbb{G}_{2}$ (multiplicative group);
both have order $q$, where $q$ is the length of $k$-bit. Suppose $P$ be a
generator of $\mathbb{G}_{1}$, a bilinear function is
$e:\mathbb{G}_{1}\times\mathbb{G}_{1}\rightarrow\mathbb{G}_{2}$ that maps the
$\mathbb{G}_{1}$ to $\mathbb{G}_{2}$ and,
$H_{1}:\\{0,1\\}^{*}\rightarrow\mathbb{G}_{1}$,
$H_{2}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}^{*}$ and
$H_{3}:\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$ are three cryptographic
hash functions.

The KGC chooses an element $s_{0}\in\mathbb{Z}_{q}^{*}$ (master key), evaluate
$P_{0}=s_{0}P$ (Public key), $g=e(P,P)$ and simultaneously sends $P_{0}$ to
each CPCs.

For given $P_{0}$, $CPC^{i}$ chooses an element $s_{i}\in\mathbb{Z}_{q}^{*}$
(their secret keys), evaluate $P_{i}=s_{i}P$ (their public keys) and
$Y_{i}=s_{i}P_{0}$ (system public key shares), where $1\leq i\leq n$. Now,
$CPC^{i}$ sends $<P_{i},Y_{i}>$ to the KGC and keeps $s_{i}$ secret.

KGC verifies the received parameters $<P_{i},Y_{i}>$ using equation
$Y_{i}=s_{0}P_{i}$, and computes the system public key as
$Y=\sum_{i=1}^{n}Y_{i}=s_{0}(s_{1}+s_{2}+...+s_{n})P$. Now, KGC publishes the
parameter
$pp=<q,e,g,P,P_{0},\mathbb{G}_{1},\mathbb{G}_{2},H_{1},H_{2},H_{3},P_{1},..P_{n},Y>$
and keeps safe its master key $s_{0}$.

  2. 2.

KeyGeneration: It involves three sub-algorithms: KeyIssuing, KeySecuring and
KeyExtraction, define as follows:

     * •

KeyIssuing. The user requests to the KGC for the partial private key on his
identity $ID$. The KGC authenticates the user identity $ID$ and computes the
partial private key as $P_{ID}=s_{0}Q_{ID}$, where $Q_{ID}=H_{1}(ID)$, and
sends $P_{I}D$ to the user.

     * •

KeySecuring. The user simultaneously asks $CPC^{i}$ for protecting the
requested partial private key $P_{ID}$. The $CPC^{i}$ computes the private key
share $X_{i}=s_{i}P_{ID}$, using its secret key $s_{i}$ and sends them to the
user. The user can verify the received parameters using
$e(X_{i},P)\overset{?}{=}e(P_{ID},P_{i})$.

     * •

KeyExtraction. On given private key share $X_{i}$, the user combines and
computes his original private key as
$d_{ID}=\sum_{i=1}^{n}X_{i}=s_{0}(s_{1}+s_{2}+...+s_{n})Q_{ID}$.

Note that $d_{ID}$ is the original private key against the identity $ID$,
which can be verified using $e(d_{ID},P)\overset{?}{=}e(Q_{ID},Y)$.

  3. 3.

Signing. The sender chooses an element $r\in\mathbb{Z}_{p}^{*}$, and sign a
given message $m$ to compute the signature $\sigma=<R,S>$ using his private
key $d_{ID}$, where $R=rP$, and $S=r^{-1}(H_{2}(m)P+H_{3}(R)d_{ID})$.

  4. 4.

Verification. On given message-signature pair $<m,S,R>$, sender’s $ID$, and
param, the recipient verifies the signature-message pair using (3.2).

$e(S,R)\overset{?}{=}g^{H_{2}(m)}e(Q_{I}D,Y)^{H_{3}(R)}$ (3.2)

This completes the full description of our EF-IBS scheme.

###  3.4 Security Analysis

This section gives the security of proposed ESKI-IBE and EF-IBS schemes.

####  3.4.1 Security Analysis of ESKI-IBE

######  Theorem 3.1.

The proposed ESKI-IBE is correct.

###### Proof.

Proof. The correctness of our proposed ESKI-IBE scheme is defined as follows.

$\displaystyle W\oplus H_{4}(z^{\prime})$ $\displaystyle=W\oplus H_{4}(V\oplus
H_{2}(g^{\prime}))$ $\displaystyle=W\oplus H_{4}(V\oplus H_{2}(e(U,d_{ID})))$
$\displaystyle=M\oplus H_{4}(z)\oplus H_{4}(V\oplus H_{2}(e(U,d_{ID})))$
$\displaystyle=M\oplus H_{4}(z)\oplus H_{4}(z\oplus
H_{2}(e(s_{0}s_{1}....s_{n}Q_{ID},rP))\oplus H_{2}(e(U,d_{ID})))$
$\displaystyle=M\oplus H_{4}(z)\oplus H_{4}(z\oplus H_{2}(e(d_{ID},U))\oplus
H_{2}(e(U,d_{ID})))$ $\displaystyle=M\oplus H_{4}(z)\oplus H_{4}(z)=M$

Thus, the proposed ESKI-IBE scheme is corrected. ∎

######  Theorem 3.2.

Assume $H_{1}$, $H_{2}$, $H_{3}$, and $H_{4}$ are four random oracle models,
and the BDH problem is infeasible to solve. Our proposed ESKI-IBE scheme is
semantically secure against IND-ID-CCA attack. Assume there exists an
adaptively chosen message $M_{i}$ and chosen identity $ID_{i}$. Adversary
$Adv(q_{pp},q_{p},q_{d},q_{1},q_{2},q_{3},q_{4},t,\epsilon)$ runs at most
Partial-Key-Extract queries $q_{pp}$, private-key-Extract queries $q_{p}$,
decryption queries $q_{d}$, $H_{1}$ queries $q_{1}$, $H_{2}$ queries $q_{2}$,
$H_{3}$ queries $q_{3}$, and $H_{4}$ queries $q_{4}$, respectively. Adversary
$Adv_{k}$ can break our proposed ESKI-IBE scheme in polynomial time $t$ and
success probability $\epsilon$. Then, there exists a simulator $B$ that helps
an adversary $Adv_{k}$ against ESKI-IBE and can solve the BDH problem with
probability $\epsilon^{\prime}$.

$\epsilon^{\prime}\geq\frac{1}{(q_{3}+q_{4})}\Bigg{(}\big{(}\frac{\epsilon(k)}{e(1+nq_{pp}q_{p}+q_{d})q_{2}}+1\big{)}\big{(}1-\frac{2}{q}\big{)}^{q_{d}}-1\Bigg{)}$
(3.3)

and $t^{\prime}=t+t_{s}+q_{pp}+q_{p}+q_{d}+q_{1}+q_{2}+q_{3}+q_{4}$
where $t_{s}$ is algorithm B’s simulation time.

###### Proof.

We proceed with the security reduction through the followings steps:

Reduction 1. Construct IND-CCA adversary $B$ against $BasicPubhy$ of [1] with
the help of IND-ID-CCA adversary $Adv$ against ESKI-IBE.

Given IND-ID-CCA adversary $Adv$ against ESKI-IBE, we first construct IND-CCA
adversary B against BasicPubhy. B obtains public key
$K_{Pub}=<P,P_{Pub},D_{ID},H_{2},H_{3},H_{4}>$ from $Adv$ during game against
$BasicPub^{hy}$.

Setup: $B$ helps $Adv_{k}$ by giving the public parameter
$pp=<P,P_{P}ub,H_{1},H_{2},H_{3},H_{4}>$. $H_{1}$ queries are simulated in the
same as in Theorem 3.2.

Phase1: At any time during attacks , the $Adv_{k}$ runs following queries.

  * •

Partial key Extraction queries. After executing $H_{1}$ query, $B$ gets the
$D_{i}\in\mathbb{G}_{1}$ such that $H_{1}(ID_{i})=D_{i}$. Assume tuples
$<ID_{i},D_{i},b_{i},c_{i}>$ against $ID_{i}$ in $H_{1}^{List}$ list, $B$
makes a list $PP^{List}$ of tuples $<ID_{j},D_{j},S_{j},b_{j},c_{j}>$ and do
the following:

    * –

Aborts, if $c_{i}=1$. That means B’s attack on BasicPub failed.

    * –

If $c_{i}=0$, we know $H_{1}(ID_{i})=b_{i}P$. Compute
$S_{i}=b_{i}P_{Pub}\in\mathbb{G}_{1}$. Note that $S_{i}=s_{0}D_{i}$ is
associated with a partial private key corresponding to $ID_{i}$.

    * –

$B$ then adds an entry $<ID_{i},D_{i},S_{i},b_{i},c_{i}>$ in $H_{1}^{List}$
list and gives $S_{i}$ to $Adv_{k}$.

  * •

Private Key Extraction queries. After executing partial private key extraction
queries, $B$ gets $S_{i}\in\mathbb{G}_{1}$ such that $S_{i}=b_{i}P_{Pub}$.
Assume tuples $<ID_{i},D_{i},b_{i},c_{i}>$ against $ID_{i}$ in $H_{1}^{List}$
list and tuples $<ID_{i},D_{i},S_{i},b_{i},c_{i}>$ against $S_{i}$ in
$PP^{P}{List}$ list, $B$ do the following:

    * –

Aborts if $c_{i}=1$. That means $B$’s attack on BasicPub is failed.

    * –

If $c_{i}=0$, we know $S_{i}=b_{i}P_{P}ub$. Computes
$S_{IDi}=b_{i}Y\in\mathbb{G}_{1}$. Note that
$S_{IDi}=s_{0}s_{1}..s_{n}D_{i}\in\mathbb{G}_{1}$ is associated with private
key correspond to $ID_{i}$ and outputs to $Adv_{k}$.

  * •

Decryption Query. Suppose $Adv_{k}$ runs an decryption on given input
$<ID_{i},C_{i}>$, where $C_{i}=<U_{i},V_{i},W_{i}>$. Now simulator $B$ outputs
as follows:

    * –

To obtain $D_{i}\in\mathbb{G}_{1}$ such that $H_{1}(ID_{i})=D_{i}$, $B$
executes the above $H_{1}$ queries. Assume tuple $<ID_{i},D_{i},b_{i},f_{i}>$
be one entry in the $H_{1}^{List}$.

    * –

To obtaining the $D_{i}\in\mathbb{G}_{1}$ such that $S_{i}=s_{0}D_{i}$,
execute the above partial private key extraction queries. Assume tuple
$<ID_{i},D_{i},b_{i},f_{i}>$ be one entry in the $H_{1}^{List}$.

    * –

If $f_{i}=0$, $B$ runs the private key extraction queries to produce the
private key against $ID_{i}$.

    * –

If $f_{i}=1$, then $D_{i}=b_{i}Q_{ID}$. Recall that $U_{i}\in\mathbb{G}_{1}$.
$B$ sets $C^{\prime}_{i}=<b_{i}U_{i},V_{i},W_{i}>$. Let $S_{i}=s_{0}D_{i}$ be
the FullESKI-IBE partial private key and private keys as
$S_{IDi}=s_{0}s_{1}..s_{n}D_{i}$ against the $ID_{i}$. The BasicPubhy
decryption of $C^{\prime}_{i}$ using $S_{ID}$ is equivalent to the decryption
of $C_{i}$ using $S_{IDi}$ in FullESKI-IBE. Thus, we examine this observation
as

$e(b_{i}U_{i},S_{ID})=e(b_{i}U_{i},s_{0}s_{1}..s_{n}Q_{ID})=e(U_{i},b_{i}s_{0}s_{1}..s_{n}Q_{ID})=e(U_{i},s_{0}s_{1}..s_{n}D_{i})=e(U_{i},S_{i}k)$

Then, gives the decryption query to $Ch$ and $Ch$ response back to $Adv_{k}$.

Challenger phase: Now, $Adv_{k}$ gives the two equal size message
$M_{0},M_{1}\in\\{0,1\\}$ and challenge identity $ID_{ch}\neq ID$. Then, $Ch$
computes Ciphertext $C=Enc(M_{c},ID_{ch},pp)$ on some chosen random bit
$c\in\\{0,1\\}$. $B$ does as follows:

  * •

Suppose any message $M_{0},M_{1}\in\\{0,1\\}$ be challenged to the $Ch$ which
it respond with a ciphertext $C=<U,V,W>$ where $C$ is the encrypted form of
$M_{c}$ on bit $cin\\{0,1\\}$.

  * •

$B$ then runs the $H_{1}$ query to get $D\in\mathbb{G}_{1}$ such that
$H_{1}(ID_{ch})=D$ on tuple $<ID_{ch},D,b,f>$. $B$ aborts if $f=0$ and attack
become failed.

  * •

For $f=1$, $D=bQ_{ID}$ and we know $C=<U,V,W>$. For $b^{-1}$ is multiplicative
inverse of $b$, $B$ set $C^{\prime}=<b^{-1}U,V,W>$ and respond to $Adv_{k}$
with challenged $C^{\prime}$.

Phase 2: Similar to phase 1, $Adv_{k}$ adaptively issue more query where no
private key extraction is allowed on $ID_{c}h$.

Guess: At the end, $Adv_{k}$ gives the guess $c^{\prime}\in\\{0,1\\}$. The
game is in favour of the adversary if $c=c^{\prime}$. If $B$ does not abort,
then $Adv_{k}(A)=\left|Pr[c^{\prime}=c]-\frac{1}{2}\right|\geq\epsilon$. The
proof is given in [1].

The algorithm could abort for 3 reasons (Events):

  * •

$E_{1}$: During phase 1 or phase 2, an invalid partial private key and private
key extraction queries run by $Adv$.

  * •

$E_{2}$: On invalid challenge identity $ID^{ch}$ challenged by $Adv_{k}$.

  * •

$E_{3}$: During phase 2, an invalid decryption query is run by adversary
$Adv_{k}$.

For $nq_{p}$ private key queries in each $q_{pp}$ partial private key queries
and $q_{d}$ decryption queries, we have a total $nq_{pp}q_{p}$ queries. We
know the probability that B does not abort the game is:

$Pr[\neg E_{1}\wedge\neg E_{2}\wedge\neg E_{3}]\geq
a^{nq_{pp}q_{p}+q_{d}}(1-\alpha)$

This value is maximized at
$\alpha=\left(1-\frac{1}{(1+q_{pp}q_{p}^{n})}\right)$, which means
$Pr[\text{not\\_abort}]\geq\frac{1}{e(1+q_{pp}q_{p}^{n}+q_{d})}$, where $e$ is
the natural logarithm. Therefore, B’s advantage against $BasicPub^{hy}$ is
$\text{Advantage}(B)\geq\frac{1}{e(1+q_{pp}q_{p}^{n}+q_{d})}$.

Reduction 2. We obtain PKE system BasicPubhy from BasicPub system using FO-
transformation.

From theorem 4.5 of BF-IBE [13], Let IND-CCA $Adv_{k}$ have advantage
$\epsilon(k)$ while attacking BasicPubhy. Suppose $Adv_{k}$ has at most
$q_{d}$ decryption queries and makes at most $q_{3}$ and $q_{4}$ queries to
the hash functions $H_{3}$ and $H_{4}$ respectively. Then there is an IND-CPA
simulator B against BasicPub with advantage $\epsilon_{1}$, where

$\epsilon_{1}\geq\bigg{(}\frac{1}{(q_{3}+q_{4})}\bigg{)}\bigg{(}(\epsilon(k)+1)(1-\frac{2}{q})^{q_{d}}-1\bigg{)}$

Reduction 3. As an output of FO-transformation, there exists an adversary
$Adv_{k}$ against BasicPub, which can be used to construct a simulator B to
solve the BDH problem by IND-ID-CPA of [13].

From the above 3 reductions, we bound an IND-ID-CPA adversary $Adv_{k}$ on
BasicESKI-IBE with advantage $\epsilon(k)$ gives a BDH algorithm with
advantage $\epsilon^{\prime}$ as required, where,

$\epsilon^{\prime}\geq\bigg{(}\frac{1}{(q_{3}+q_{4})}\bigg{)}\bigg{(}\frac{\epsilon(k)}{(e(1+q_{pp}q_{p}^{n}+q_{d})q_{2})+1)}\bigg{)}\bigg{(}(1-\frac{2}{q})^{q_{d}}-1\bigg{)}$

∎

######  Theorem 3.3.

Our proposed ESKI-IBE scheme is secured against an impersonation attack.

###### Proof.

Proof. In the proposed keyIssuing algorithm, the user gives parameters
$<ID,X,D_{ID}>$ such that $D_{ID}=xH_{1}(ID)$ for secret information x, and
requests to the KGC for his partial private key. Suppose there is an adversary
$Adv$ with identity $ID_{A}$, who wishes to impersonate the user by modifying
the public parameters $<ID,X,D_{ID}>$ to $<ID_{A},D_{ID}^{*},X^{*}>$, where
$D_{ID}^{*}=x^{*}H_{1}(ID)$, and $X^{*}=x^{*}P$ such that
$x^{*}\in\mathbb{Z}_{q}$, and passes it to KGC. The KGC first the
authenticates the $ID_{A}$, then computes $Q_{IDA}=H_{1}(ID_{A})$ to validate
the received parameter $<ID_{A},D_{ID}^{*},X^{*}>$ using (3.4).

$e(Q_{IDA},X^{*})\overset{?}{=}e(D_{ID}^{*},P)$ (3.4)

The correctness of (3.4) is verified as:

$\displaystyle e(Q_{IDA},X^{*})$
$\displaystyle=e(Q_{IDA},x^{*}P)=e(x^{*}Q_{IDA},P)$
$\displaystyle=e(D_{IDA},P)\neq e(D_{ID}^{*},P)$

The above inequalities demonstrate that the KGC detects if any malicious
entity impersonates the user in the ESKI scheme. Therefore, our proposed
scheme avoids the impersonation attack. ∎

######  Theorem 3.4.

The proposed ESKI-IBE scheme is secured against insider attacks.

###### Proof.

Suppose a malicious CPC wishes to issue a signature on random parameters,
instead of the received parameters without disclosing any hint to other CPC.
Any malicious CPC and group of malicious CPC can control the user’s private
key. The proposed ESKI-IBE scheme is said to be secured against insider
attacks if the user detects any curious CPC generates the signature in its
choice parameter. In our proposed scheme, the user receives the parameter
$<X_{i-1},D_{i-1}>$ from the $CPC^{i-1}$, validates it and requests to
$CPC^{i}$ for partial private key share by sending $<ID,X_{i-1},D_{i-1}>$.
Suppose $CPC^{i}$ is an adversary who generates the signature on his choice
without giving any hint to other CPC. $CPC^{i}$ chooses random
$r\in\mathbb{Z}_{q}$, computes $D_{i}^{*}=rs_{1}H_{1}(ID)$, and
$X_{i}^{*}=rs_{1}P$, and sends $<D_{i}^{*},X_{i}^{*}>$ to user. The user
verifies the correctness of parameters using (3.6).

$e(D_{i-1},P_{i})?=e(D_{i}^{*},P)$ (3.5)

The correctness of (3.5) is verified as:

$\displaystyle e(D_{i-1},P_{i})$
$\displaystyle=e(D_{[}i-1],s_{i}P)=e(s_{i}D_{i-1},P)$
$\displaystyle=e(s_{i}s_{i-1}..s_{1}s_{0}xQ(ID),P)=e(D_{i},P)\neq
e(D_{i}^{*},P)$

The above inequalities show that the user detects if any curious CPC generates
a false signature in its choice. This proves that our proposed ESKI systems
are secure against insider attacks. ∎

######  Theorem 3.5.

The proposed ESKI scheme avoids the CPC’s incompetency.

###### Proof.

Incompetency refers to the inability of CPC to check the validity of the
received parameter without knowing any information about the received
parameters. The proposed ESKI-IBE scheme is said to be secured against the
incompetency attack if the CPC can check the validity of receiver parameters
and sign it without knowing any information about the received parameters.

In the key-securing phase of our proposed system, the user sends their
identity ID, signed blinding factor $X_{i-1}^{\prime}$, and blinded partial
private key $D_{i-1}$ to $CPC^{i}$ and sequentially requests them for key
protection. The $CPC^{i}$ validates the parameters $\langle
X_{i-1},D_{i-1}\rangle$ using (3.6).

$e(Q_{ID},X_{i-1})\overset{?}{=}e(D_{i-1},P)$ (3.6)

Suppose an adversary $Adv$ modified $<X_{i-1},D_{i-1}>$ as
$<D_{i-1}^{*}=rD_{i-1},X_{i-1}^{*}=rX_{i-1}>$ where $r$ is random variable.
$CPC^{i}$ checks these parameters using (3.8).

$e(Q_{ID},X_{i-1}^{*})\overset{?}{=}e(D_{i-1}^{*},P)$ (3.7)

On successful validation, $CPC^{i}$ set
$<D_{i}^{*}=s_{i}D_{i-1}^{*},X_{i}^{*}=s_{i}X_{i-1}^{*}>$ and outputs it to
the user who verifies the correctness of parameters $<D_{i}^{*},X_{i}^{*}>$
using Equation (3.9).

$e(D_{i-1},P_{i})\overset{?}{=}e(D_{i}^{*},P)$ (3.8)

The correctness of (3.8) is verified as:

$\displaystyle e(D_{i-1},P_{i})$
$\displaystyle=e(D_{i-1},s_{i}P)=e(s_{i}D_{i-1},P)$
$\displaystyle=e(s_{i}s_{i-1}..s_{1}s_{0}xQ(ID),P)=e(D_{i},P)\neq
e(D_{i}^{*},P)$

These inequalities show that the user can easily detect adversarial
misbehaviour during communication between the user and $CPC^{i}$. Therefore,
our proposed ESKI Systems are secure against CPC’s incompetency attack. ∎

####  3.4.2 Security Analysis of EF-IBS scheme

######  Theorem 3.6.

The proposed EF-IBS is consistent.

###### Proof.

The Equation (3.2) ensures the validity of the signature-message pair. Since
$R=rP$ and $S=r^{-1}(H_{2}(m),H_{3}(R)d_{ID})$ are given, the consistency of
Equation (3.2) is verified as follows. From LHS,

$\displaystyle e(S,R)$ $\displaystyle=e(r^{-1}(H_{2}(m)P+H_{3}(R)d_{ID}),rP)$
$\displaystyle=e((H_{2}(m)P+H_{3}(R)d_{ID}),P)$
$\displaystyle=e(H_{2}(m)P,P)e(H_{3}(R)d_{ID},P)$
$\displaystyle=e(H_{2}(m)P,P)e(H_{3}(R)s_{0}(s_{1}+s_{2}+...+s_{n})Q_{ID},P)$
$\displaystyle=e(H_{2}(m)P,P)e(H_{3}(R)Q_{ID},Y)$
$\displaystyle=e(P,P)^{H_{2}(m)}e(Q_{ID},Y)^{H_{3}(R))}$
$\displaystyle=g^{H_{2}(m)}e(Q_{ID},Y)^{H_{3}(R)}$

This completes the correctness of Equation (3.2). ∎

######  Theorem 3.7.

(EF-ID-CMA). Suppose $H_{1},H_{2}$ and $H_{3}$ are three random oracle models
and forger $F$ wants to forge a signature on message $m$. Suppose forger $F$
for an adaptive chosen message and identity attacks (EF-ID-CMA) to our EL-IBS
scheme with advantage $k^{-n}$ and running time $t$, there exists an algorithm
B that helps $F$. Thus, $F(t,q_{1},q_{2},q_{3},q_{p},q_{S},k^{-n})$ have the
following advantage to breaks the proposed scheme.

$|Pr[F(t,q_{1},q_{2},q_{3},q_{p},q_{S},k^{-n})]|\geq
k^{-n}(1-q_{1}/2^{k})^{q_{p}}(1-(q_{2}+q_{3})/2^{k})^{q_{s}}$ (3.9)

and, $Timet^{\prime}=t+t_{B}+q_{1}+q_{2}+q_{3}+q_{P}+q_{S}$

Where, $q_{1},q_{2},q_{3},q_{p}$ and $q_{S}$ are the most queries to
$H_{1},H_{2},H_{3}$ hash oracles, private key extraction and signature oracle
respectively asked by $F$ and $t_{B}$ is running time for algorithm $B$.

###### Proof.

Suppose a forger $F$ wants to forge any signature and let there must be a
simulator $B$, which helps $F$. We have to design an algorithm $B$ to solve
the CDHP.

Setup: Consider three hash functions
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*},H_{2}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}^{*}$
and $H_{3}:\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$, generator $P$ of
$\mathbb{G}_{1}$ and bilinear function
$e:\mathbb{G}_{1}\times\mathbb{G}_{1}\rightarrow\mathbb{G}_{2}$, $B$ chooses
an element $a\in\mathbb{Z}_{q}^{*}$, and set system public key as $Y=aP$ and
$g=e(P,P)$. $B$ now set parameter
$pp=<q,e,g,P,P_{0},\mathbb{G}_{1},\mathbb{G}_{2},H_{1},H_{2},H_{3},Y>$ and
gives $pp$ to $F$.

Oracles: Forger $F$ performs the following oracles.

  * •

$H_{1}$ oracle: $B$ makes a list $H_{1}^{List}$, which is initially empty
having tuple $<ID_{i},h_{1}i,b_{i},x_{i}>$. When $F$ queries on identity
$ID_{i}$, $B$ responds $F$ in the following way.

    * –

$B$ gives $h_{1}i$ to the $F$, if $ID_{i}$ found in the $H_{1}^{List}$ of
tuple $<ID_{i},h_{1}i,b_{i},x_{i}>$.

    * –

Otherwise, $B$ chooses a bit $x\in\\{0,1\\}$, where $Pr[x=0]=\alpha$. Pick an
element $b\in\mathbb{Z}_{q}^{*}$, set $H_{1}(ID)=h_{1}=bQ_{ID}$ for $x=1$,
else, set $H_{1}(ID)=h_{1}=bP$. Adds tuple $<ID_{i},h_{1i},b,x>$ to list
$H_{1}^{List}$, and gives $h_{1i}$ to $F$.

Note, $H_{1}(ID)$ gives no information to $F$ until they query the $H_{1}$
oracle on $ID$ because $H_{1}$ is the random oracle.

  * •

$H_{2}$ oracle. For given message $m$, $B$ chooses a random element
$h_{2}\in\mathbb{Z}_{q}^{*}$, set $H_{2}(m)=h_{2}$ and returns it to $F$.

  * •

$H_{3}$ oracle. For given message $R$, $B$ chooses a random element
$h_{3}\in\mathbb{Z}_{q}^{*}$, set $H_{3}(R)=h_{3}$ and returns it to the $F$.

  * •

Private key extraction oracle. $F$ submit an identity $ID$. $B$ maintains a
list $H_{1}^{List}$ having tuple $<ID_{i},d_{IDi},b_{i}>$. $B$ responds
private key $d_{ID}$ to F, if queried key contained in the list. Otherwise,
$B$ chooses a random element $b\in\mathbb{Z}_{q}^{*}$, set $d_{ID}=bY$, adds
$d_{ID}$ in the list and gives $d_{ID}$ to the $F$.

  * •

Signing oracle. For a given input $<ID,m>$, $B$ queries the private key from
the EF-IBS scheme if it does not have a private key $d_{ID}$ corresponding to
$ID$. $B$ runs the signing algorithm of EF-IBS to get the signature
$\sigma=<S,R>$. $B$ invokes a hash query such that $h_{1}=H_{1}(ID)$,
$h_{2}=H_{2}(m)$ and $h_{3}=H_{3}(R)$. It then computes
$\sigma^{\prime}=<S^{\prime},R^{\prime}>$, where $S^{\prime}=rS$ and returns
it to $F$.

Challenge: At the end, $F$ responds a tuple $<ID^{*},m^{*},S^{*},R^{*}>$
against identity $ID^{*}$. Since $F$ is allowed to win the EF-ID-CMA game with
a non-negligible advantage against the EF-IBS scheme as assumed, there is
$e(S^{*},R^{*})\overset{?}{=}g^{h_{2}}e(h_{1},Y)^{h_{3}}$, where
$h_{1}=H_{1}(ID^{*})$, $h_{2}=H_{2}(m^{*})$ and $h_{3}=H_{3}(R^{*})$.

To break the EF-IBS scheme, B submits the challenge tuple
$\sigma^{\prime}=<S^{\prime},R^{\prime}>$, where $S^{\prime}=rS^{*}$ and
$R^{\prime}=r^{-1}R^{*}$, $h_{2}=H_{2}(m)$ and
$h^{\prime}_{3}=H_{3}(R^{\prime})$. We can get

$\displaystyle
e(S^{\prime},R^{\prime})=e(rS^{*},r^{-1}R^{*})=e((h_{2}P+h^{\prime}_{3}abP),R^{*})$

Analysis. The probability that B does not abort the game is defined by four
events.

  * •

$E_{1}$: The extract oracles fail if $H_{1}$ oracle outputs the inconsistent
outputs with probability at most $(q_{1}/2)^{k}$. The simulation is complete
$q_{p}$ time, which happens with probability at least
$(1-q_{1}/2^{k})^{q_{p}}$.

  * •

$E_{2}$: The signature oracles fail if $H_{2}$ and $H_{3}$ oracles output the
inconsistent outputs with probability at most $(q_{2}+q_{3})/2^{k}$. The
simulation is complete $q_{s}$ time, which happens with probability at least
$(1-(q_{2}+q_{3})/2^{k})^{q_{s}}$.

  * •

$E_{3}$: When $F$ runs the sign oracle, $B$ does not stop.

  * •

$E_{4}$: The forger $B$ computes the valid message-signature forgery.

From the above four events, we obtain the probability that $F$ can break the
scheme is

$\displaystyle Pr[\neg E_{1}\land\neg E_{2}\land E_{4}|E_{3}]\geq
k^{-n}\left(1-\frac{q_{1}}{2^{k}}\right)^{q_{p}}\left(1-\frac{q_{2}+q_{3}}{2^{k}}\right)^{q_{s}}$

∎

######  Theorem 3.8.

(EKA-ID-CMA). Suppose $H_{1},H_{2}$ and $H_{3}$ are three random oracle models
and adversary A wishes to defame the KGC that his private key is used by the
KGC and let an algorithm $B$, which helps $A$. Suppose $A$ executes private
key extract oracles, signature oracles, $H_{1}$ hash oracles, $H_{2}$ hash
oracles, and runs at most $t$ times with advantage at most $k^{-n}$. Under the
assumption of ROM and intractable to solve the CDH problem, our proposed EF-
IBS Scheme is resilient to existential key abuse against the adaptive chosen
message and identity attacks (EUS-ID-CMA).

###### Proof.

Suppose a forger $F$ wants to abuse a user by forging a signature and let
there must be a simulator B, which helps $F$. We have to design an algorithm
$B$ to solve the CDH problem.

Setup: $B$ considers $P$ as a generator of group $\mathbb{G}_{1}$, three hash
functions
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$,
$H_{2}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}^{*}$ and
$H_{3}:\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$, a bilinear map function
$e:\mathbb{G}_{1}\times\mathbb{G}_{1}\rightarrow\mathbb{G}_{2}$. $B$ chooses
$a\in\mathbb{Z}_{q}^{*}$, and compute $Y=aP$, and public parameter
$pp=<q,e,g,P,P_{0},\mathbb{G}_{1},\mathbb{G}_{2},H_{1},H_{2},H_{3},Y>$. $B$
outputs $pp$ to $F$.

Oracles: Forger $F$ asks the queries, where $B$ responds the following
oracles.

  * •

$H_{1}$ oracle: $B$ prepares a list $H_{1}^{List}$ having tuple
$<ID_{i},h_{1}i,b_{i},x_{i}>$, which is initially empty. $F$ queries on
Identity $ID$, $B$ responds $F$ in the following way.

    * –

$B$ gives $h_{1i}$ to $F$, if $ID$ found in the $H_{1}^{List}$ of tuple
$<ID_{i},h_{1}i,b_{i},x_{i}>$.

    * –

Otherwise, $B$ chooses a bit $x\in\\{0,1\\}$, where $Pr[x=0]=\alpha$. Pick a
random element $b\in\mathbb{Z}_{q}^{*}$, set $H_{1}(ID)=h_{1}=bQ_{ID}$ for
$x=1$, else, set $H_{1}(ID)=h_{1}=bP$. Add the tuple $<ID_{i},h_{1i},b,x>$ to
the list $H_{1}^{List}$, and give $h_{1i}$ to $F$.

Note, $H_{1}(ID)$ gives no information to $F$ until they query the $H_{1}$
oracle on $ID$ because $H_{1}$ is the random oracle.

  * •

$H_{2}$ oracle. For given message $m$, $B$ chooses a random element
$h_{2}\in\mathbb{Z}_{q}^{*}$, set $H_{2}(m)=h_{2}$ and returns to the $F$.

  * •

$H_{3}$ oracle. For a given message $R$, $B$ chooses a random element
$r\in\mathbb{Z}_{q}^{*}$, set $h_{3}=H_{3}(R)=rP$ and returns to $F$.

  * •

Private key extraction oracles. $F$ submit an identity $ID$. $B$ maintains a
list $H_{1}^{List}$ having tuple $<ID_{i},d_{IDi},b_{i}>$. $B$ responds
private key $d_{ID}$ to $F$, if queried key contained in the list. Otherwise,
$B$ chooses a random element $b\in\mathbb{Z}_{q}^{*}$, set $d_{ID}=bY$, adds
$d_{ID}$ in the list and gives $d_{ID}$ to the $F$.

  * •

Signing oracle. For signing oracle on $<ID,m>$, if B does not have private key
$d_{ID}$ corresponding to $ID$, it computes the private key by running the
private key extraction oracle. Using private key $d_{ID}$ and $H_{2}$ and
$H_{3}$ responds, $B$ outputs the signing query as follows:

    * –

If $ID$ is queried previously, $B$ abort the simulation.

    * –

Otherwise, $B$ execute the private key oracle using $ID_{i}$ corresponding to
$H_{1}^{List}$ and corresponding private key $d_{ID}$, queries the $H_{2}$
oracle to get $h_{2}$, queries the $H_{3}$ oracle to get $h_{3}$, computes the
signature $R=rP,S=r^{-1}(h_{2}iP+h_{3}id_{ID})$. $B$ sends $<S,R>$ to $A$.

Challenge: At the end, $A$ responds to the challenge
$<ID^{*},m^{*},S^{*},R^{*}>$ against identity $ID^{*}$ such that the private
key against $ID^{*}$ that has been queried in private key extraction oracle
previously and there must be a signing oracle that outputs $<ID^{*},m,S,R>$.
It seems that $B$ does not abort the game with probability
$(1-1/q_{1})(1-1/(q_{1}(q_{2}+q_{3})))$. Also, the probability that $m^{*}=m$
is $1/(q_{1}(q_{2}+q_{3}))$. So, there is

$\displaystyle e(S^{*},R^{*})$ $\displaystyle=g^{(}h_{2})e(bP,aP)^{(}h_{3})$
$\displaystyle=e(P,P)^{(}h_{2})e(bP,aP)^{(}h_{3})$
$\displaystyle=e(P,P)^{(}h_{2})e(bP,aP)^{(}h_{3})$
$\displaystyle=e(h_{2}P,P)e(h_{3}abP,P)$ $\displaystyle=e(h_{2}P+h_{3}abP,P)$

Thus, $B$ obtains $r^{*}S^{*}=h_{2}P+h_{3}abP$, i.e.,
$abP=h_{3}^{-1}(r^{*}S^{*}-h_{2}P)$. Therefore, $B$ can break the CDH problem.

∎

######  Theorem 3.9.

(EUS-ID-CMA). Suppose $H_{1}$, $H_{2}$ and $H_{3}$ are three random oracle
models and adversary $A$ who wish to defame the KGC that his private key is
used by the KGC and let an algorithm $B$, which helps $A$. Suppose A executes
at most $q_{p}$ private key extract oracles, $q_{s}$ signature oracles,
$q_{1}$ $H_{1}$ hash oracles, $q_{2}$ $H_{2}$ hash oracles, runs at most $t$
times with advantage at most $k^{-n}$. Under the assumption of ROM and
intractable to solve the CDH problem, our proposed EF-IBS Scheme is
existential user slandering secured against the adaptive chosen message and
identity attacks (EUS-ID-CMA).

###### Proof.

Suppose a malicious user $A$ who wishes to defame the KGC that his private key
is used by him and lets an algorithm $B$, which helps $A$. We have to design
an algorithm $B$ to solve the CDHP. Setup: Consider three hash functions
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$,
$H_{2}:{0,1}^{*}\rightarrow\mathbb{Z}_{q}^{*}$, and
$H_{3}:\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}^{*}$, generator $P$ of
$\mathbb{G}_{1}$, and bilinear function
$e:\mathbb{G}_{1}\times\mathbb{G}_{1}\rightarrow\mathbb{G}_{2}$. $B$ chooses
an element $a\in\mathbb{Z}_{q}^{*}$ and sets the system public key as $Y=aP$
and $g=e(P,P)$. $B$ now sets the parameter $pp=\langle
q,e,g,P,P_{0},\mathbb{G}_{1},\mathbb{G}_{2},H_{1},H_{2},H_{3},Y\rangle$ and
gives $pp$ to $F$.

Oracles: Forger $F$ performs the following oracles.

  * •

$H_{1}$ oracle: $B$ makes a list $H_{1}^{List}$, which is initially empty
having tuple $<ID_{i},h_{1}i,b_{i},x_{i}>$. When $F$ queries on identity
$ID_{i}$, $B$ responds $F$ in the following way.

    * –

$B$ gives $h_{1i}$ to the $F$, if $ID_{i}$ found in the $H_{1}^{List}$ of
tuple $<ID_{i},h_{1}i,b_{i},x_{i}>$.

    * –

Otherwise, $B$ chooses a bit $x\in\\{0,1\\}$, where $Pr[x=0]=\alpha$. Pick an
element $b\in\mathbb{Z}_{q}^{*}$, set $H_{1}(ID)=h_{1}=bQ_{ID}$ for $x=1$,
else, set $H_{1}(ID)=h_{1}=bP$. Add the tuple $<ID_{i},h_{1i},b,x>$ to the
list $H_{1}^{List}$, and give $h_{1i}$ to $F$.

Note, $H_{1}(ID)$ gives no information to $F$ until they query the $H_{1}$
oracle on $ID$ because $H_{1}$ is the random oracle.

  * •

$H_{2}$ oracle. For given message $m_{i}$, $B$ chooses a random element
$h_{2}\in\mathbb{Z}_{q}^{*}$, set $H_{2}(m)=h_{2}$ and returns it to the $F$.

  * •

$H_{3}$ oracle. For given message $R$, $B$ chooses a random element
$h_{3}\in\mathbb{Z}_{q}^{*}$, set $H_{3}(R)=h_{3}$ and returns it to the $F$.

  * •

Private key extraction oracle. After successful execution of $H_{1}$ oracle,
$B$ obtains $h_{1i}$ against $ID_{i}$. Using tuple
$<ID_{i},h_{1}i,b_{i},x_{i}>$ in $H_{1}^{List}$, $B$ performs the following
steps.

    * –

If $x_{i}=1$, abort the game.

    * –

Otherwise, choose a random element $b\in\mathbb{Z}_{q}^{*}$, set $d_{ID}=bY$
and gives $d_{ID}$ to the $F$.

  * •

Signing oracle. For a given input, $<ID,m>$, $B$ executes the signature oracle
to generate the signature $<S,R>$ using the output of the $h_{2}$ and $h_{3}$
oracles as follows.

    * –

If $ID$ is queried previously, $B$ abort the simulation.

    * –

Otherwise, $B$ execute the private key oracle using $ID$ corresponding to
$H_{1}^{List}$ and corresponding private key $bY$ and picks
$r\in\mathbb{Z}_{q}^{*}$ and set the signature $<S,R>$, where $R=rP$ and
$S=r^{-1}(h_{2}P+h_{3}abP)$

Challenge: At the end, $A$ responds to the challenge
$<ID^{*},m^{*},S^{*},R^{*}>$ against identity $ID^{*}$ where, the private key
against $ID^{*}$ that has been queried in private key extraction oracle
previously. So, $B$ generates the private key $d_{i}$. It has been observed
that A can break our EF-IBS against the EUS-ID-CMA if $d_{i}=d_{ID}$.

From the forking lemma in [13], B can replay the same tuple but with a
distinct $H_{2}$ choice. It then produces two valid signature $<S^{*},R^{*}>$
and $<S^{{}^{\prime}*},R^{{}^{\prime}*}>$ on message $m^{*}$ corresponding to
hash function $H_{2}$ and $H^{\prime}_{2}$ having distinct values $h_{2}\neq
h^{\prime}_{2}$ respectively. Since, $R^{*}=r^{*}P$,
$S^{*}=r^{*-1}(H_{2}(m^{*})P+H_{3}(R^{*})abP)$ and
$R^{{}^{\prime}*}=r^{{}^{\prime}*}P,S^{{}^{\prime}*}=(r^{{}^{\prime}*-1})(H^{\prime}_{2}(m^{*})P+H_{3}(R^{{}^{\prime}*})abP)$.

$\displaystyle\frac{e(S^{*},R^{*})}{e(S^{\prime*},R^{\prime*})}$
$\displaystyle=\frac{g^{h_{2}}e(bP,aP)^{h_{3}}}{g^{h^{\prime}_{2}}e(bP,aP)^{h^{\prime}_{3}}}=g^{h_{2}-h^{\prime}_{2}}e(bP,aP)^{h_{3}-h^{\prime}_{3}}$
$\displaystyle=g^{h_{2}-h^{\prime}_{2}}e(bP,aP)^{h_{3}-h^{\prime}_{3}}=e(P,P)^{h_{2}-h^{\prime}_{2}}e(bP,aP)^{h_{3}-h^{\prime}_{3}}$
$\displaystyle=e(((h_{2}-h^{\prime}_{2})+(h_{3}-h^{\prime}_{3})ab)P,P)$
$\displaystyle=e(r^{*}S^{*}(r^{{}^{\prime}*}S^{{}^{\prime}*})^{-1},P)$

$\displaystyle r^{*}S^{*}(r^{\prime*}S^{\prime*})^{-1}$
$\displaystyle=((h_{2}-h^{\prime}_{2})+(h_{3}-h^{\prime}_{3})ab)P$
$\displaystyle(h_{3}-h^{\prime}_{3})abP$
$\displaystyle=r^{*}S^{*}(r^{{}^{\prime}*}S^{{}^{\prime}*})^{-1}-(h_{2}-h^{\prime}_{2})P$
$\displaystyle abP$
$\displaystyle=(h_{3}-h^{\prime}_{3})^{-1}(r^{*}S^{*}(r^{{}^{\prime}*}S^{{}^{\prime}*})^{-1}-(h_{2}-h^{\prime}_{2}))P$

Therefore B can solve the CDH problem. ∎

###  3.5 Performance Analysis

This section analyzes the performance of the proposed ESKI-IBE and EF-IBS
schemes, in terms of computation overhead (in msec), communication overhead
(in Bytes) and storage cost (in Bytes).

####  3.5.1 Experiment Simulation

In order to validate the proposed schemes, we simulate the experiments on the
Intel(R) Core(TM) i7-2600K CPU @ 3.4 GHz, and 8 GB of RAM, using gcc 4.6. We
consider the Tate pairing constructs over the Type-A curve of the PBC library
[122] in order to achieve the 1024-bit RSA level of security. The Type-A
super-singular elliptic curve $E/\mathbb{F}_{P}:y^{2}=x^{3}+x$ built on two
prime $p$ and $q$, such that $|p|=512-bit$, $q=2^{159}+2^{17}+1$ is Solaris
prime ($|q|=160-bit$) satisfying $p+1=12qr$, where
$\mathbb{G}_{1}=\mathbb{G}_{2}$, with embedding degree is 2. We take the
following cryptographic operations for analysis of the computational cost of
the proposed EF-IBS system: bilinear pairing operations, scalar multiplication
in ECC, addition in ECC, modular multiplication, modular inversion,
exponentiation and map-to-point hash function. Table 3.1 shows the computation
cost of required cryptographic operations used in the entire thesis. We follow
the methodologies given in [18, 37, 9, 34] in order to compute the computation
cost of required cryptographic operations.

Operations | Notations | Cost (in $T_{M}$) | Cost (in ms)
---|---|---|---
Modular multiplication | $T_{M}$ | 01.00 $T_{M}$ | $\approx 0.23$
Modular inversion | $T_{I}$ | 11.60 $T_{M}$ |  $\approx(11.60*0.23)$ $\approx 2.67$
Points addition | $T_{A}$ | 00.12 $T_{M}$ |  $\approx(0.12*0.23)$ $\approx 0.03$
Scalar point multiplication | $T_{SM}$ | 29.00 $T_{M}$ |  $\approx(29*0.23)$ $\approx 6.67$
Modular Exponentiation | $T_{E}$ | 240.00 $T_{M}$ |  $\approx(240*0.23)$ $\approx 55.2$
Map-To-Point hash operation | $T_{H}$ | 29.00 $T_{M}$ | $\approx 6.67$
Bilinear pairing | $T_{P}$ | 87.00 $T_{M}$ | $\approx 20.01$
Table 3.1: Computational cost of required cryptographic operations (in ms)

####  3.5.2 Performance Evaluation of ESKI

Computation cost. Now, we compare the computation cost of setup and key
generation phases of our proposed ESKI model with the corresponding phases of
other Escrow-free Schemes in the literature [83, 84, 27, 26, 28, 29, 115, 185,
184]. Using notations and computation cost of operations given in Table 3.1,
we summarize the computation cost of KGC-Setup, CPC-Setup, Key issuing, Key
securing and Key extraction phase of our ESKI model for $n=0,1,10$ and $100$
number of CPCs, given in Table 3.2. In Figure 3.1, it can be seen that the
computation cost of CPC-Setup and key issuing phase increases linearly, that
is $2n(T_{P}+T_{S})=(51.36*n)ms$ as the value of $n$ grows. On the other side,
the computation cost of the Setup, Key issuing, and key retrieving phases are
$13.34ms,106.72ms$, and $46.7ms$, respectively, and remain constant for any
number of CPCs. It is noted that our scheme acts as a general IBE scheme which
takes 166.8 ms in setup and key generation for $n=0$.

####  3.5.3 Performance Evaluation of ESKI-IBE scheme

This section estimates the performance of our proposed ESKI-IBE scheme, in
terms of computation cost and communication cost. For comparison of our scheme
with other related schemes, we assume that HIBE/HIBS scheme in the related
schemes is 1 level, which is equivalent to a pure IBE/IBS scheme. As our
proposed ESKI scheme employs multiple authorities, we compare our scheme with
Chen et al. [27], Chen et al. [26] and Li et al. scheme [115].

Table 3.2: Computation time (in ms) of KGC-Setup, CPC-Setup, Key-Issuing, Key-Securing and Key-Extraction phase of our ESKI scheme for n = {0, 1, 10 and 100}, the number of CPC participated in the system. Phases | #operations | Computation cost (in ms)
---|---|---
|  | n=0 | n=1 | n=10 | n=100
KGC-Setup | $1T_{SM}+1T_{H}$ | 13.34 | 13.34 | 13.34 | 13.34
CPC-Setup | $2n(T_{P}+T_{SM})$ | 0 | 53.36 | 533.6 | 5,336
Key Issuing | $4(T_{P}+T_{SM})$ | 106.72 | 106.72 | 106.72 | 106.72
Key Securing | $2n(T_{P}+T_{SM})$ | 0 | 53.36 | 533.6 | 5,336
Key Extracting | $2T_{P}+1T_{SM}$ | 46.7 | 46.7 | 46.7 | 46.7
Total | $(4n+6)(T_{P}+T_{SM})+1T_{H}$ | 166.8 | 273.5 | 1,234 | 10,838

Computation cost. Table 3.3 summarizes the computation cost of Chen et al.
[27], Chen et al. [26] and Li et al. scheme [115], our scheme-I and our
scheme-II. It can be observed from Figure 3.2 that our scheme (when we do not
consider the CPC cost) takes constant time (46.69 ms) while the overhead of
other scheme increase linearly. Similarly, Figure 3.3 shows the comparison of
our scheme (when we considered CPC cost) with others where it can be seen that
our scheme performed better as compared to Chen et al. [27] and Chen et al.
[26].

Figure 3.1: Computation overhead (in ms) of the different algorithms of proposed ESKI-IBE scheme. Figure 3.2: Setup and Key generation comparison of proposed ESKI-IBE scheme with others in terms of computation Cost (Without outsource Computing) Table 3.3: Computation comparison of our proposed scheme with related schemes. Scheme | Set up (A) | Key Extraction (B) | Total Cost (A+B)
---|---|---|---
Chen et al. [27] | $(n+1)T_{P}$ | $(3+n)T_{SM}+(2+n)T_{A}$ | 26.71n+40.1
Chen et al. [26] | $(n+1)T_{P}$ | $(4n+7)(T_{SM}+T_{A})$ | 58.7n+66.9
Feng Li. [115] | $(2n+1)T_{SM}+nT_{A}+1T_{H}$ | $(2+n)T_{SM}+nT_{A}+1T_{P}$ | $20.1n+46.7$
Our W/o CPC | $1T_{SM}+1T_{H}$ | $5T_{SM}$ | 46.49
Our CPC | $(2n+1)T_{SM}+1T_{H}$ | $(2n+5)T_{SM}$ | 26.68n+46.49
Figure 3.3: Setup and Key generation comparison of proposed ESKI-IBE scheme
with others in terms of computation Cost (With outsource Computing) Figure
3.4: Communication Cost (in Bytes) of proposed ESKI-IBE proposed scheme

Communication cost. In order to compare the communication cost of our proposed
scheme with other schemes, we consider the size of
$|\mathbb{G}_{1}|=|\mathbb{G}_{3}|$ = 512-bit (64 Bytes), $|\mathbb{Z}_{q}|$ =
160-bit (20 Bytes), and $|ID|$ = 80-bit (10 Bytes), where $\mathbb{G}_{3}$ is
a group used in Chen et al. [27] and Chen et al. [26]. Table 3.4 summarizes
the comparison of the communication cost of our proposed scheme with other
Escrow-free Schemes in the literature [[83, 84, 27, 26, 28, 29, 115, 185, 184,
144]. It can be observed from Figure 3.4 that the proposed ESKI model have the
private key and public key size of 64 Bytes and 10 Bytes respectively.

Table 3.4: Bandwidth and security comparison of our proposed scheme with
related schemes

Schemes | Public key size | Private key size | Crypt. Tool | Assumption
---|---|---|---|---
Karati et al. [83] | 168 Bytes | 202 Bytes | ECC | ECDLP
Karati et al. [84] | 104 Bytes | 74 Bytes | Bilinear Pairing | EBSDH@, BSDH#
Chen et al. [27] | 128 Bytes | 10 Bytes | COBG | DSE&
Chen et al. [26] | 128 Bytes | 10 Bytes | COBG${}^{\&}\&$ | DSE
Chen et al. [28] | 128 Bytes | 74 Bytes | COBG | DSE
Chen et al. [29] | 148 Bytes | 74 Bytes | Bilinear Pairing | CDH##
Feng Qi. [115] | 64 Bytes | 10 Bytes | Bilinear pairing | BDH@@
Zhang et al. [185] | 84 Bytes | 74 Bytes | Bilinear pairing | CDH
Zhang et al. [184] | 128 Bytes | 74 Bytes | Bilinear pairing | BDH
Sahana et al. [144] | 64 Bytes | 74 Bytes | Bilinear pairing | CDH
Our scheme | 64 Bytes | 10 Bytes | Bilinear pairing | BDH

@Extended Bilinear Strong Diffie-Hellman, #Bilinear Strong Diffie-Hellman, ##
computational Diffie-Hellman problem, @@ Bilinear Diffie-Hellman problem,
&Dual system encryption, ${}^{\&}\&$Composite Order Bilinear Groups

Table 3.5: General comparison of our proposed scheme with related schemes.

Scheme | RKEP @ | RSKIP # | RUSP ∗ | FID @@
---|---|---|---|---
Karati et al. [83] | $\checkmark$ | $\checkmark$ | $\times$ | $\times$
Karati et al. [84] | $\checkmark$ | $\checkmark$ | $\times$ | $\times$
Chen et al. [27] | $\checkmark$ | $\times$ | $\times$ | $\checkmark$
Chen et al. [26] | $\checkmark$ | $\checkmark$ | $\times$ | $\checkmark$
Chen et al. [28] | $\checkmark$ | $\times$ | $\checkmark$ | $\times$
Chen et al. [29] | $\checkmark$ | $\times$ | $\checkmark$ | $\times$
Feng Qi. [115] | $\checkmark$ | $\times$ | $\times$ | $\checkmark$
Zhang et al. [185] | $\checkmark$ | $\checkmark$ | $\times$ | $\times$
Zhang et al. [184] | $\checkmark$ | $\times$ | $\times$ | $\times$
Sahana et al. [144] | $\checkmark$ | $\times$ | $\times$ | $\times$
Our scheme | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$

@ Resilient to Key escrow problem, # Resilient to secure key issuing problem,
∗ Resilient to user slandering problem, @@ Achieve full identity based
advantage

General comparison. Table 3.5 summarizes the general comparison of our scheme
with related schemes in which we observed that our proposed ESKI scheme is
resilient to key escrow problem (RKEP), resilient to secure key issuing
problem (RSKI), resilient to user slandering problem (RUSP) and achieve full
identity-based feature (FID).

####  3.5.4 Performance Analysis of EF-IBS Scheme

This section estimates the performance of our proposed EF-IBS scheme, in terms
of computation cost and communication cost.

Table 3.6: Computation cost (in ms) comparison of proposed IBS with related schemes. Schemes | Signing | Verification | Total
---|---|---|---
[84] | $2T_{SM}+1T_{A}+1T_{E}$ | $1T_{p}+3T_{E}$ | $1T_{p}+2T_{SM}+1T_{A}+4T_{E}$
[28] | $5T_{SM}+2T_{A}$ | $5T_{p}+2T_{SM}+1T_{A}$ | $5T_{p}+7T_{SM}+3T_{A}$
[25] | $4T_{SM}+1T_{A}$ | $4T_{p}+2T_{SM}$ | $4T_{p}+6T_{SM}+1T_{A}$
[144] | $2T_{SM}+1T_{A}$ | $2T_{p}+1T_{SM}+1T_{A}$ | $2T_{p}+3T_{SM}+2T_{A}$
[152] | $4T_{SM}+2T_{A}+1T_{E}$ | $4T_{p}+4T_{SM}+1T_{E}$ | $4T_{p}+8T_{S}M+2T_{A}+2T_{E}$
[159] | $2T_{S}M+7T_{E}$ | $7T_{p}+4T_{SM}+1T_{E}$ | $7T_{p}+6T_{SM}+8T_{E}$
[175] | $3T_{SM}+3T_{E}$ | $3T_{p}+2T_{SM}$ | $3T_{p}+7T_{SM}+3T_{E}$
Our | $3T_{SM}+1T_{A}$ | $2T_{p}+1T_{E}$ | $2T_{p}+3T_{SM}+1T_{E}+1T_{A}$
Table 3.7: Communication cost and security comparison of proposed IBS with
related schemes

Schemes | Private | Public | Signature | Cryptographic | Crypt. | Security
---|---|---|---|---|---|---
| key size | key size | size | Primitive | Tool | Assump.
[84] | $1|\mathbb{G}_{1}|+2|\mathbb{Z}_{q}|$ | $1|\mathbb{G}_{1}|+1|ID|$ | $3|\mathbb{G}_{1}|$ | CLS | BP ## | EBSDHa,
|  |  |  |  |  | BSDHb
[28] | $3|\mathbb{G}_{1}|$ | $1|\mathbb{G}_{1}|+1|ID|$ | $4|\mathbb{G}_{1}|$ | HIBS | COBG@@ | DSE ∗∗
[25] | $2|\mathbb{G}_{1}|+1|\mathbb{Z}_{q}|$ | $1|\mathbb{G}_{1}|+1|ID|$ | $3|\mathbb{G}_{1}|$ | HIBS | BP | CDH @
[144] | $2|\mathbb{G}_{1}|$ | $1|\mathbb{G}_{1}|+1|ID|$ | $2|\mathbb{G}_{1}|$ | Partial IBS | BP | CDH
[152] | $2(|\mathbb{G}_{1}|+|\mathbb{Z}_{q}|)$ | $2|\mathbb{G}_{1}|+1|ID|$ | $3|\mathbb{G}_{1}|$ | CLS | BP | CDH
[159] | $2|\mathbb{G}_{1}|$ | $2|\mathbb{G}_{1}|+1|ID|$ | $5|\mathbb{G}_{1}|$ | CLS | BP | GCDH #
[175] | $2|\mathbb{G}_{1}|$ | $1|\mathbb{G}_{1}|+1|ID|$ | $3|\mathbb{G}_{1}|$ | CLS | BP | CDH
Our | $1|\mathbb{G}_{1}|$ | $1|ID|$ | $2|\mathbb{G}_{1}|$ | IBS | BP | BDH ∗

a Extended Bilinear Strong Diffie-Hellman, b Bilinear Strong Diffie-Hellman, @
computational Diffie-Hellman problem, # generalized computational Diffie-
Hellman problem, ∗ Bilinear Diffie-Hellman problem, @@ Composite order
bilinear group, ## Bilinear Pairing and ∗∗ dual system encryption

Figure 3.5: Signing, verification and total computational cost (in ms)
comparison of proposed EF-IBS scheme with other schemes Figure 3.6: Private
key, public key and signature size comparison of proposed EF-IBS scheme with
related schemes

Computation cost. In Table 3.6, we compare the signing and verifying cost of
our proposed EF-IBS scheme with related schemes such as Karati et al. [84],
Chen et al. [28], Chen et al. [25], Sahana et al. [144], Shim et al. [152],
Tseng et al. [159] and Yang et al. [175] IBS schemes. For signing a message,
the proposed scheme takes $3T_{SM}+1T_{A}=20.04ms$, while Karati et al. [84],
Chen et al. [28], Chen et al. [25], Sahana et al. [144], Shim et al. [152],
Tseng et al. [159] and Yang et al. [175] IBS schemes take
$18.17ms,33.4ms,26.7ms,13.4ms,31.6ms,47.15ms$ and $23ms$ respectively. For
verifying a message-signature pair, the proposed scheme takes
$2T_{BP}+1T_{E}=44.85ms$, while Karati et al. [84], Chen et al. [28], Chen et
al. [25], Sahana et al. [144], Shim et al. [152], Tseng et al. [159] and Yang
et al. [175] IBS schemes take $34.5ms$, $113.4ms$, $93.4ms$, $46.7ms$,
$111.5ms$, $171.6ms$ and $79.4ms$ respectively. Thus, the proposed system
takes 64.85 ms for total computational cost, while Karati et al. [84], Chen et
al. [28], Chen et al. [25], Sahana et al. [144], Shim et al. [152], Tseng et
al. [159] and Yang et al. [175] IBS schemes take $54.67ms$, $146.8ms$,
$120.1ms$, $60.1ms$, $143.1ms$, $218.75ms$, and $102.4ms$ respectively. Figure
3.5 compares our proposed scheme with other related schemes.

Storage cost. Table 3.7 compares the communication cost and security
assumption of our scheme with Karati et al. [84], Chen et al. [28], Chen et
al. [25], Sahana et al. [144], Shim et al. [152], Tseng et al. [159] and Yang
et al. [175] IBS schemes. For communication cost evaluation, we assume
$|ID|=2bytes$. For the super-singular curve over the binary field
$\mathbb{F}_{2^{271}}$ with the order of $\mathbb{G}_{1}$ is 252-bit prime and
using compression technique [27], we consider $|\mathbb{G}_{1}|=34bytes$ and
$|\mathbb{Z}_{q}|=32bytes$. We assume that the HIBE/HIBS scheme in [84], [28],
[25] [7], [10], [11] are $1$-level HIBE/HIBS scheme, which is equivalent to
standard IBE/IBS scheme. The proposed scheme requires to transmit
$2|\mathbb{G}_{1}|$= 68 Bytes while Karati et al. [84], Chen et al. [28], Chen
et al. [25], Sahana et al. [144], Shim et al. [152], Tseng et al. [159] and
Yang et al. [175] IBS schemes take $102Bytes$, $136Bytes$, $102Bytes$,
$68Bytes$, $102Bytes$, $170Bytes$ and $102Bytes$ respectively. Also, the
proposed scheme has the least public key ($2Bytes$) and private key
($34Bytes$) size in comparison with the related schemes, shown in Figure
(3.6).

Batch Verification. Here, we discuss that the proposed EF-IBS scheme verifies
multiple message-signature pairs simultaneously in the least communication and
computation cost compared to the situation where multiple message-signature
pairs are verified one by one. On given message-signature pairs
$<m_{k},S_{k},R_{k}>$, sender’s $ID$, and $pp$, the recipient verifies the
signature-message pairs using (3.10).

$\prod_{k=0}^{n}e(S_{k},R_{k})\overset{?}{=}g^{\sum_{(}k=0)^{n}H_{3}(m_{k})}e(Q_{I}D,Y)^{sum_{(}k=0)^{n}H_{3}(R_{k})}$
(3.10)

The Equation (3.10) ensures the validity of multiple signature-message pairs.
The consistency of the above Equation (3.7) is verified as follows. From LHS,

$\displaystyle\prod_{k=0}^{n}e(S_{k},R_{k})$
$\displaystyle=\prod_{k=0}^{n}e(r_{k}^{-1}(H_{2}(m_{k})P+H_{3}(R_{k})d_{I}D),r_{k}P)$
$\displaystyle=\prod_{k=0}^{n}e((H_{2}(m_{k})P+H_{3}(R_{k})d_{ID}),P)$
$\displaystyle=\prod_{k=0}^{n}e(H_{2}(m_{k})P,P)\prod_{k=0}^{n}e(H_{3}(R_{k})Q_{ID},Y)$
$\displaystyle=\prod_{k=0}^{n}e(P,P)^{H_{2}(m_{k})}\prod_{k=0}^{n}e(Q_{ID},Y)^{(}H_{2}(R_{k}))$
$\displaystyle=\prod_{k=0}^{n}g^{H_{2}(m_{k})}\prod_{k=0}^{n}(Q_{ID},Y)^{H_{2}(R_{k})}$
$\displaystyle=g^{\sum_{k=0}^{n}H_{3}(m_{k})}e(Q_{ID},Y)^{\sum_{k=0}^{n}H_{3}(R_{k})}$

This completes the correctness of (3.10). For verifying k message-signature
pairs simultaneously, the batch verification needs $(k+1)T_{B}P+kT_{E}$ while
individual verification needs $2kT_{B}P+2kT_{E}$ of computation cost.

Comparison with secret-sharing based solution. In the secret-sharing solution
[13], the master key is distributed among multiple PKGs, and the user requests
each PKG for its private key share using the secret-sharing scheme. Each PKG
authenticates the user and computes the private key shares using their master
key shares and issues them to the user. The user then combines the shares and
extracts their private key. While in our scheme, the user’s private key is
derived from the KGC, further protected by multiple authorities under their
secret keys. In the proposed IBS, the KGC authenticates the user and issues a
partial private key to him, and multiple authorities protect the private key.
Furthermore, private key distribution among the entities is secured under the
user’s secret key. Therefore, our proposed IBS scheme is secured against the
malicious-but-passive PKG that overcomes the inefficiency due to multiple-user
authentication.

Comparison with CL-PKC and CB-PKC. In CL-PLC [3], the user derived his private
key, which consists of a partial private key derived from the trusted
certificate authority and the user’s secret key to sign a message. For
verifying the message-signature pair, the recipient needs the signer identity
ID and the public key corresponding to the signer’s secret key. Similarly, in
CB-PKC [60], the user’s private key involves the secret key of the certificate
authority and his secret key. Both these two cryptosystems were partially
built over the framework of IBC directly without introducing more
infrastructures. However, due to the introduction of the user’s secret key,
they do not adequately preserve the identity-based property. On comparing CL-
PKC [3] and CB-PKC [60], the user’s private key in our proposed approach is
derived from the KGC and simultaneously protected by the multiple CPCs.
Assuming at least one CPC is honest, our approach addresses the key escrow,
key abusing, and user slandering problem.

###  3.6 Summary

This section introduces a solution that can enhance trust in Private Key
Generators (PKG) within Identity-Based Cryptography (IBC). It presents a
secure and efficient key issuing scheme that addresses key escrow, secure key
issuing, and user slandering issues. The proposed scheme is then utilized to
implement an escrow-free Identity-Based Encryption (IBE) scheme that ensures
confidentiality, and an escrow-free Identity-Based Signature (IBS) scheme that
is secure against forgery. The proposed schemes are benchmarked against
existing solutions in computation and communication costs, and the results
demonstrate that the proposed schemes require the least computation and
communication cost, making them ideal for practical applications. This
approach provides an alternative to traditional IBC, which relies on a trusted
third party, the PKG. The use of an escrow-free key issuing scheme provides a
secure and efficient way to generate keys without relying on a trusted PKG.

[75mm] Difficulties in your life do not come to destroy you but to help you
realise your hidden potential and power. Let difficulties know that you too
are difficult. Avul Pacir Zainulabidin Abdul Kalam-Atomic Scientist and
President of India

##  Chapter 4 Identity-Based Blind Signature Scheme for End-to-End Verifiable
Internet-Voting System

The Electronic Voting System (EVS) [161] is undoubtedly more efficient,
participatory, and fair than the traditional postal voting system. However,
inconsistencies have been observed in the EVS system, including ballot
privacy, voter anonymity, transparency, and auditing. To address these
shortcomings, experts have utilized several cryptographic tools, such as
homomorphic cryptosystems [19, 30, 177], public key encryption [105], and
zero-knowledge proof [105]. An early secure EVS system using a mix-net
approach was developed by David Chaum [22]. Blind signature schemes [54, 130,
119], proxy servers [23], and secret sharing mechanisms [140] have also been
used to implement the EVS system. In this chapter, we introduce two secure
Identity-Based Blind Signature (IDBS) schemes: IDBS-I and IDBS-II. These
schemes have been designed to prevent forgeable attacks and ensure blindness.
We have implemented an End-to-End verifiable internet voting (E2E-VIV) system
with batch verification based on the proposed IDBS-II scheme. Additionally, we
have demonstrated that the E2E-VIV system meets the required security goals.

There have been discussed several practical E2E-VIV systems. The first system
based on the principle of E2E-VIV is the Rijnland Internet-based election
system (RIES) [68] that enables a voter to access the public algorithm and
parameters to confirm his participation in the election. This verification
procedure is supposed to be secure as compared to the traditional postal
system, but it is far weaker than desired individual verification. Peter Ryan
invented Pret a Voter system [142] that uses a list of shuffled ordering
candidates and a space of vote marking and a traditional cryptographic method.
It enables a voter to verify his vote based on the shuffled ordering
candidate. Identical to Pret a voter’s election experience, Punchscan system
discussed by Popoveniuc et al. [139] allows voting on the paper ballots and
the security is achieved by the use of an optical scanner that reads the
privacy-preserving area. The voter is permitted to verify his receipt with the
published record.

The Scantegrity system [20, 21] generates a random number and distributes it
to the election officials using a secret sharing scheme. It computes a three-
letter code using the random number for each printed ballot and generates a
table for post-election verification. During the election, a voter marks a
choice with invisible ink on the paper to obtain the three-letter code. He can
record the code and ballot ID to check if his vote was tabulated. In
Remotegrity system [181], the voter obtains a lottery-style code and
authentication card with serial numbers. It uses both the serial number and
code against the candidate’s selection and authentication code to cast a vote.
Adida presents a web-based voting system, known as Helios, that can achieve
E2E verifiability and privacy [2]. This method has a unique design mechanism
in the voting device to help the voter in verification during vote casting. A
voter would cast the encoded vote only if he is convinced that the voting
device is not cheating him. Corteir et al. [36] point out that the repetition
of the voter’s choice in the Helios will leak any information about his vote.
In [31, 180], the E-voting system achieves E2E verifiability in the standard
model and is secure under the well-known decisional Diffie-Hellman problem.
Joaquim et al. [77] present an E2E-VIV system that provides the advantage of
mobility and vote privacy to the voters. In [22], each voter has a voter
security token that encrypts the vote to transmit his encoded candidate choice
to the officials.

Most of the above-discussed E2E-VIV systems are paper ballot based. Recently,
a team of experts has suggested moving the election process online as a voter
is particularly interested in the online system [77]. In 1992, Fujiokta et al.
[54] gave the first secret E-voting mechanism based on the blind signature
scheme, which ensures privacy and fairness. Since then, several blind
signatures-based E-voting systems have been discussed [119, 177, 23, 140,
105]. However, they have lacks security and transparency. The E2E
verifiability is one of the tools to promise the integrity and transparency of
the system [23]. Such internet voting systems are based on traditional public
key cryptosystem which requires a significant computational cost for
certificate management and public keys. In this chapter, we proposed two
identity-based blind signature schemes and implement an End-to-End Verifiable
Internet Voting system. We consider the smartphone as a voting device to
collect the voter’s biometric features and authenticate him against his
biometric features and identity, for example, national identification number,
employee ID, and social security number. The proposed E2E-IVS system provides
mobility to a voter and enables him to cast his vote secretly on a public
computer/device without revealing any information about the vote. Now, we
discuss the proposed E2E-IVS system.

###  4.1 System Model

In this section, we give the brief architecture of the E2E-IVS system and its
security requirements. We also define the identity-based blind signature
scheme and its security model.

####  4.1.1 Architecture Design

Here, we discuss the architecture of the proposed E2E-VIV system, which
involves five entities: key generation centre (KGC), voters, candidates,
voting device, and election commission authority (ECA).

  * •

Key Generation Center. The KGC initializes the system, authenticates each
entity (voters, candidates, and ECA) and issues the private keys to them.
Additionally, the KGC maintains a record of registered voters and registered
candidates.

  * •

Voter. A voter is a person in any organization or a citizen of the country
having a unique ID and registered with KGC to obtain his private key.

  * •

Election Commission Authority. The ECA, in the proposed system, is an
election-conducting server that performs the following three processes. (1) It
authenticates the voter and distributes a secret digital blank ballot to him
without knowing his ID. It maintains the record of the valid voters for whom
blank ballots are already issued. (2) It receives and verifies the vote during
the vote-casting phase and issues a witness to him. (3) It filters the
duplicate ballots, counts them, and announces the winner.

  * •

Voting Device. A voting device could be a smartphone or computer that contains
a fingerprint and iris sensor, which is either implanted or attached to the
voting device.

  * •

Candidate. A person nominated by any group or political party who can
participate in the election process. He must be first registered with KGC and
obtain a private key.

The proposed E2E-IVS system consists of the following six algorithms.

  * •

Initialization. The KGC initializes the system and computes its master key
$s_{0}$ and public parameter $pp$. The KGC keeps $s_{0}$ secret and publishes
$pp$.

  * •

Registration. Before the election process, each participating entity is
required to register with KGC. The KGC authenticates the entities against
their IDs and biometric information and issues the private keys to them over
an insecure channel. Further, KGC prepares two lists: $List^{RV}$ and
$List^{RC}$ which contain the biometric details of all the registered voters
and registered candidates, respectively, and passes them to the ECA after
registration.

  * •

Authentication and Ballot distribution. In PKI-based cryptography, the user’s
private key is associated with his ID. Thus, we cannot use the voter’s private
key for signature purposes as it may lose the voter’s anonymity. The pseudonym
public and private keys preserve voter anonymity. In order to preserve
anonymity, the system enables the voter to generate the pseudonym public and
pseudonym private keys. During the blank distribution phase, a voter blinds
and signs the pseudonym public key using his pseudonym private key and asks
the ECA for a blind blank ballot against his pseudonym public key. To
authenticate a voter, the ECA maintains two lists ($List^{RV}$ and
$List^{VV}$) for the registered voters and voters for whom the ballots have
previously been distributed. The ECA first checks if the voter is registered
(i.e., found in list $List^{RV}$), and the blank ballot is not issued to him
previously (i.e., not found in list $List^{VV}$), only then ECA issues a fresh
pseudonym certificate, known as a blank ballot, against the pseudonym public
key to the voter and adds an entry in the list $List^{VV}$; otherwise, it
raises an error. Then, the voter extracts the blank digital ballot using his
secret values.

  * •

Vote casting. An IVS system has many inconsistencies, e.g., network congestion
due to voter traffic during the election period, election server failure, and
people with no internet facility during the election period. The proposed
system allows a voter for early voting to overcome these difficulties. A voter
may cast a vote before the election date using a timestamp T that ensures the
freshness of the vote. During the election and/or pre-election, a voter
chooses a candidate from the list $List^{RC}$, computes the electronic ballot
$Bt$ using BLS short signature scheme and passes it to ECA. The ECA
authenticates the voter and validates the ballot B, and issues an electronic
receipt if both conditions are satisfied; otherwise, it rejects the vote and
adds $Bt$ in $List^{B}$ (initially empty). The ECA includes a unique random
value in each receipt that makes it fresh and unique.

  * •

Vote counting. When the voting day is over, the ECA stops to receive
additional ballots. It makes sure that there are no invalid or duplicate
electronic ballots. To identify the duplicate votes in the list $List^{B}$,
ECA manages two lists: $List^{V}$ to store the details of valid voters, and
$List^{IV}$ to store the details of invalid voters. The ECA separates the
invalid votes from the list $List^{B}$ by identifying two ballots having the
same signature. Finally, the ECA publishes both lists.

  * •

Auditing. After the election process is over, the voter verifies if his vote
corresponding to his receipt is in the ballot list $List^{V}$ or $List^{IV}$.
Also, anyone can verify if all ballots are counted correctly.

####  4.1.2 Security Requirements for E2E-IVS System

This section discusses the security requirements for the internet-based voting
system.

  * •

Voter’s anonymity. It must ensure the vote anonymous against the voter’s ID
who is able to vote.

  * •

Vote integrity. The system must be secure against an adversarial attack on an
individual voter’s devices and on its architecture. It must also ensure the
vote’s privacy.

  * •

Voter’s eligibility. The system must permit only eligible/authentic voters to
vote.

  * •

Uniqueness. It must ensure that a voter gets only one ballot, and can cast
only one vote.

  * •

Resistant to bribery and coercion. In any election process, the collusion
between a voter and a candidate may give two main inconsistencies: i) the
candidate may give some bribe to the voter (bribery), or ii) the candidate may
threaten or force a voter (coercion). During as well as after the vote
counting process, a voter can freely cast his vote under coercion and bribery
situations and cannot prove whom he supported.

  * •

Ballot stuffing. An illegal practice of voting, i.e., casting multiple ballots
during a vote should not be possible, whereby one ballot is allowed.

  * •

Individual verifiability. Any voter can verify that his ballot is correctly
involved in the ballot list.

  * •

Universal verifiability. Anyone can verify that all ballots in the list have
been correctly tallied.

  * •

Batch verifiability. In order to optimize the cost of verification, the system
must verify the massive ballots simultaneously.

####  4.1.3 Identity-based Blind Signature Scheme

It involves three entities: Signer, User and Private Key Generator (PKG) that
perform four randomized probabilistic polynomial-time (PPT) algorithms: Setup,
Key Extract, Blind Signature, and Verify.

  * •

Setup: The PKG computes the master key s and a public parameter $pp$. It keeps
s secret and publishes$pp$.

  * •

Key Extract: The PKG computes the private key $d_{IDS}$ against the signer’s
$ID_{S}$ using and param and sends $d_{IDS}$ to the signer.

  * •

Blind Signature: Without knowing the content of message $M$, the signer signs
on it as follows.

    * –

Blinding: The user blinds m using its secret key and requests to the signer
for signature on the blinded $M$.

    * –

Signing: Given blinded $M$, the signer computes a blind signature using its
private key $d_{S}$ and sends it to user.

    * –

Unblinding: The user retrieves the original signature $\sigma$.

Verifying: On given tuple $<M,\sigma>$ and signer’s identity $ID_{S}$, the
user verifies the signature.

####  4.1.4 Security Threat

The proposed IDBS scheme is considered to be secure if it achieves the
blindness property and under the chosen message and ID attack, it is
existentially unforgeable (EUF-ID-CMA).

EUF-ID-CMA: It can be defined by the following game playing between the Forger
$F$ that acts as a malicious user and challenger $Ch$ that acts as the signer.

The IDBS scheme is EUF-ID-CMA secured if forger $F$ has a negligible advantage
in the following game.

Setup: The $Ch$ computes its master key and public parameters, where it keeps
the master key and responds public parameter to $F$.

Oracle: $F$ performs the following oracles.

  * •

Extract oracle: On given $ID$, $Ch$ runs this oracle to compute the private
key $d_{S}$ and sends to $F$.

  * •

Blind signature oracle: For given $ID$ and message $M$, $F$ blindly requests a
signature on m from $Ch$. The $Ch$ runs the oracle to generate the signature
and gives to $F$

Forgery: At the end, the forger $F$ responds with a Message-Signature pair
$<M^{*},\sigma^{*}>$ against $ID^{*}$. The forger $F$ will win the game if it
fulfils the following conditions.

  * •

$<M^{*},\sigma^{*}>$ is the valid message-signature pair against $ID^{*}$.

  * •

The Blindsig oracle has not been queried on $<M^{*},\sigma^{*}>$.

  * •

The extract oracle has not been queried on $ID^{*}$.

Unlinkability. The blindness security notion can be understood using the
following game playing between the adversary $Adv$ that acts as a malicious
signer and Challenger Ch that acts as the honest user. The user have two
distinct message $<M_{b},M_{1-b}>$ engaged in the proposed IDBS scheme and
obtains the signatures $<\sigma_{b},\sigma_{1-b}>$, where $b\in\\{0,1\\}$.

The IDBS scheme is unlinkable if forger $F$ has a negligible advantage in the
following game.

Setup: The Ch computes its master key and public parameters, where it keeps
the master key and responds public parameter to the $F$. Oracle: $F$ performs
the following oracles.

  * •

Extract oracle: For given $ID$, $Ch$ runs this oracle to get the private key
$d_{S}$ and sends it to $F$.

  * •

Blind signature oracle: For given $ID$ and message $M$, $F$ blindly requests a
signature on $M$ from $Ch$. The $Ch$ runs the oracle to generate the signature
$\sigma$ and gives to $F$.

Challenge: $Ch$ pick a bit $b\in\\{0,1\\}$ at random and ask $Adv$ for
signature on $M_{b}$ and $M_{1-b}$. Finally, $Ch$ generates the signature
$<\sigma_{b},\sigma_{1-b}>$ on message $<M_{b},M_{1-b}>$ and gives
$<\sigma_{b},\sigma_{1-b}>$ to $F$.

Response: For the given tuple $\langle
M_{0},M_{1},\sigma_{b},\sigma_{1-b}\rangle$, $F$ predicts a bit
$b^{\prime}\in{0,1}$ and wins the game if $b=b^{\prime}$ holds with advantage
$|\Pr[b=b^{\prime}]|\geq\frac{1}{2}+k^{-n}$.

###  4.2 Proposed Identity-based Blind Signature schemes

In this section, we proposed two identity-based blind signature schemes:
IDBS-I and IDBS-II.

####  4.2.1 ID-based Blind Signature-I Scheme

The proposed IDBS-I scheme consists of four algorithms run between the user
and the signer defined as follows:

  * •

Setup: Suppose $P$ be the generator of group $\mathbb{G}_{1}$ of prime order
$q$. Bilinear map
$e:\mathbb{G}_{1}\times\mathbb{G}_{1}\rightarrow\mathbb{G}_{2}$. Let three
pre-image resistant cryptographic hash functions are
$H_{1}:\\{0,1\\}^{*}\rightarrow\mathbb{G}_{1}$,
$H_{2}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}$,
$H_{3}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$, and
$H_{4}:\mathbb{G}_{2}\times\mathbb{Z}_{q}\rightarrow\\{0,1\\}^{*}$. Let the
private key of the signer, and the user is denoted as $d_{S}$ and $d_{U}$,
respectively. Let $t$ indicate the timestamp. PKG selects randomly
$s\in\mathbb{Z}_{q}$ and computes public key $P_{Pub}=sP$. PKG publishes
$pp=<\mathbb{G}_{1},q,e,P,P_{Pub},H_{1},H_{2},H_{3},H_{4}>$, and keeps secret
key $s$ secretly.

  * •

Extract: PKG computes $d_{S}=sQ_{S}$, and $d_{U}=sd_{U}$, where
$Q_{S}=H_{1}(ID_{S})$ and $Q_{U}=H_{1}(ID_{U})$, and sends $d_{S}$ and $d_{U}$
to the signer and the user, respectively.

  * •

BlindSig: Suppose a user wants to sign on message M, four sub-algorithms
(Commitment, Authenticating & Blinding, Signing, Unblinding) must run between
the signer and the user as follows:

    * –

Commitment: On random chosen integer $s\in\mathbb{Z}_{q}$, the signer computes
$k=e(d_{S},\\\ rH_{2}(t)Q_{U})$ and $R=rH_{2}(t)Q_{S}$, and passes $R$ to the
user.

    * –

Authenticating & Blinding: Using his private key, the user computes
$K=e(d_{U},R)$. If $k\neq K$, the user picks a random number
$a\in\mathbb{Z}_{q}$ as a blinding factor, computes $A=a^{-1}R$,
$h=H_{3}(M,A)$, $b_{M}=ah$ and $X=H_{4}(b_{M},K)$ sends $<b_{M},X>$ to the
signer.

    * –

Signing: The signer computes $X^{\prime}=H_{4}(b_{M},k)$ and check if
$X^{\prime}=X$ holds. For valid justification, the signer produces a signature
with his private key as $S=(rH_{2}(t)+b_{M})d_{S}$ and sends it back to the
user.

    * –

Unblinding: The user unblinds the blinded signature $S$ with blinding factor
$a$ as $S^{\prime}=a^{-1}S$, and publishes signature $<S^{\prime},A,M>$ on the
message $m$.

  * •

Verify: On given $<S^{\prime},A,M>$, verify that
$(S^{\prime},P,A+H_{3}(M,A)Q_{S},P_{Pub})$ is a valid Gap-Diffie-Hellman
tuple, i.e., if DDHP is easy to solve while CDHP is hard, the signature is
valid. Using the pairing mapping function, the verifier accepts the signature
if and only if

$e(S^{\prime},P)=e(A+H_{3}(M,A)Q_{S},P_{Pub})$ (4.1)

####  4.2.2 ID-based Blind Signature-II Scheme

Our proposed IDBS-II scheme consists of four PPT algorithms: setup, extract,
blind signature, and verify. These are defined as follows.

  * •

Setup: Given a security parameter $k$, the PKG assumes an additive group
$\mathbb{G}_{1}$ of order $q$, where $q$ is large prime number of $k$-bit and
its generator be $P$. PKG defines two hash function
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$ and
$H_{2}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$. The PKG
chooses a random element $s\in\mathbb{Z}_{q}$ (its master key) and computes
the public key $P_{Pub}=sP$. The PKG publishes the public parameter
$pp=<\mathbb{G}_{1},q,P,P_{0},H_{1},H_{2}>$, and keeps $s$ secret.

  * •

Extract: For given signer’s identity $ID_{S}$, $pp$ and its master key $s$,
PKG chooses a random number $a\in\mathbb{Z}_{q}$, computes the signer’s
private key $<A=aP,d_{IDS}=a+sQ_{S}>$, where $Q_{S}=H_{1}(A,ID_{S})$ and gives
$<A,d_{S}>$ to the signer.

    * –

Blind signature: The signer and user perform the following steps to obtain a
signature on the message.

    * –

Commitment: The signer selects two random elements
$n_{1},n_{2}\in\mathbb{Z}_{q}$, computes $Q_{1}=n_{1}P$ and $Q_{2}=n_{2}P$,
and sends them to the user.

    * –

Blinding: For given received parameters $<Q_{1},Q_{2}>$ and message $m$, the
user selects six elements $g,h,i,j,k,l\in\mathbb{Z}q$, such that $\gcd(i,j)=1$
and $ki+lj=\gcd(i,j)$. For the selection of elements $k$ and $l$, we use the
Extended Euclidean algorithm. The user then computes the parameters $b{M1}$
and $b_{M2}$ using equations (4.2)-(4.7) and asks the signer for a signature
on $<b_{M1},b_{M2}>$.

$R_{1}=gQ_{1}+iP\hskip 8.53581ptand\hskip 8.53581ptr_{1}=absc(R_{1})modq$
(4.2) $R_{2}=hQ_{2}+jP\hskip 8.53581ptand\hskip
8.53581ptr_{2}=absc(R_{2})modq$ (4.3) $r=r_{1}r_{2}modq$ (4.4)
$R=R_{1}+R_{2}+r(A+Q_{ID}P_{0})$ (4.5) $b_{M1}=kg^{-1}i(H_{2}(M,R)-r)modq$
(4.6) $b_{M2}=lh^{-1}j(H_{2}(M,R)-r)modq$ (4.7)

    * –

Signature: On received parameters $<b_{M1},b_{M2}>$ and its private key
$d_{IDS}$, signer computes $S^{\prime}_{1}=(d_{IDS}b_{M1}-n_{1})modq$ and
$S^{\prime}_{2}=(d_{IDS}b_{M2}-n_{2})modq$, and sends
$<S^{\prime}_{1},S^{\prime}_{2}>$ to the user.

    * –

Unblinding: On received parameters $<S^{\prime}_{1},S^{\prime}_{2}>$ using his
secret values, i.e., $<g,h,\\\ i,j>$, user computes the original signature
$\sigma=<S,R>$, where $S=(S_{1}+S_{2})$, $S_{1}=(S^{\prime}_{1}g-i)$ and
$S_{2}=(S^{\prime}_{2}h-j)$. The user sends the signature pair $<S,R,A>$ to
the verifier.

  * •

Verify: For given signature pair $<A,S,R>$, the user verifies the valid
signature if and only if it satisfied the Eequation
$H_{2}(M,R)(A+H_{1}(A,ID_{S})P_{Pub})=SP+R$.

###  4.3 Security Analysis

In this section, we provide the security proof of the proposed IDBS-I and
IDBS-II schemes.

######  Theorem 4.1.

(Consistency). The proposed IDBS-I and IDBS-II schemes are consistency.

###### Proof.

The correctness of the proposed IDBS-I scheme is verified as follows.

Since, $S^{\prime}=a^{-1}S$, we have

$\displaystyle e(S^{\prime},P)$ $\displaystyle=e(a^{-1}S,P)$
$\displaystyle=e(a^{-1}(rH_{2}(t)+b_{M})d_{IDS},P)$
$\displaystyle=e(a^{-1}(rH_{2}(t)+aH_{3}(m,A))Q_{IDS},P_{Pub})$
$\displaystyle=e(a^{-1}R+H_{3}(m,A)Q_{IDS},P_{Pub})$
$\displaystyle=e(A+H_{3}(m,A)Q_{IDS},P_{Pub})=RHS$

This completes the correctness of the proposed IDBS-I scheme. Now, we prove
the consistency of the proposed IDBS-II scheme.

We have $S=(S_{1}+S_{2})$, then

$\displaystyle SP+R$
$\displaystyle=(S_{1}+S_{2})P+R=(S^{\prime}_{1}g-i+S^{\prime}_{2}h-j)P+R$
$\displaystyle=((d_{IDS}b_{M1}-n_{1})g-i+(d_{IDS}b_{M2}-n_{2})h-j)P+R$
$\displaystyle=(d_{IDS}ki(H_{2}(M,R)-r)-n_{1}g-i+d_{IDS}lj(H_{2}(M,R)-r)-n_{2}h-j)P+R$
$\displaystyle=d_{IDS}H_{2}(M,R)(ki+lj)P-(ki+lj)rd_{IDS}P-n_{1}gP-n_{2}hP-iP-
jP+R$ $\displaystyle=d_{IDS}H_{2}(M,R)P-(rd_{IDS}P+n_{1}gP+n_{2}hP+iP+jP)+R$
$\displaystyle=(a+sQ_{ID})H_{2}(M,R)P-(r(a+sQ_{ID})P+gQ_{1}+hQ_{2}+iP+jP)+R$
$\displaystyle=(A+Q_{ID}P_{Pub})H_{2}(M,R)-R+R$
$\displaystyle=(A+Q_{ID}P_{Pub})H_{2}(M,R)$

This proves the consistency of the proposed IDBS-II scheme. ∎

######  Theorem 4.2.

(Un-forgeability). Suppose $H_{1}$ and $H_{2}$ are two random oracle models
and a forger $F$ wants to forge a signature on message $M$. Suppose forger $F$
executes at most $q_{E}$ extract oracles, $q_{B}$ Blind signature oracles,
$q_{1}$ $H_{1}$ hash oracles, $q_{2}$ $H_{2}$ hash oracles, runs at most $t$
times with advantage at most $k^{-n}$. Under the assumption of ROM and
intractable to solve the ECDLP, our proposed IDBS Scheme is existential and
Un-forgeable secured against the adaptive chosen message and identity attacks.
Forger $F(t,q_{1},q_{2},q_{E},q_{B},k^{-n})$ have the following advantage to
break the proposed IDBS-II scheme.

$|Pr[F(t,q_{1},q_{2},q_{E},q_{B},k^{-n})]|\geq\epsilon(1-q_{1}/k)^{q_{2}+q_{E}}$
(4.8)

###### Proof.

Consider a forger $F$ wish to forge any signature in the proposed ID-BS scheme
and let there exist an algorithm $B$ which helps $F$. We design an algorithm
$B$ that helps $F$ to solve the ECDLP.

Setup: $B$ considers two cryptographic hash functions
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$ and
$H_{2}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}$ and is accountable to simulate
these oracles. $B$ picks $a\in\mathbb{Z}_{q}$, set $P_{0}=aP$ and gives public
parameter $pp=<\mathbb{G}_{1},q,P,P_{0},H_{1},H_{2}>$ to $F$.

Oracles: Forger $F$ can perform the following oracles.

  * •

$H_{1}$ oracle: $B$ prepares an empty list $H_{1}^{List}$ having tuple
$<R_{Xi},ID_{i},H_{1}(ID_{i},R_{Xi}),*>$. When $F$ queries to $H_{1}^{List}$
on $<ID_{i},R_{Xi}>$, $B$ responds $F$ in the following way.

    * –

$B$ gives $H_{1}(ID_{i},R_{Xi})$ to $F$ and adds the tuple
$<R_{Xi},ID_{i},H_{1}(ID_{i},R_{Xi}),*>$ to list $H_{1}^{List}$, if
$ID_{i}=ID^{*}$.

    * –

Otherwise, $B$ chooses randomly $m_{i}\in\mathbb{Z}_{q}$ and gives
$H_{1}(ID_{i},R_{Xi})=-m_{i}$ to $F$ and adds tuple
$<R_{Xi},ID_{i},H_{1}(ID_{i},R_{Xi}),m_{i}>$ to list $H_{1}^{List}$.

    * –

$B$ gives $H_{1}(ID_{i},R_{Xi})$ to $F$, if $<ID_{i},R_{Xi}>$ found in the
$H_{1}^{List}$ in the tuple of $<R_{i},ID_{i},\\\ H_{1}(ID_{i},R_{Xi}),m_{i}>$
or $<R_{Xi},ID_{i},H_{1}(ID_{i},R_{Xi}),*>$.

Note, $H_{1}(ID,R_{X})$ gives no information to $F$ until he queries the
$H_{1}$ oracle on $ID$ as $H_{1}$ is the random oracle.

  * •

$H_{2}$ oracle: On given parameters $R$ and $h$, $B$ runs $H_{2}$ oracle and
gives the output to the $F$. Suppose $z_{1}$, $z_{2}$ and $z_{3}$ are outputs
when $H_{2}$ oracle executes three times.

  * •

Key Extract oracle: $B$ simulate the extract oracles. It pick
$n_{i}\in\mathbb{Z}_{q}$ and set $R_{Xi}=m_{i}P_{0}+n_{i}P$ in such that
$d_{Xi}=m_{i}$ and $H_{1}(ID,A_{i})=a_{i}$, and add
$<R_{Xi},ID_{i},H_{1}(ID_{i},R_{Xi}),d_{Xi}>$ in list. We set these parameters
such that they satisfy the Equation (4.9).

$d_{Xi}P=R_{Xi}+H_{1}(ID_{i},R_{Xi})P_{0}$ (4.9)

  * •

Ballot issuing oracle: $F$ queries the blind ballot issuing algorithm to get a
blind signature on message $M_{i}$ with identity $ID_{i}$. Let $F$ give the
blinded ballot $<b^{\prime}_{R1},b^{\prime}_{R2}>$ to $B$. Then, $B$ responds
to the following oracles.

    * –

If $ID_{i}\neq ID^{*}$, using $ID_{i}$ corresponding to $H_{1}^{List}$, $B$
executes the extraction oracles and signs the ballot using the corresponding
private key.

    * –

If $ID_{i}=ID^{*}$, $B$ executes $H_{2}$ oracles on ballot $R_{i}$ and picks
up the tuple $<R_{Xi},ID_{i},\\\ H_{1}(ID_{i},R_{Xi}),d_{Xi}>$ from
$H_{1}^{List}$ to sign ballot $R_{i}$ and outputs the corresponding signature
$<\sigma_{i}^{*}=(s_{i}^{*},R^{*},h^{*}),R_{X}^{*}>$ to $F$.

Forgery. $F$ responds a signature
$<\sigma_{i}^{*}=(s_{i}^{*},R^{*},h^{*}),R_{X}^{*}>$ pair against identity
$ID^{*}$. In order to forge a signature, suppose the forger $F$ creates three
distinct signatures $(\sigma_{1}^{*},\sigma_{2}^{*},\sigma_{3}^{*})$ on same
message $M$, where $<\sigma_{1}^{*}=(s_{1}^{*},R^{*},h_{V}^{*}),R_{X}^{*}>$,
$<\sigma_{2}^{*}=(s_{2}^{*},R^{*},h_{V}^{*}),R_{X}^{*}>$ and
$<\sigma_{3}^{*}=(s_{3}^{*},R^{*},h_{V}^{*}),R_{X}^{*}>$. We consider
$s_{0},r_{X}$ and $u$ as the discrete logarithm of $P_{0},R_{X}$ and $R$,
respectively, i.e., $P_{0}=s_{0}P$, $R_{X}=r_{X}P$ and $R=uP$. From
$sP=H_{2}(R,h_{V})(R_{X}+H_{1}(ID_{X},R_{X})P_{0})-R$, we get
$s_{i}^{*}=(z_{i}(r_{X}+s_{0}H_{1}(ID,R_{X}))-u)modq$ for $1\leq i\leq 3$. The
parameters $s_{0},r_{X}$ and $u$ from these equations are unknown to $F$.
Thus, $F$ solves three linear equations to obtain these values, which is
equivalent to solving the ECDL problem.

Analysis. The probability that $B$ does not abort the game is denoted as
$Pr[\neg E_{1}\wedge\neg E_{2}]$.

  * •

$E_{1}$: The extract oracle fails if $H_{1}$ oracle outputs the inconsistent
outputs with probability at most $q_{1}/k$. The simulation is completed in
$q_{E}$ time, which happens with probability at least $(1-q_{1}/k)^{q_{E}}$.

  * •

$E_{2}$: The execution of $H_{2}$ oracle fails if $H_{2}$ oracle gives the
inconsistent outputs with probability at most $q_{1}/k$. The simulation is
completed in $q_{2}$ time, which happens with probability at least
$(1-q_{1}/k)^{q_{2}}$.

From these two events, we obtain the probability that Adv can break the scheme
with

$Pr[\neg E_{1}\wedge\neg E_{2}]\geq\epsilon(1-\frac{q_{1}}{k})^{q_{2}+q_{E}}$

∎

######  Theorem 4.3.

(Blindness). The proposed IDBS-II scheme achieves the blindness property.

###### Proof.

Suppose an adversary $Adv$ that plays the role of ECA and challenger $Ch$ that
plays a role of an honest voter runs the blind signature algorithm. Suppose
Adv obtains the parameters $<b_{R1},b_{R2},s^{\prime}_{1},s^{\prime}_{2}>$ by
executing the ballot issuing oracle. Let the corresponding signature be
$<R,h_{V},s>$. There exists a tuple of values $<a,b,c,d,e,f>$ that links
$<b_{R1},b_{R2},s^{\prime}_{1},s^{\prime}_{2}>$ to $<R,h_{V},s>$.

From $b_{R1}=ea^{-1}c(H_{2}(R,h_{V})-r)$ and
$b_{R2}=fb^{-1}d(H_{2}(R,h_{V})-r)$, we get $a=eb_{R1}^{-1}c(H_{2}(R,h)-r)$
and $b=fb_{R2}^{-1}d(H_{2}(R,h_{V})-r)$, respectively. Similarly, from
$s_{1}=(s^{\prime}_{1}a-c)$ and $s_{2}=(s^{\prime}_{2}b-d)$, we get
$c=(s^{\prime}_{1}a-s_{1})$ and $d=(s^{\prime}_{2}b-s_{2})$, respectively. By
substituting these values in $R=aA_{1}+bA_{2}+(c+d)P+r(R_{E}+Q_{E}P_{0})$, it
can be noted that $Adv$ must know the value of $r$ to compute $R$. The value
$r$ depends on $<a,b,c,d>$ whose production is equivalent to solving the ECDL
problem. Thus, the proposed E2E-VIV system provides voter anonymity. ∎

###  4.4 Construction of End-to-End Verifiable Internet Voting System

Here, we construct the E2E-IVS system using the IDBS-II scheme, which consists
of six algorithms. In Algorithm (4.1), the KGC initializes the system, and
computes its master key $s_{0}$ and public parameter param. It keeps $s_{0}$
secret and publishes $pp$.

Algorithm 4.1 System initialization

1:Given a security parameter $k$, choose three groups
$\mathbb{G}_{1}$,$\mathbb{G}_{2}$ and $\mathbb{G}_{T}$ of order $q$ ($k$-bit),
a generator $P$ of $\mathbb{G}_{1}$, a generator $Q$ of $\mathbb{G}_{2}$, and
bilinear map $e:\mathbb{G}_{1}\times\mathbb{G}_{2}\rightarrow\mathbb{G}_{T}$.

2:Choose five hash functions,
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$,
$H_{2}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$,
$H_{3}:\\{0,1\\}^{*}\rightarrow\mathbb{Z}_{q}$,
$H_{4}:\\{0,1\\}^{*}\rightarrow\mathbb{G}_{2}$ and
$H_{5}:\mathbb{Z}_{q}\times\mathbb{G}_{1}\times\mathbb{Z}_{q}\times\mathbb{G}_{1}\times\mathbb{G}_{2}\times\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$.

3:Choose an element $s_{0}\in\mathbb{Z}_{q}$ (its master key) and compute the
public key $P_{Pub}=sP$.

4:Publishes the public parameter
$pp=<q,e,P,P_{Pub},\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},H_{1},H_{2},H_{3},H_{4},H_{5}>$,
and keeps $s_{0}$ secret.

Algorithm 4.2 Registration and key generation

1:KGC prepares two lists: $List^{RV}$ and $List^{RC}$.

2:On given identity $ID_{E}$. The KGC picks a random element
$r_{E}\in\mathbb{Z}_{q}$, and computes the private key $<d_{E},R_{E}>$, where
$R_{E}=r_{E}P$, $Q_{E}=H_{1}(ID_{E}||R_{E})$ and $d_{E}=r_{E}+sQ_{E}$, and
sends it to the to ECA over a secure channel.

3:Candidate scans his biometric data and computes
$h_{3C}=H_{3}(binfo_{C}||ID_{C})$, using his identity $ID_{C}$.

4:Given $h_{3C}$ and $ID_{C}$, candidate asks KGC for its private key. The KGC
picks a random element $r_{C}\in\mathbb{Z}_{q}$, and computes a private key
$<d_{C},R_{C}>$, where $R_{C}=r_{C}P$, $Q_{C}=H_{1}(ID_{C}||R_{C})$ and
$d_{C}=r_{C}+sQ_{C}$, and sends it to the candidate and adds an entry $h_{3C}$
to $List^{RC}$.

5:Similarly to step 4, the voter obtains his private key $<d_{V},R_{V}>$ from
KGC, where KGC maintains list $List^{RV}$ for registered voters.

6:KGC sends lists ($List^{RV}$ and $List^{RC}$) to ECA and candidate and
$List^{RC}$ to voter.

In Algorithm (4.2), KGC registers every entity (voter, ECA and candidate)
against their $IDs$ and biometric information $h_{3}$. It issues a private key
$(d_{x},R_{x})$ to the entity over a secure channel and adds an entry of
entity’s $h_{3}$ in the respective list: $List^{RV}$ or $List^{RC}$. The KGC
outputs both lists to ECA and $List^{RC}$ to voter. The private key
$(d_{x},R_{x})$ can be verified using Equation (4.10), where x denotes the
entity.

$d_{x}P=H_{1}(ID_{x}||R_{x})P_{Pub}+R_{x}$ (4.10)

Algorithm 4.3 Authentication and Ballot distribution

1:ECA chooses two secret integers $a_{1}$, $a_{2}\in\mathbb{Z}_{q}$, computes
$<A_{1}=a_{1}P,A_{2}=a_{1}P,R_{E}>$ and gives them to voter.

2:Ballot request: Voter performs the following steps:

3: Select six elements $a,b,c,d,e,f\in\mathbb{Z}_{q}$ such that $gcd(c,d)=1$
and $ec+fd=gcd(c,d)$.

4: Compute a pseudonym public key $R$ as follows.

5: $R_{1}=aA_{1}+cP$ and $r_{1}=absc(R_{1})modq$

6: $R_{2}=bA_{2}+dP$ and $r_{2}=absc(R_{2})modq$

7: $r=r_{1}r_{2}modq$

8: $R=R_{1}\mathbb{Z}_{q}+R_{2}+r(R_{E}+Q_{E}P_{0})$

9: $h_{3V}=H_{3}(binfo_{V},ID_{V})$

10: $h_{V}=ah_{3}V+c$

11: $b_{R1}=ea^{-1}c(H_{2}(R,h_{V})-r)modq$

12: $b_{R2}=fb^{-1}d(H_{2}(R,h_{V})-r)modq$

13: $U_{1}=(ab_{R1}+bb_{R2})P$

14: $U_{2}=rP$

15: Send $<b_{R1},b_{R2},R,h_{V},h_{3}V,U_{1},U_{2}>$ to ECA for requesting a
blank ballot.

16:Authentication: ECA authenticates the voter using three conditions.

17: $U_{1}==(H_{2}(R,h_{V})P-U_{2})$

18: $h_{3V}\in List^{RV}$

19: $h_{3V}\notin List^{VV}$

20:Ballot issuing: If the above conditions are satisfied, ECA performs the
following steps.

21: Compute $s^{\prime}_{1}=(d_{E}b_{R1}-a_{1})modq$ and
$s^{\prime}_{2}=(d_{E}b_{R2}-a_{2})modq$

22: Issue a blind ballot $<s^{\prime}_{1},s^{\prime}_{2}>$ to voter and add
$h_{3V}$ to $List^{VV}$.

23:Unblinding: Voter unblinds the blind ballot and computes the blank ballot
$BB$ as follow.

24: Compute $s_{1}=(s^{\prime}_{1}a-c)modq$, $s_{2}=(s^{\prime}_{2}b-d)modq$
and $s_{12}=(s_{1}+s_{2})modq$.

25:The ballot is $BB=<s_{12},R,h_{V}>$.

Algorithm 4.4 Vote Casting

1:The voter chooses $C_{name}\in List^{RC}$, timestamp $T$ and preforms the
following steps.

2:Compute $V_{1}=aH_{4}(C_{name}||T)$ and $V_{2}=a(R_{E}+Q_{E}P_{0})$.

3:Set ballot $B=<BB,V_{1},V_{2},C_{name},T>$ and sends it to ECA.

4:ECA validates the vote ballot $B$ using (4.11) and (4.12).

5: $d_{E}H_{2}(R,h_{V})P\overset{?}{=}s_{1}2P+R$ (4.11)
$e(d_{E}P,V_{1})\overset{?}{=}e(V_{2},H_{4}(C_{n}ame||T))$ (4.12)

6:if ( then4.11) and (4.12) are valid,

7: ECA picks a random element $n_{c}\in\mathbb{Z}_{q}$, and sets receipt as
$P_{n_{c}}=n_{c}P$, $Rcpt=H_{5}(B||P_{n_{c}})$ and $s_{Rcpt}=n_{c}+d_{E}Rcpt$
and adds $<B,P_{n_{c}},Rcpt,s_{Rcpt}>$ in $List^{B}$.

8: Sends receipt $<P_{n_{c}},Rcpt,s_{Rcpt}>$ to voter

9:end if

In Algorithm (4.3), the voter requests for the digital ballot in which ECA
authenticates the voter by checking his biometric parameters and makes a list
$List^{VV}$ for valid voters to whom a ballot is issued. If the valid voter
has not received any ballot previously, the ECA issues a fresh blind blank
ballot to him without knowing any information about his identity. Finally, the
voter extracts the blank ballot. Algorithm (4.4) defines the vote-casting
process in which a voter picks a candidate that he supports, computes the
signature on his choice of support using the short signature scheme [14] and
attaches it with the blank ballot to produce the electronic ballot B. The
voter sends the electronic ballot to ECA which verifies the ballot and vote
and acknowledges the receipt to the voter. ECA prepares a list $List^{B}$
where it stores the ballot’s information $<B,P_{n_{c}},S_{Rcpt},Rcpt>$.

Table 4.1: Filtrating duplicate ballots and separating them into valid and
invalid ballot lists.

$R$ | $s_{12}$ | $h_{V}$ | Ca | $V_{1}$ | $V_{2}$ | Actions
---|---|---|---|---|---|---
0@ | 0 | 0 | 0 |  $\times$# | $\times$ | add one ballot in $List^{VB}$ and reject other
0 | 0 | 0 | 1@@ | $\times$ | $\times$ | add one ballot in $List^{VB}$ and other in $List^{IB}$
$\times$ | 1 | $\times$ | $\times$ | $\times$ | $\times$ | both ballot are add in $List^{IB}$
1 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | both ballot are add in $List^{IB}$
$\times$ | $\times$ | 1 | $\times$ | $\times$ | $\times$ | both ballot are add in $List^{IB}$
1 | 1 | 1 | $\times$ | $\times$ | $\times$ | both ballot are add in $List^{VB}$

@if the corresponding parameter in two ballots has the same values, @@if the
corresponding parameter in two ballots has the different value, acandidate
vote and #denotes don’t care.

1:ECA prepares two list: $List^{VB}$ and $List^{IB}$

2:Pick two tuples

3: $B_{i}=<s_{12i},R_{i},h_{Vi},V_{1i},V_{2i},C_{name_{i}}>$ and

4: $B_{j}=<s_{12j},R_{j},h_{Vj},V_{1j},V_{2j},C_{name_{j}}>\in List^{B}$

5:Using Table 4.1, ECA filters the two ballots into two lists $List^{VB}$ and
$List^{IB}$.

6:Publishes $List^{VB}$ and $List^{IB}$.

Algorithm 4.5 Vote Counting

Algorithm (4.5) counts the valid ballot from the pre-maintained list
$List^{B}$. Suppose two ballots in list $List^{B}$ are
$B_{i}=<R_{i},s_{12i},h_{Vi},C_{name_{i}},V_{1i},V_{2i}>$ and
$B_{j}=<R_{j},s_{12j},h_{Vj},C_{name_{j}},V_{1j},V_{2j}>$. The ECA creates
lists $List^{VB}$, which contains the valid ballot details, and $List^{IB}$,
which contains the invalid ballot details. The ECA filters the duplicate
ballot and separates it into $List^{VB}$ or $List^{IB}$. The ECA performs
$B_{i}\oplus B_{j}$, where $\oplus$ denotes the exclusive-or operation that
outputs the set of bits for each ballot’s parameters. The resultant bits match
with the tuple of Table 4.1 that decide which corresponding action has to be
performed with the two ballots. In the end, the ECA publishes both lists:
$List^{VB}$ and $List^{IB}$. Algorithm (4.6) enables a voter to check if his
vote is present in the ballot list. If a voter finds that his receipt is
present in $List^{VB}$ and, using Equation (4.13) he checks the ballot that he
intended. Also, anyone can find that a receipt is recorded in $List^{VB}$ and
can check if the vote is recorded as the voter intended using Equation (4.14).
Further, anyone can count ballots from the published list $List^{VB}$ and can
verify that all ballots are correctly counted.

Algorithm 4.6 Auditing

1:On given $<s_{R}cpt,P_{n_{c}}>$, voter finds his ballot in lists $List^{VB}$
and $List^{IB}$

2:Voter checks whether his ballot is correctly recorded as he intended, using
Equation (4.13).

3:
$Q_{V}s_{Rcpt}P=Q_{E}H_{5}(B,P_{n_{c}})(Q_{E}^{-1}Q_{V}R_{E}+s_{V}P-R_{V})+Q_{V}P_{n_{c}}$
(4.13)

4:Any entity, say $X$, can check using Equation (4.14) whether the ballot is
correctly recorded as the voter intended without knowing the actual vote.

5:
$Q_{X}s_{Rcpt}P=Q_{E}H_{5}(B,P_{n_{c}})(Q_{E}^{-1}Q_{X}R_{E}+s_{X}P-R_{X})+Q_{X}P_{n_{c}}$
(4.14)

###  4.5 Security Analysis of E2E-VIV System

Here, we carry out the security analysis of our proposed E2E-VIV systems.

  * •

Voter anonymity. During and after the election process, the voter’s identity
must be hidden from other entities in the system. In the ballot distribution
process, Theorem 4.2 ensures the voter’s anonymity. For requesting a ballot
and casting a vote, a voter generates the pseudonym public-private key pair
($R,<a,b,c,d,e,f>$) instead of using his private key ($d_{V},R_{V}$). In the
vote casting phase, the ECA verifies the blank ballot BB that corresponds to
the pseudonym public key $R$ without knowing the information about the voter’s
real identity. In order to protect the voter’s biometric information, we use
the pre-image collision-resistant hash function $H_{3}$ that encrypts the
biometric information. So, the use of pseudonym public and private key pair,
pre-image resistant hash function $H_{3}$ and Theorem 4.2 prove that our
system preserves the voter’s anonymity.

  * •

Resistant to Bribery and Coercion. After the election, in our proposed system,
the ECA issues a receipt <$P_{n_{c}},Rcpt,s_{Rcpt}$> to each voter, which is
only the witness to the voter to prove that he has cast his vote to the
intended one. In our proposed system, the ECA adds a random number $n_{c}$ to
each receipt to ensure the freshness of the ballot. Any curious voter can show
his choice of vote to others only if he guesses the correct value of $n_{c}$
which is equivalent to computing the ECDLP. Thus, our proposed scheme is
resistant to bribery and coercion attacks.

  * •

Voter’s eligibility/Authentication. The use of a functional digital signature
authenticates a voter against his $ID_{V}$ and biometric details $h_{3V}$ and
stores $h_{3V}$ in list $List^{RV}$ during the registration process. In blank
ballot distribution, the ECA maintains a list $List^{VV}$ for those valid
voters who have been already issued a ballot. From a given blank ballot
$BB=<b_{R1},b_{R2},R,h_{V},h_{3V},\\\ U_{1},U_{2}>$, the ECA authenticates the
voter only if $U_{1}==(H_{2}(R,h_{V})P-U_{2})$, and $h_{3V}$ is in
$List^{RV}$, not in $List^{VV}$. The consistency of the first condition is
proved as follows. From LHS,

$\displaystyle U_{1}$
$\displaystyle=(ab_{R1}+bb_{R2})P=(ec(H_{2}(R,h_{V})-r)+fd(H_{2}(R,h_{V})-r))P$
$\displaystyle=(H_{2}(R,h_{V})-r)(ec+fd)P=H_{2}(R,h_{V})P-rP=H_{2}(R,h_{V})P-U_{2}$

The above equalities show the consistency of the first conditions.

  * •

Vote Integrity. During the ballot-issuing process, the ECA issues a blank
ballot to a voter whose integrity has been proved in Theorem 4.2. During the
vote-casting phase, the integrity of the vote is ensured by the short
signature scheme whose security is equivalent to solving the GDH problem [14].
Thus, the proposed system achieves vote integrity during and after the
election process.

  * •

Uniqueness and Fairness (ballot stuffing). In the proposed system, a voter
assists a pair of pseudonym public and pseudonym private keys for requesting a
blank ballot from the ECA. Before issuing a ballot to a voter, the ECA
prepares a list of valid voters to whom the ballots have already been issued.
In order to authenticate a voter against his voter’s pseudonym public key $R$
and biometric information $h_{3V}$, ECA checks if
$U_{1}==(H_{2}(R,h_{3V})P-U_{2})$ holds and $h_{3V}$ is in lists $List^{RV}$,
not in $List^{VV}$. Now, the ECA issues a fresh blank ballot $BB$ to the voter
and adds $h_{3V}$ in $List^{VV}$. Thus, a voter obtains only one blank ballot
and can cast only one vote. Therefore, the proposed system is resistant to
ballot stuffing. Verifiability. After the election, the ECA publishes the list
of invalid ballots $List^{IB}$ and valid ballot list $List^{VB}$. From given
$<P_{n_{c}},Rcpt,S_{Rcpt}>$, an eligible voter can check if
$<P_{n_{c}},Rcpt,S_{Rcpt}>$ belongs to $List^{IB}$ or $List^{VB}$. The voter
ensures that his vote is counted in the election process if the parameters
$<P_{n_{c}},Rcpt,S_{Rcpt}>$ satisfy Equation (4.12). The consistency of
Equation (4.13) is similar to the consistency of the IDBS-II scheme, which is
proved in Theorem 1.

This proves the consistency of Equation (4.12). Similarly, anyone in the
system can also check participation of receipt using Equation (4.13). Since a
voter is allowed to check the ballot’s status, it can bring the coercion
problem where the voter can check if his vote was correctly counted or not
because the voter can show the value of the vote to anyone. In order to
overcome this inconsistency, the proposed system publishes two lists: invalid
ballot and valid ballot lists, so that he can check to which list his ballot
belongs. In order to count the valid voter, anyone can verify that only valid
votes were counted. Thus, the ECA proves that all receipts of the votes have
been counted corresponding to the valid ballots that were previously verified
and stored. Therefore, the proposed system achieves individual verifiability
and universal verifiability. Since the proposed system uses the fingerprint
and iris sensor-based smartphone as a voting device, the voter can cast a vote
at any place. The use of smartphones with sensor technologies makes the
E2E-VIV system convenient and user-friendly for non-technical users. The
performance efficiency shows that the proposed system is efficient as compared
to other systems/schemes. Also, the system provides an early voting facility
for those voters who are unable to access the network during the election due
to any reason.

###  4.6 Performance Analysis

This section provides a comparison of our E2E-VIV system with the related
electronic voting systems and examines their performance.

####  4.6.1 Experiment Simulation

Table 4.2: Number of machine cycles required by cryptographic operations. Notation | Operations | # Cycles (in Kilo)
---|---|---
#Pr | RSA public key | 766
#Sk | RSA private key | 51,805
#Exp | DSA exponentiation | 17,334
#Sm | ECC scalar point multiplication | 300
#Pm | Pairing multiplication | 450
#MTP | Map-To-Point hash function | 310
#Bp | Bilinear pairing | 2,100

Suppose the Weil pairing is defined over the Type-F curve (BN curve) of PBC
library [122] with 256-bit of one group and 512 bit of another group, and
embedding degree is 12, whose security level is identical to 3072-bit RSA. For
128 bit of AES security of BN curve $E/\mathbb{F}_{P}:y^{2}=x^{3}+b$, where
$b\neq 0$, gives the group size $|\mathbb{Z}_{q}|$ = 256 bit, the field size
of $\mathbb{G}_{1}$, i.e., $|\mathbb{G}_{1}|$ = 160 bit, the field size of
$\mathbb{G}_{2}$, i.e., $|\mathbb{G}_{2}|$ = 512 bit, and the field size of
$\mathbb{G}_{T}$, i.e., $|\mathbb{G}_{T}|$ = 3072 bit. To compare our scheme
with the non-ECC based schemes [23, 33, 109, 169], we consider two large prime
numbers of 3072 bit, i.e., $|p_{1}|=|p_{2}|$=3072 bit, such that their product
is hard to factorize and consider a large prime p of 1024 bit and a prime
factor q of 160 bits, i.e., $|p|$ = 1024 bit, and $|q|$ =160 bit, such that
$(p-1)|q$. Further, we assume that $|C_{name}|=|ID|=|T|$ = 80 bit.

####  4.6.2 Implementation and Benchmark

Here, we compare the performance of our proposed internet-voting system with
related schemes [119], [177], [23], [33], [109], and [169], in terms of
machine cycles obtained by simulating experiment on Intel(R) Core(TM) i7-2600K
CPU @ 3.4 GHz, and 8 GB of RAM, using gcc 4.6. We consider the same
methodology as discussed in [177] to estimate the machine cycles consumed by
operations (for example, private and public operations based on RSA,
operations on elliptic curve and pairing). Table 4.1 summarizes the notations
and number of machine cycles consumed by the required cryptographic
operations.

Table 4.2 shows the performance of our system with the existing systems [119],
[177], [23], [33], [109], and [169]. The proposed system and system [119] use
elliptic curve cryptography, and their security is based on ECDL and GDH
problems. The systems [177], [23], [33], [109], and [169] are based on the
traditional RSA public key cryptosystem and their security is based on the
discrete logarithm problem (DLP) and integer factorization problems (IFP). It
can be seen from Table 4.2 that the ECC-based operations (scalar
multiplication and addition) are efficient than the RSA based operations.

Table 4.3: Efficiency comparison of our scheme with related schemes

Scheme | #Cycles | Blank Ballot | Vote Ballot | Cryptographic | Security
---|---|---|---|---|---
|  | Size (in Bytes) | size (in Bytes) | primitives | Assumption
[119] | 20,940,500 | 128B | 202B | Short signature | GDHP
|  |  |  | Blind signature | DDHP
[177] | 173,340,000 | 1152B | 2098B | HE∗ | DDHP
|  |  |  | ZKP# | DDHP
[23] | 364,935,431 | 1152B | 2304B | Digital signature | IFPa
|  |  |  | Blind signature | IFP
[33] | 211,053,653 | 768B | 1930B | Digital signature | IFP
|  |  |  | Blind signature | IFP
[109] | 77,745,803 | 1152B | 1152B | Digital signature | IFP
|  |  |  | Blind signature | IFP
[169] | 160,015,290 | 188B | 296B | Digital signature | IFP
|  |  |  | Mix Net | DLP@
Our | 9,620,000 | 96B | 212B | Short signature | GDHP
|  |  |  | IDBS | ECDLP

ainteger factorization problem, @discrete logarithm problem, #Zero Knowledge
proof, ∗Homomorphic Encryption

Table 4.2 shows that our proposed system needs 16*#Sm + 2*#Bp + 2*#MTP = 9,620
Kcycles, whereas the schemes [119], [177], [23], [33], [109], and [169] need
20,940, 173,340, 364,935, 211,053, 477,746, and 160,015 Kcycles, respectively.
The computation cost of our system is much better, i.e., it takes 46%, 5%, 2%,
4%, 2% and 6% of the computation costs of the schemes [119], [177], [23],
[33], [109], and [169], respectively, shown in Figure (4.1). For a blank
ballot, our system needs 3*32 = 96 bytes, whereas the schemes [119], [177],
[23], [33], [109], and [169] need 128, 1152, 1152, 768, 1152, and 188 bytes,
respectively. For a voting ballot, our system needs 4*32+1*64 + (80)/8 +(80)/8
=212 bytes, whereas the schemes [119], [177], [23], [33], [109], and [169]
need 202, 2098, 2304, 1930, 1152, and 296 bytes, respectively. From Figure
(4.2), we observe that the ballot bandwidth in our scheme is much better,
i.e., it takes 75%, 8%, 8%, 12%, 8% and 51% of ballot bandwidth size of the
schemes [119], [177], [23], [33], [109], and [169] respectively, and the vote-
ballot bandwidth in our scheme is 105%, 10%, 9%, 10%, 18% and 68% of the vote-
ballot bandwidth of schemes [119], [177], [23], [33], [109], and [169],
respectively.

Figure 4.1: Computation costs of proposed E2E-VIV and other systems Figure
4.2: Ballot and vote-ballot size of proposed E2E-VIV and other systems

Now, we compared our E2E-VIV system with related voting systems, such as
[119], [177], [23], [113] [33], [109], and [169], in terms of following
parameters, where $C_{1}$: voter’s anonymity, $C_{2}$: resilient to coercion
and bribery, $C_{3}$: Eligibility, $C_{4}$: Integrity, $C_{5}$: Fairness,
$C_{6}$: Mobility, $C_{7}$: Efficiency, $C_{8}$: Uniqueness, $C_{9}$:
Accuracy, $C_{10}$: Convenience, $C_{11}$: Verifiability, $C_{12}$: early
voting, $C_{13}$: Batch verifiability, $C_{14}$: E2E-VIV, as summarized in
Table 4.3. As evident from this table, our E2E-VIV system provides all
security features, but no existing scheme satisfies all of them. Thus, the
E2E-VIV system is suitable for implementing a voting system in an internet
environment with E2E verifiable feature, shown in Table in 4.4.

Table 4.4: Security features of our System and existing Schemes Scheme | $C_{1}$ | $C_{2}$ | $C_{3}$ | $C_{4}$ | $C_{5}$ | $C_{6}$ | $C_{7}$ | $C_{8}$ | $C_{9}$ | $C_{10}$ | $C_{11}$ | $C_{12}$ | $C_{13}$ | $C_{14}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
[119] | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\times$ | Avg | $\checkmark$ | $\checkmark$ | Avg | $\checkmark$ | $\times$ | $\times$ | $\times$
[177] | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | – | $\checkmark$ | Avg | $\checkmark$ | $\checkmark$ | Avg | $\checkmark$ | $\times$ | $\times$ | $\checkmark$
[23] | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | Avg | $\checkmark$ | $\checkmark$ | high | $\checkmark$ | $\times$ | $\times$ | $\times$
[113] | $\checkmark$ | – | $\checkmark$ | $\checkmark$ | – | $\checkmark$ | High | $\checkmark$ | $\checkmark$ | High | $\checkmark$ | $\times$ | $\times$ | $\times$
[33] | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | Low | $\checkmark$ | $\checkmark$ | High | $\checkmark$ | $\times$ | $\times$ | $\times$
[109] | $\times$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | Low | – | $\checkmark$ | Avg | $\checkmark$ | $\times$ | $\times$ | $\times$
[169] | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | Avg | $\checkmark$ | $\checkmark$ | Avg | $\checkmark$ | $\times$ | $\times$ | $\times$
Our | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | High | $\checkmark$ | $\checkmark$ | High | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$

####  4.6.3 Batch Verification

This section illustrates the performance of systems, in terms of computation
cost on verifying the blank ballot and vote ballot simultaneously. For
convenience, we suppose 20 ballots as a batch. Figure (4.3) compares the
machine cycles (in KCycle) consumed for verifying the batch of 20 valid blank
ballots simultaneously, 20 valid/invalid blank ballots simultaneously and 20
valid/invalid blank ballots individually. Similarly, Figure (4.4) compares the
machine cycles (in KCycle) consumed for verifying the batch of 20 valid vote
ballots simultaneously, 20 valid/invalid vote ballots simultaneously and 20
valid/invalid vote ballots individually. Suppose ECA obtains
$BB_{i}=<s_{i},R_{i},h_{V}i>$ from $i^{th}$ voter, $1\leq i\leq n$. The ECA
verifies n valid blank ballots using Equation (4.15).

$\sum_{i=0}^{n}H_{2}(R_{i},h_{Vi})d_{E}P=\sum_{i=0}^{n}s_{i}P+\sum_{i=0}^{n}R_{i}$
(4.15)

Similarly, the ECA verifies multiple ballots using Equation (4.16).

$e(\sum_{i=0}^{n}V_{1i},d_{E}P)=e(\sum_{i=0}^{n}H_{4}(C_{name_{i}}),\sum_{i=0}^{n}V_{2i})$
(4.16)

The consistency of (4.15) is verified as follows. From RHS of (4.16),

$\displaystyle\sum_{i=0}^{n}(s_{i})P+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}(s_{1}i+s_{2}i)P+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}(s^{\prime}_{1}ia_{i}-c_{i}+s^{\prime}_{2}ib_{i}-d_{i})P+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}(d_{E}H_{2}(R_{i},h_{Vi})(e_{i}c_{i}+f_{i}d_{i})-(e_{i}c_{i}+f_{i}d_{i})r_{i}d_{E}-a_{1}a_{i}-c_{i}-a_{2}b_{i}-d_{i})P+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}d_{E}H_{2}(R_{i},h_{Vi})P-\sum_{i=0}^{n}(r_{i}(R_{E}+Q_{E}P_{0})+R_{1i}+R_{2i})+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}d_{E}H_{2}(R_{i},h_{Vi})P-\sum_{i=0}^{n}(R_{i})+\sum_{i=0}^{n}R_{i}$
$\displaystyle=\sum_{i=0}^{n}(H_{2}(R_{i},h_{Vi}))d_{E}P$

This proves the consistency of (4.15). Similarly, the consistency of (4.16) is
verified as follows. From LHS of Equation (4.16), we have

$\displaystyle e(\sum_{i=0}^{n}V_{i1},d_{E}P)$
$\displaystyle=\sum_{i=0}^{n}a_{i}H_{4}(C_{name_{i}},d_{E}P)$
$\displaystyle=e(\sum_{i=0}^{n}H_{4}(C_{name_{i}}),\sum_{i=0}^{n}a_{i}(R_{E}+Q_{E}P_{0}))$
$\displaystyle=e(\sum_{i=0}^{n}H_{4}(C_{name_{i}}),\sum_{i=0}^{n}V_{2i})$

This proves the consistency of (4.16).

Figure 4.3: Computational cost of verifying batch of blank ballots of
different size Figure 4.4: Computational cost of verifying batch of ballots of
different size

Analysis: The Equations (4.15) and (4.16) verify the multiple blank ballots
and ballots, respectively, if all blank ballots and ballots are valid, i.e.,
they individually verify Equations (4.15) and 4.16), respectively. If any
ballot is invalid or modified, the Equations (4.15) and (4.16) will not be
satisfied. For the batch of valid and invalid ballots, the proposed system
uses the divide and conquer mythology to optimize the computation cost. The
proposed system divides $n$ ballots into two $n/2$ ballots, and checks
Equations (4.15) and (4.16). If the ballots satisfy these equations, stop the
process; otherwise, the process is repeated until the size of the ballot
becomes one. Thus, the proposed system has $Olog(n)$ time complexity for the
batch of $n$ invalid and valid ballots, the complexities for n valid ballots
and single ballot are $O(1)$ and $O(n)$, respectively, as shown in Table 4.5.

Table 4.5: Batch verification analysis of blank ballots and ballots Verification | Blank ballots | Blank ballots
---|---|---
| Computation | Complexity | Computation | Complexity
| cost |  | cost |
Single | 2n*#Sm | $O(n)$ | 2n*#Bp | $O(n)$
n (valid) | 2*#Sm | $O(1)$ | 2*#Bp | $O(1)$
n (invalid &valid) | $Log(n)$ |  $2*\\#Sm$ $OLog(n)$ | $OLog(n)*2*\\#Bp$ | $OLog(n)$

###  4.7 Summary

This chapter presents two Identity-Based Blind Signature (IDBS) schemes: the
pairing-free IDBS-I and the pairing-friendly IDBS-II. Both proposed systems
are secure against the existential forgery attack under chosen message and
$ID$. An End-to-End Verifiable Internet Voting (E2E-VIV) system is also
designed in this chapter. The E2E-VIV system authenticates each voter using a
unique identifier issued by the appropriate authority and their biometric
information. The proposed IDBS-II scheme is used to issue a blank ballot to
the voter, and the BLS short signature scheme is used to protect the vote from
any modification. The proposed IDBS schemes are compared with related existing
schemes and have the least machine cycles. The security analysis shows that
the proposed schemes are secure against existential forgery attacks under
chosen message and $ID$. The E2E-VIV system provides a secure and verifiable
voting process. The use of unique identifiers and biometric information
ensures that each vote is cast by an eligible voter, and the IDBS-II scheme
ensures that each ballot is issued anonymously. The BLS short signature scheme
protects the vote from any modification.

[75mm] Reality is created by the mind, we can change our reality by changing
our minds. Plato- Greek philosopher, pedagogue and mathematician

##  Chapter 5 ID-Based Blind Signature with Message Recovery Scheme for
Privacy-Preserving in Cloud Storage

Data outsourcing, which allows users and organizations to exploit external
distributed servers such as the cloud, has become a notable breakthrough in
big data technology. In cloud-enabled systems, a cloud service provider (CSP)
manages, maintains, and makes data available to data owners over the Internet.
This enables users to store and process their data remotely, providing them
with significant benefits such as cost reduction, scalability, and
flexibility. However, data outsourcing also presents significant privacy and
security challenges. Once the data owner shifts the data to the untrusted
cloud, they lose direct control over the data, and the data becomes
susceptible to alteration by the CSP or any outsider attacker.

One of the primary concerns of data owners is the privacy of their stored
data. The CSP may have access to the data, and they may not have adequate
security measures in place to protect the data from unauthorized access. This
could lead to data breaches, data theft, and unauthorized access, which can
have severe consequences for the data owner. Moreover, the CSP or any outsider
attacker could also alter the data, leading to various security breaches such
as data tampering, data loss, and data corruption. These attacks could be
challenging to detect, and the data owner may not be aware of the alterations
until it is too late. Therefore, data owners need to take appropriate measures
to ensure the privacy and security of their data when outsourcing it to the
cloud. They can use various security mechanisms such as encryption, access
control, and secure communication protocols to protect their data from
unauthorized access and alteration. Additionally, regular security audits and
risk assessments can help identify potential vulnerabilities and threats,
enabling data owners to take proactive measures to mitigate the risks.

In this chapter, we propose an identity-based blind signature with a message
recovery (IDBS-MR) scheme, which is secured against existential forgery
attacks under the adaptive chosen message and ID attacks (EF-ID-CMA) and ECDL
problems. Further, we present a privacy-preserving data outsourcing mechanism
that audits the integrity of stored data for resource-limited devices in cloud
computing using the proposed IDBS-MR scheme. In the proposed privacy-
preserving scheme, the data owner verifies the blinded signature received from
the TPA and the TPA audits data integrity stored on the cloud. The performance
analysis shows that our scheme is efficient as compared to related existing
schemes.

In the last decades, there have been discussed various primitives to achieve
integrity auditing for outsourced data on the cloud—we categorise such
primitives into three distinct verification approaches. The first approach is
to authenticate the data structure; generally, Merkel hash tree (MHT), to
achieve secure search results [11]. The basic idea is to produce an index for
data files based on MHT, and the integrity of results can be achieved by re-
generating the signature on the root of MHT. Unfortunately, it is expensive in
terms of computation and communication. Besides, they do not ensure the
consistency of the results. Another approach is the probabilistic integrity
auditing approach that allows the user to insert some bogus block in the cloud
[165]. The disadvantage of such methods as they do not support common database
operations, e.g., projection. The last approach is to use of signature-
verification method [135, 131] that saves computation costs during integrity
auditing.

In 2004, Deswarte et al. [38] discussed the concept of integrity auditing and
gave the first integrity auditing scheme based on RSA. However, efficiency was
an issue that is addressed by Filho et al. [59], followed by they gave an
improved integrity auditing scheme. Yamamoto et al. [173] utilized homomorphic
hash function and batch processing in order to audit multiple data blocks.
Ateniese et al. [4], in 2007, presented a provable data possession (PDP)
scheme that enables a user to verify whether the server possesses data. In the
same year, Juels et al. [80] extended the PDP scheme and presented a proof of
retrievability (POR) scheme that ensures the user checks for stored data
possession and retrievability in the remote server. Although both schemes [4,
80] have high computation costs on the user side, they are not suitable for
implementing secure cloud storage. For cloud storage, Wang et al. [165]
discussed an integrity auditing scheme by employing a third-party auditor
(TPA), in which the auditing process is delegated to the TPA.

In the schemes mentioned earlier, the user generates the signature for the
data, and TPA audits the data integrity, which can be optimized for the user
with a resource-limited device. Recently, Liu et al. [116] addressed this
issue and presented a privacy-preserving integrity auditing for lightweight
devices using a blind signature scheme. We found that such schemes have
expensive operations, such as bilinear pairing on the TPA side. Besides, they
need certificate maintenance costs since they are based on traditional public
key infrastructure (PKI). Using the IBC technique, Zhang et al. [183] were the
first to propose the IDBS schemes. Later, many IDBS schemes have been
presented, such as [58, 102, 70, 57, 66, 100, 41, 71, 124, 157, 103]. In 2007,
Han et al. [65] presented an identity-based blind signature with a message
recovery scheme. However, this scheme [65] is implemented using pairing on
elliptic curves. Since then, very few IDBS-MR schemes have been offered, given
in the literature [65, 45, 72, 73, 39]. Recently, Verma et al. [163] present a
new IDBS-MR scheme using pairing whose security is based on the assumption of
ROM and the solving k-CAA problem.

From the above-discussed schemes, it has been noticed that the existing IDBS-
MR schemes are designed on pairing on elliptic curves. Hence, due to the high
computation cost of the pairing operation, they could not be suitable for the
cloud-storage data. Here, we present a new identity-based blind signature
scheme with message recovery without bilinear pairing. We first discuss the
system architecture followed by its implementation.

###  5.1 System Model

Here, we discuss the system architecture of privacy-preserving with integrity
auditing for cloud storage.

####  5.1.1 Network Architecture

The network architecture for privacy-preserving data outsourcing with
integrity consists of four entities: private key generator (PKG), third-party
auditor (TPA), user, and cloud, as shown in Figure (5.1).

Figure 5.1: Architecture of proposed Privacy-preserving data outsourcing with
integrity auditing

  1. 1.

Third party Auditor: TPA is a semi-trusted third-party auditor, which can
generate a signature on blinded data blocks requested by the user and can
audit the stored cloud data on behalf of the user.

  2. 2.

Private key generator: PKG generates a private key corresponding to the TPA’s
identity and issues it to TPA.

  3. 3.

Cloud: Several distributed servers combine to form an untrusted cloud, which
is managed and maintained by CSP. CSP may reject the request made by the user
or provide an incomplete query to the user in order to save cloud computation
and storage. Moreover, the cloud generates storage proof against the audit
challenge challenged by the TPA.

  4. 4.

User: The users are the data owners having resource-constrained devices, for
example, smartphones and tablets. In comparing with TPA and CSP, the user has
lower storage and computation power. The user wants to use cloud services in a
pay-per-use manner.

####  5.1.2 Design Goals

Here, we give the design goals that must achieve the following security
requirements in order to enable the privacy-preserving with integrity auditing
for cloud data storage:

  * •

Signature delegation and verification. The user delegates the signing process
to TPA since the user has a resource-limited device.

  * •

Integrity auditing. It allows TPA to validate the consistency of stored data
on the cloud on-demand without knowing any information about the original
message.

  * •

Privacy-preserving. It ensures that no entity can drive users’ data stored on
the cloud from the information collected during integrity auditing.

  * •

Batch verification. Since the data file is divided into many blocks, which are
signed by TPA, it is costly on the user side to verify each signature
individually. It enables the user to verify multiple signatures
simultaneously.

  * •

Lightweight. It ensures that the signature verification on the user side and
integrity auditing on the TPA side should be performed with minimum
communication as well as computation cost.

####  5.1.3 Identity-based Blind Signature with Message Recovery

This section gives a brief introduction to identity-based blind signature with
message recovery that helps in signature delegation without leaking any
content to TSP.

######  Definition 5.1.

(Identity-Based Blind Signature with data recovery scheme). The IDBS-MR scheme
involves four entities: signer, user, verifier and private key generator
(PKG). In the proposed scheme, the signer acts as a TPA, the user is a data
owner and PKG generates the private key for TPA. It consists of four
randomized probabilistic polynomial-time (PPT) algorithms: setup, extract,
blind signature, and verification, as discussed below.

  * •

Setup: Using security parameters, the PKG computes the master key and public
parameters. PKG keeps the master key and publishes public parameters.

  * •

Extract: For a given signer’s identity, the PKG computes the private key using
its master key and public parameter.

  * •

Blind signature: The signer and user perform the following steps to sign on a
given message.

    * –

Commitment: For the secret number, the signer computes public parameters,
passes them to the user and keeps the secret number to him.

    * –

Blinding: On a given public parameter and message M, the user blinds the
message using random secret numbers. The user then requests the signer for the
signature on the blinded message.

    * –

Signature: For each blinded message, the signer computes the blind signature
using his private key and outputs it to the user.

    * –

Unblinding: The user retrieves the blinded signature using his secret key and
outputs the original signature.

  * •

Verification: On a given blind signature, Verifier recovers the message and
then verifies the signature.

####  5.1.4 Security Threat

To discuss the security of our proposed IDBS-MR schemes, we go through the
definition of Zhang et al.’s identity-based blind signature scheme [10] and
Tso et al.’s identity-based signature with message recovery scheme [39] where
they discussed the unlinkability and unforgeability. Thus, the proposed IDBS-
MR scheme is considered to be secure if it is secured against existential
forgeable attack under the chosen message and ID attack (EF-ID-CMA) and
achieves the blindness property.

######  Definition 5.2.

Definition 5.2. (EF-ID-CMA). We discuss the unforgeability of our proposed
IDBS-MR scheme through the following game playing between a forger $F$ that
acts as a malicious user and challenger $Ch$ that acts as the honest signer
under adaptive chosen message and identity attack in the random oracle model
(ROM).

Setup: The challenger $Ch$ runs the setup algorithm and computes the master
key and public parameters. The $Ch$ responds public parameter to $F$.

Oracle: $F$ performs the following oracles. Extract oracle: For given $ID$,
forger $F$ requests to run the extract algorithm. The $Ch$ runs this oracle to
compute the private key corresponding to an identity $ID_{i}$, where $1\leq
i\leq q_{k}$ and sends it to $F$. Besides, $Ch$ saves the record in list
$L_{ext}$, which is initially empty. Blind signature oracle: For a message
$M_{i}\in\\{0,1\\}^{l2}$ of its choice in an adaptive manner, forger $F$ asks
blind signature oracle to obtain the blind signature $\sigma$. The $Ch$
executes the Blind signature oracle and responds to the result to $F$ and
saves it in the list $L_{BS}$, which is initially empty.

Forgery: At the end, the forger $F$ responds a signature $\sigma^{*}$ on given
message $M^{*}$ with signer’s identity $ID^{*}$. The forger $F$ will win the
game if it fulfils the following conditions.

  * •

$\sigma^{*}$ is the valid signature against $M^{*}$ and $ID^{*}$.

  * •

The blind signature oracle has not been queried on $<M^{*}>$.

  * •

The extract oracle has not been queried on $ID^{*}$.

Under chosen message and identity attacks, the proposed IDBS-MR scheme is said
to be existentially unforgeable, if any forger $F$ has a negligible
probability to succeed in the above game.

######  Definition 5.3.

Blindness. The blindness security notion can be defined by the adversary $Adv$
that acts as a malicious signer and is engaged with two users $U_{0}$ and
$U_{1}$ in the following game:

Setup: It computes the master key and public parameters and responds to public
parameters to $Adv$. For given $ID$, forger $Adv$ requests to run the extract
algorithm. This oracle gives the private key corresponding to an identity
$ID_{i}$, where $1\leq i\leq q_{k}$ and sends it to $Adv$. For selective
$b\in\\{0,1\\}$, the $U_{0}$ and $U_{1}$ get two distinct message $M_{b}$ and
$M_{1-b}$, respectively.

$U_{0}$ and $U_{1}$ compute $\sigma_{b}$ (signature on $M_{b}$) and
$\sigma_{1-b}$ (signature on $M_{1-b}$), respectively, and give it to $Adv$.

At the end, $Adv$ predicts a bit $b^{\prime}\in\\{0,1\\}$ and wins the game if
$b=b^{\prime}$ holds with advantage $|Pr[b=b^{\prime}]|\geq 1/2+k^{-n}$. The
proposed IDBS-MR scheme is blind if $Adv$ wins the above game with a
negligible advantage.

###  5.2 Proposed ID-Based Blind Signature Scheme with Message Recovery

This section discusses the implementation of the IDBS-MR scheme, which
consists of four PPT algorithms: Setup, Key Generation, Blind signature, and
Verification, as defined below.

Figure 5.2: Flow process of proposed privacy-preserving with integrity
auditing

  1. 1.

Setup: Given a security parameter $k$, the PKG assumes an additive group
$\mathbb{G}_{1}$ of order $q$, where $q$ is large prime number of $k$-bit and
$P$ be its generator. Suppose three hash functions
$H_{1}:\\{0,1\\}^{*}\times\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$,
$H_{2}:\mathbb{G}_{1}\rightarrow\mathbb{Z}_{q}$ and
$H_{3}:\mathbb{G}_{1}\rightarrow\\{0,1\\}^{|q|}$ and two functions
$F_{1}:\\{0,1\\}^{l_{2}}\rightarrow\\{0,1\\}^{l_{1}}$ and
$F_{2}:\\{0,1\\}^{l_{1}}\rightarrow\\{0,1\\}^{l2}$, where $l1$ and $l2$ are
two positive integers such that $l_{1}+l_{2}=|q|$. Suppose $absc(P)$ gives the
$x$-coordinate of point $P$. The PKG chooses a random element
$s_{0}\in\mathbb{Z}_{q}$ (its master key) and computes the public key
$P_{0}=s_{0}P$. The PKG publishes the public parameter
$pp=<\mathbb{G}_{1},q,P,P_{0},H_{1},H_{2},F_{1},F_{2},l_{1},l_{2},k>$, and
keeps $s_{0}$ secret.

  2. 2.

Key Generation: For given signer’s identity $ID_{S}$, $pp$ and its master key
$s_{0}$, PKG chooses a random number $a\in\mathbb{Z}_{q}$, computes the
signer’s private key $d_{IDS}=a+s_{0}Q_{IDs}$, where $Q_{IDs}=H_{1}(A,ID_{S})$
and $A=aP$ and gives $<A,d_{IDS}>$ to the signer.

  3. 3.

Blind signature: The signer and user perform the following steps to obtain a
blind signature on the message.

     * •

Commitment: The signer selects two random elements
$n_{1},n_{2}\in\mathbb{Z}_{q}$, computes $Q_{1}=n_{1}P$ and $Q_{2}=n_{2}P$,
and sends them with its public parameter $A$ to the user.

     * •

Blinding: For the given received parameters $<Q_{1},Q_{2},A>$ and message
$m\in\\{0,1\\}^{l2}$, the user selects six elements
$g,h,i,j,k,l\in\mathbb{Z}_{q}$, such that $gcd(i,j)=1$ and $ki+lj=gcd(i,j)$.
We use the extended Euclidean algorithm to select elements $k$ and $l$. The
user then computes the parameters $b_{M1}$ and $b_{M2}$ given in (5.1)-(5.7)
and asks the signer for a signature on $<b_{M1},b_{M2}>$.

$R_{1}=gQ_{1}+iP\hskip 14.22636ptand\hskip 14.22636ptr_{1}=absc(R_{1})$ (5.1)

$R_{2}=hQ_{2}+jP\hskip 14.22636ptand\hskip 14.22636ptr_{2}=absc(R_{2})$ (5.2)

$r=r_{1}r_{2}$ (5.3)

$u=F_{1}(m)||F_{2}(F_{1}(m))\oplus m$ (5.4)

$R=R_{1}+R_{2}+ru(A+Q_{ID}P_{0})$ (5.5)

$b_{M1}=kg^{-1}i(H_{2}(R)-ru)modq$ (5.6)

$b_{M2}=lh^{-1}j(H_{2}(R)-ru)modq$ (5.7)

     * •

Signature: On received parameters $<b_{M1},b_{M2}>$ and its private key
$d_{IDS}$, signer computes the blind signature
$<s^{\prime}_{1},s^{\prime}_{2}>$, where
$s^{\prime}_{1}=(d_{IDS}b_{M}1-n_{1})$ and
$s^{\prime}_{2}=(d_{IDS}b_{M2}-n_{2})$, and sends
$<s^{\prime}_{1},s^{\prime}_{2}>$ to the user.

     * •

Unblinding: On received parameters $<s^{\prime}_{1},s^{\prime}_{2}>$, user
sets $s_{1}=(s^{\prime}_{1}g-i)$ and $s_{2}=(s^{\prime}_{2}h-j)$ and computes
the original signature $<v,R>$, where $s=(s_{1}+s_{2})$ and $v=u\oplus