# Electronic Voting Protocol Using Identity-Based Cryptography

Authors: Gina Gallegos-Garcia; Horacio Tapia-Recillas
Journal: The Scientific World Journal
 (2015)

---

## Abstract

Electronic voting protocols proposed to date meet their properties based on Public Key Cryptography (PKC), which offers high flexibility through key agreement protocols and authentication mechanisms. However, when PKC is used, it is necessary to implement Certification Authority (CA) to provide certificates which bind public keys to entities and enable verification of such public key bindings. Consequently, the components of the protocol increase notably. An alternative is to use Identity-Based Encryption (IBE). With this kind of cryptography, it is possible to have all the benefits offered by PKC, without neither the need of certificates nor all the core components of a Public Key Infrastructure (PKI). Considering the aforementioned, in this paper we propose an electronic voting protocol, which meets the privacy and robustness properties by using bilinear maps.


---

## Body

## 1. Introduction

Since 1964, considerable efforts have been made to improve the efficiency of election processes that has brought, as a consequence, a wide range of proposals on such topic.Electronic voting has been mentioned in different media as the use of computers or computerized voting equipment to cast ballots in an election, which nowadays are a reasonable alternative to conventional elections and other opinion expressing processes [1–5]. Roughly speaking an electronic voting protocol, used to develop an electronic voting process, involves three main entities: voters, registration authorities, and counting authorities who interact with each other during four main phases: registration, authentication, voting, and counting [6, 7], from which authentication is out of our scope.In order to use an electronic voting protocol inside an electronic voting process, it should satisfy several properties [8]. However, proposed protocol meets privacy and robustness properties by using bilinear maps.(i)
Privacy: a vote must be kept secret from any coalition of authorities.(ii)
Robustness: the protocol can be developed even if there are entities who do not give correct information. In other words, this property is against dishonest users.In this paper a voting protocol based on bilinear maps [9, 10] satisfying privacy, uncoercibility, and robustness is proposed. The paper is organized as follows: in Section 2 some intractable problems on finite groups are recalled. The security of the proposed protocol is based on these intractable problems. In Section 3 the proposed protocol is presented. An analysis of privacy and robustness properties is given in Section 4. Obtained results are showed in Section 5. Section 6 presents concluding remarks and final references are listed.


## 2. Preliminaries

Let(G1,+) be a cyclic group of order m written additively. With such a group G1, the following hard cryptographic problems are defined:(i)
Discrete Logarithm Problem (DLP): givenP,P′∈G1, find an integer n such that P=nP′ whenever such integer exists.(ii)
Computational Diffie-Hellman Problem (CDHP): given a tripleP,aP,bP∈G1 for a,b∈Zm, find the element (ab)P.(iii)
Decision Diffie-Hellman Problem (DDHP): given a quadrupleP,aP,bP,cP∈G1 for a,b,c∈Zm, decide whether c≡ab(modm) or not.We assume throughout the paper that DLP and CDHP are intractable, which means that there does not exist a Polynomial Time Algorithm to solve them with nonnegligible probability. When the DDHP is easy but the CDHP is hard on the groupG1,G1 is called a Gap Diffie-Hellman (GDH) group. Such a group can be found on supersingular elliptic curves or hyperelliptic curves over finite fields [11, 12]. The proposed electronic voting protocol can be built on any GDH group.


## 3. The Proposed Electronic Voting Protocol

The protocol is divided into three phases: setup, voting, and counting. In the setup stage the key pairs to be used during the voting and counting phases are generated. The generation of these key pairs involves the participation ofn entities Ei, where 1≤i≤n [12–14]. Each entity broadcasts and receives specific information by using Shamir’s secret-sharing scheme in order to generate its public and private shares [15]. In the voting phase voters encrypt votes and ask a blind signature [13, 14]. In the counting phase, a Combining Entity reconstructs the signatures of the votes and verifies and decrypts them [13, 14, 16, 17].The Combining Entity, who does not have any private key, decrypts the votes by combining decryption shares, which are generated by each entityEi, after which the votes are counted and the tally is published.The three phases are detailed as follows.


### 3.1. Setup Phase

(1)
Let(G1,+) and (G2,∗) be cyclic groups of the same order q which is assumed to be a prime number, with G1=P1, and let e^:G1×G1→G2 be a nondegenerated bilinear mapping. Let H1:{0,1}∗→G1 and H2:G2→{0,1}n be two hash functions. This information is known to all entities Ei,i=1,2,…,n, where n≤q-1. Furthermore, each entity Ei chooses a binary string, an element of {0,1}k, corresponding to information identifying this entity, for example, an e-mail address, an IP address, and telephone number. The entity Ei sends information to each Ej to generate the public encryption key Ppub and its respective private decryption key d as follows:
(a)
EntityEi randomly selects ai0∈Zq∗, keeps it in secret, and broadcasts ai0P1.
(b)
EntityEi randomly picks up a polynomial fix=ai0+ai1x+⋯+ait-1xt-1∈Zq[x] of degree ≤t-1 such that fi(0)=ai0. The integer t is taken sufficiently large.
(c)
E
i computes and broadcasts aijP1 for j=1,2,…,t-1 and sends fi(j) to each Ej for j=1,2,…,n, where j≠i.
(2)
AfterEi receives fj(i) from entity Ej,j=1,2,…,n,  j≠i, it does the following:
(a)
E
i verifies fj(i)P1 by checking that fj(i)P1=(∑k=0t-1ikajk)P1, for each j=1,2,…,n,  j≠i. If the check fails, Ei broadcasts a complaint against Ej.
(b)
It computes its private sharedi=∑k=1nfk(i) and keeps it in secret. This di may be considered as an element of Zq.
EachEi calculates its public share Ppubi=diP1∈G1 and computes the public encryption key Ppub=∑i=1nai0P1∈G1.
(3)
With the above calculations, the public key isPpub=dP1 and its respective private key, that is distributed to every entity Ei, is d=∑i=1nai0.
(4)
LetID be the binary sequence identifying the receiver, also called Combining Entity, and let PpubID=H1(ID)∈G1; all entities Ei compute their private encryption private share dIDi=ai0PpubID.
(5)
In order to generate the signature and verification key pair, each entityEi sends the following information to each Ej. This is done by using the same (additive) group G1=P1 as follows:
(a)
EntityEi randomly selects bi0∈Zq∗, keeps it in secret, and broadcasts bi0P1.
(b)
It picks up randomly a polynomialgix=bi0+bi1x+⋯+bit-1xt-1∈Zq[x] of degree ≤t-1 such that gi(0)=bi0. Note that the polynomials fi(x),gi(x), despite having the same degree, are different.
(c)
It computes and broadcastsbijP1 and sends gi(j) to each Ej for j=1,2,…,n, j≠i.
(6)
AfterEi receives gj(i) from entity Ej,j=1,2,…,n, j≠i, it does the following:
(a)
E
i verifies gj(i)P1 by checking that gj(i)P1=(∑k=0t-1ikbjk)P1. If the check fails, Ei broadcasts a complaint against Ej.
(b)
It computes its private sharesi=∑k=1ngk(i) and keeps it in secret. The element si can be regarded as an element of Zq.
(c)
Then, eachEj calculates its public share Qi=siP1 and computes the public verification key Q=(∑i=1nbi0)P1.
(7)
With the above calculations, the public key isQ=(∑i=1nbi0)P1; it means that Q=sP1 and its respective private key that is distributed to every entity Ei is s=∑i=1nbi0.


### 3.2. Voting Phase

(1)
Lete^:G1×G1→G2 be the bilinear pairing mentioned above. To encrypt a vote as a message, the voter chooses an option v and selects 0≠r∈Zq. Then, it codifies v as an element of {0,1}n. After that, the voter selects any PpubID and computes one scalar multiplication and one bilinear pairing obtaining the encrypted vote given by (U,W), where U=rP1∈G1 and W=v⊕H2(e^(Ppub,PpubID)r)∈{0,1}n.
(2)
The voter gets the blinded encrypted votev′ by choosing randomly 0≠b∈Zq and calculating v′=b(U+H1(W)). After that, v′ is sent to each entity Ei in order to ask for an i-shadow-blind signature to each entity Ei, with 1≤i≤n.
(3)
Each entityEi computes σi′=siv′ and sends it back to the voter. Since v′∈G1, σi′∈G1 as well.
(4)
The voter calculates thei-shadow-signature of each entity Ei by computing σi=b-1σi′=si(U+H1(W)). Since σi′ is an element of G1 so is σi.
(5)
Considering a storage device, the vote(U,W) and thei-shadow-signatures are stored as (U,Wσ1⋯σn), where σi is computed as in the previous step.


### 3.3. Counting Phase

(1)
To rebuild and verify the signature of each vote, the independent Combining Entity proceeds as follows:
(a)
It selects a subsetS⊆{σ1,σ2,…,σn} of t shadow-signatures, that is, |S|=t, and computes σ=∑i∈SLiσi, where Li denotes the Lagrange coefficient associated with the polynomial gi(x) given by Lj=∏j∈S,j≠i-j/(i-j) ([17]). Observe that in particular ∑i∈SsiLi=s.
(b)
It verifies the signature by checking thate^(σ,P1)=e^(U+H1(W),Q).
(2)
To decrypt the votes, the procedure is as follows:
(a)
Each entityEi calculates its decryption share e^(U,dIDi) for every vote cast and sends to the Combining Entity, who selects a set T⊆{e^(U,dID1),e^(U,dID2),…,e^(U,dIDn)} of t decryption shares and computes g=∏i∈Te^(U,dIDi)Ii, where Ii denotes the Lagrange coefficient associated with the polynomial fi(x) given by Ij=∏j∈S,j≠i-j/(i-j) ([17]).
(3)
Onceg is determined, the vote is decrypted by computing v=W⊕H2(g).
(4)
The votes are counted and the tally is published. The voter can check if its vote was counted by comparing its receipt with the announced results.


## 3.1. Setup Phase

(1)
Let(G1,+) and (G2,∗) be cyclic groups of the same order q which is assumed to be a prime number, with G1=P1, and let e^:G1×G1→G2 be a nondegenerated bilinear mapping. Let H1:{0,1}∗→G1 and H2:G2→{0,1}n be two hash functions. This information is known to all entities Ei,i=1,2,…,n, where n≤q-1. Furthermore, each entity Ei chooses a binary string, an element of {0,1}k, corresponding to information identifying this entity, for example, an e-mail address, an IP address, and telephone number. The entity Ei sends information to each Ej to generate the public encryption key Ppub and its respective private decryption key d as follows:
(a)
EntityEi randomly selects ai0∈Zq∗, keeps it in secret, and broadcasts ai0P1.
(b)
EntityEi randomly picks up a polynomial fix=ai0+ai1x+⋯+ait-1xt-1∈Zq[x] of degree ≤t-1 such that fi(0)=ai0. The integer t is taken sufficiently large.
(c)
E
i computes and broadcasts aijP1 for j=1,2,…,t-1 and sends fi(j) to each Ej for j=1,2,…,n, where j≠i.
(2)
AfterEi receives fj(i) from entity Ej,j=1,2,…,n,  j≠i, it does the following:
(a)
E
i verifies fj(i)P1 by checking that fj(i)P1=(∑k=0t-1ikajk)P1, for each j=1,2,…,n,  j≠i. If the check fails, Ei broadcasts a complaint against Ej.
(b)
It computes its private sharedi=∑k=1nfk(i) and keeps it in secret. This di may be considered as an element of Zq.
EachEi calculates its public share Ppubi=diP1∈G1 and computes the public encryption key Ppub=∑i=1nai0P1∈G1.
(3)
With the above calculations, the public key isPpub=dP1 and its respective private key, that is distributed to every entity Ei, is d=∑i=1nai0.
(4)
LetID be the binary sequence identifying the receiver, also called Combining Entity, and let PpubID=H1(ID)∈G1; all entities Ei compute their private encryption private share dIDi=ai0PpubID.
(5)
In order to generate the signature and verification key pair, each entityEi sends the following information to each Ej. This is done by using the same (additive) group G1=P1 as follows:
(a)
EntityEi randomly selects bi0∈Zq∗, keeps it in secret, and broadcasts bi0P1.
(b)
It picks up randomly a polynomialgix=bi0+bi1x+⋯+bit-1xt-1∈Zq[x] of degree ≤t-1 such that gi(0)=bi0. Note that the polynomials fi(x),gi(x), despite having the same degree, are different.
(c)
It computes and broadcastsbijP1 and sends gi(j) to each Ej for j=1,2,…,n, j≠i.
(6)
AfterEi receives gj(i) from entity Ej,j=1,2,…,n, j≠i, it does the following:
(a)
E
i verifies gj(i)P1 by checking that gj(i)P1=(∑k=0t-1ikbjk)P1. If the check fails, Ei broadcasts a complaint against Ej.
(b)
It computes its private sharesi=∑k=1ngk(i) and keeps it in secret. The element si can be regarded as an element of Zq.
(c)
Then, eachEj calculates its public share Qi=siP1 and computes the public verification key Q=(∑i=1nbi0)P1.
(7)
With the above calculations, the public key isQ=(∑i=1nbi0)P1; it means that Q=sP1 and its respective private key that is distributed to every entity Ei is s=∑i=1nbi0.


## 3.2. Voting Phase

(1)
Lete^:G1×G1→G2 be the bilinear pairing mentioned above. To encrypt a vote as a message, the voter chooses an option v and selects 0≠r∈Zq. Then, it codifies v as an element of {0,1}n. After that, the voter selects any PpubID and computes one scalar multiplication and one bilinear pairing obtaining the encrypted vote given by (U,W), where U=rP1∈G1 and W=v⊕H2(e^(Ppub,PpubID)r)∈{0,1}n.
(2)
The voter gets the blinded encrypted votev′ by choosing randomly 0≠b∈Zq and calculating v′=b(U+H1(W)). After that, v′ is sent to each entity Ei in order to ask for an i-shadow-blind signature to each entity Ei, with 1≤i≤n.
(3)
Each entityEi computes σi′=siv′ and sends it back to the voter. Since v′∈G1, σi′∈G1 as well.
(4)
The voter calculates thei-shadow-signature of each entity Ei by computing σi=b-1σi′=si(U+H1(W)). Since σi′ is an element of G1 so is σi.
(5)
Considering a storage device, the vote(U,W) and thei-shadow-signatures are stored as (U,Wσ1⋯σn), where σi is computed as in the previous step.


## 3.3. Counting Phase

(1)
To rebuild and verify the signature of each vote, the independent Combining Entity proceeds as follows:
(a)
It selects a subsetS⊆{σ1,σ2,…,σn} of t shadow-signatures, that is, |S|=t, and computes σ=∑i∈SLiσi, where Li denotes the Lagrange coefficient associated with the polynomial gi(x) given by Lj=∏j∈S,j≠i-j/(i-j) ([17]). Observe that in particular ∑i∈SsiLi=s.
(b)
It verifies the signature by checking thate^(σ,P1)=e^(U+H1(W),Q).
(2)
To decrypt the votes, the procedure is as follows:
(a)
Each entityEi calculates its decryption share e^(U,dIDi) for every vote cast and sends to the Combining Entity, who selects a set T⊆{e^(U,dID1),e^(U,dID2),…,e^(U,dIDn)} of t decryption shares and computes g=∏i∈Te^(U,dIDi)Ii, where Ii denotes the Lagrange coefficient associated with the polynomial fi(x) given by Ij=∏j∈S,j≠i-j/(i-j) ([17]).
(3)
Onceg is determined, the vote is decrypted by computing v=W⊕H2(g).
(4)
The votes are counted and the tally is published. The voter can check if its vote was counted by comparing its receipt with the announced results.


## 4. Properties Analysis

### 4.1. Privacy

The proposed electronic voting protocol meets the privacy property by using a threshold encryption scheme and its respective signature version, which is probably secure under the Computational Bilinear Diffie-Hellman Problem. With this, only the Combining Entity, jointly with at leastt entities, is the only one who is able to decrypt votes and verify signatures during the counting stage. The correctness is shown as follows from the signature verification in Section 3.3:(1)e^σ,P1=e^∑i∈SLiσi,P1=∏i∈Se^σi,P1Li=∏i∈Se^b-1σi′,P1Li=∏i∈Se^b-1siv′,P1Li=∏si∈Se^siU+H1W,P1Li=∏i∈Se^U+H1W,P1siLi=e^U+H1W,∑i∈SsiLiP1=e^U+H1W,sP1=e^U+H1W,Qand from the decryption votes, also in Section 3.3:(2)g=∏i∈Te^U,dIDiIi=e^rP1,∑i∈Tai0IiPpubID=e^rP1,dPpubID=e^P1,PpubIDrd=e^dP1,PpubIDr=e^Ppub,PpubIDr.Then,(3)W⊕H2g=W⊕H2e^Ppub,PpubIDr=v.


### 4.2. Robustness

The proposed electronic voting protocol meets robustness property by using bilinear properties in such way that each entityEi has to prove, in a noninteractive way, the equality of two inverses of the isomorphism fP1=e^(P1,·) induced by the bilinear map e^.To do this, each entityEi chooses a random R∈G1 and computes w1=e^(P1,R)∈G2, w2=e^(U,R)∈G2 and a hash e of the tuple (e^(U,dIDi), e^(Ppub,PpubID),w1,w2).Then, entityEi computes V=R+edIDi∈G1 and joins the tuple (w1,w2,e,V) to its share in order that other entities Ei can check that (4)e^P1,V=e^P1,Re^Ppub,PpubIDe,e^U,V=e^U,Re^U,dIDie.Both equalities hold as we can see as follows:(5)e^P1,V=e^P1,Re^Ppubi,PpubIDe,e^P1,R+edIDi=e^P1,Re^Ppubi,PpubIDe,e^P1,Re^P1,dIDie=e^P1,Re^diP1,dIDidi-1e,e^P1,Re^P1,dIDie=e^P1,Re^P1,dIDie,e^U,V=e^U,Re^U,dIDie,e^U,R+edIDi=e^U,Re^U,dIDie,e^U,Re^U,edIDie=e^U,Re^U,dIDie,e^U,Re^U,dIDie=e^U,Re^U,dIDie.


### 4.3. Security Analysis

In the proposed protocol we assume that any attacker who wishes to break the privacy in the proposed electronic voting protocol is fully aware of the public key and any algorithms that may be used as part of the protocol. The information that is denied to the attacker is the private key for encryption during the voting phases.The nature of the relation between the public and private keys means that it is possible for any asymmetric scheme to achieve a perfect notion of security. Public keys, by definition, must contain enough information to compute their associated private key. In such case it may be theoretically possible to recover the private key from the public key; it is not computationally feasible to do so. Considering that and that we cannot derive definite mathematical statements about the security of the protocol, we do prove that a reduction exists between the difficulty of breaking the protocol and the difficulty of solving a well-studied mathematical problem.The reductionist approach is used to prove the security in our protocol relying on assumptions about the hardness of some mathematical problems. All of this is made in order to prove its security. We give some definitions as follows.Definition 1.
Given two groupsG1 and G2 of the same prime order q, a bilinear map e^:G1×G1→G2, and a generator g of G1, the Decisional Bilinear Diffie-Hellman Problem (DBDHP) in (G1,G2,e^) is to decide whether h=e^(g,g)abc given g,ga,gb,gc∈G14 and an element h∈G2.Definition 2.
Given two groupsG1 and G2 of the same prime order q, a bilinear map e^:G1×G1→G2, and a generator g of G1, the Computational Bilinear Diffie-Hellman Problem (CBDHP) in (G1,G2,e^) is to compute h=e^(g,g)abc given g,ga,gb,gc∈G14.In other words, security of proposed protocol is based on hardness assumptions for problems in groups equipped with a pairing. The advantage of solving such assumptions is given as follows.Definition 3.
The advantage of an algorithmA in solving the Bilinear Diffie-Hellman Problem (BDHP) in (G1,G2) is(6)AdvABDHPk=Pr⁡Ag,ga,gb,gc=e^g,gabc,where a,b,c←$Zq∗ and we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the BDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the BDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Definition 4.
The advantage of an algorithmA in solving the Decisional Bilinear Diffie-Hellman Problem (DBDHP) in (G1,G2) is(7)AdvADBDHPk=Pr⁡Ag,ga,gb,gc,e^g,gabc=1-Pr⁡Ag,ga,gb,gc,Z=1,where a,b,c←$Zq∗ and Z←$G2. Moreover, we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the DBDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the DBDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Definition 5.
The advantage of an algorithmA in solving the Computational Bilinear Diffie-Hellman Problem (CBDHP) in (G1,G2) is(8)AdvACBDHPk=Pr⁡Ag,ga,gb,gc,e^g,gabc=h,where a,b,c←$Zq∗ and h=e^(g,g)abc←$G2. Moreover, we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the CBDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the CBDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Considering the aforementioned, to break our protocol from the privacy point of view, first of all, attacker must break the atomic primitives our cryptographic protocol is based on in addition to getting nonnegligible advantage in the above definitions.


## 4.1. Privacy

The proposed electronic voting protocol meets the privacy property by using a threshold encryption scheme and its respective signature version, which is probably secure under the Computational Bilinear Diffie-Hellman Problem. With this, only the Combining Entity, jointly with at leastt entities, is the only one who is able to decrypt votes and verify signatures during the counting stage. The correctness is shown as follows from the signature verification in Section 3.3:(1)e^σ,P1=e^∑i∈SLiσi,P1=∏i∈Se^σi,P1Li=∏i∈Se^b-1σi′,P1Li=∏i∈Se^b-1siv′,P1Li=∏si∈Se^siU+H1W,P1Li=∏i∈Se^U+H1W,P1siLi=e^U+H1W,∑i∈SsiLiP1=e^U+H1W,sP1=e^U+H1W,Qand from the decryption votes, also in Section 3.3:(2)g=∏i∈Te^U,dIDiIi=e^rP1,∑i∈Tai0IiPpubID=e^rP1,dPpubID=e^P1,PpubIDrd=e^dP1,PpubIDr=e^Ppub,PpubIDr.Then,(3)W⊕H2g=W⊕H2e^Ppub,PpubIDr=v.


## 4.2. Robustness

The proposed electronic voting protocol meets robustness property by using bilinear properties in such way that each entityEi has to prove, in a noninteractive way, the equality of two inverses of the isomorphism fP1=e^(P1,·) induced by the bilinear map e^.To do this, each entityEi chooses a random R∈G1 and computes w1=e^(P1,R)∈G2, w2=e^(U,R)∈G2 and a hash e of the tuple (e^(U,dIDi), e^(Ppub,PpubID),w1,w2).Then, entityEi computes V=R+edIDi∈G1 and joins the tuple (w1,w2,e,V) to its share in order that other entities Ei can check that (4)e^P1,V=e^P1,Re^Ppub,PpubIDe,e^U,V=e^U,Re^U,dIDie.Both equalities hold as we can see as follows:(5)e^P1,V=e^P1,Re^Ppubi,PpubIDe,e^P1,R+edIDi=e^P1,Re^Ppubi,PpubIDe,e^P1,Re^P1,dIDie=e^P1,Re^diP1,dIDidi-1e,e^P1,Re^P1,dIDie=e^P1,Re^P1,dIDie,e^U,V=e^U,Re^U,dIDie,e^U,R+edIDi=e^U,Re^U,dIDie,e^U,Re^U,edIDie=e^U,Re^U,dIDie,e^U,Re^U,dIDie=e^U,Re^U,dIDie.


## 4.3. Security Analysis

In the proposed protocol we assume that any attacker who wishes to break the privacy in the proposed electronic voting protocol is fully aware of the public key and any algorithms that may be used as part of the protocol. The information that is denied to the attacker is the private key for encryption during the voting phases.The nature of the relation between the public and private keys means that it is possible for any asymmetric scheme to achieve a perfect notion of security. Public keys, by definition, must contain enough information to compute their associated private key. In such case it may be theoretically possible to recover the private key from the public key; it is not computationally feasible to do so. Considering that and that we cannot derive definite mathematical statements about the security of the protocol, we do prove that a reduction exists between the difficulty of breaking the protocol and the difficulty of solving a well-studied mathematical problem.The reductionist approach is used to prove the security in our protocol relying on assumptions about the hardness of some mathematical problems. All of this is made in order to prove its security. We give some definitions as follows.Definition 1.
Given two groupsG1 and G2 of the same prime order q, a bilinear map e^:G1×G1→G2, and a generator g of G1, the Decisional Bilinear Diffie-Hellman Problem (DBDHP) in (G1,G2,e^) is to decide whether h=e^(g,g)abc given g,ga,gb,gc∈G14 and an element h∈G2.Definition 2.
Given two groupsG1 and G2 of the same prime order q, a bilinear map e^:G1×G1→G2, and a generator g of G1, the Computational Bilinear Diffie-Hellman Problem (CBDHP) in (G1,G2,e^) is to compute h=e^(g,g)abc given g,ga,gb,gc∈G14.In other words, security of proposed protocol is based on hardness assumptions for problems in groups equipped with a pairing. The advantage of solving such assumptions is given as follows.Definition 3.
The advantage of an algorithmA in solving the Bilinear Diffie-Hellman Problem (BDHP) in (G1,G2) is(6)AdvABDHPk=Pr⁡Ag,ga,gb,gc=e^g,gabc,where a,b,c←$Zq∗ and we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the BDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the BDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Definition 4.
The advantage of an algorithmA in solving the Decisional Bilinear Diffie-Hellman Problem (DBDHP) in (G1,G2) is(7)AdvADBDHPk=Pr⁡Ag,ga,gb,gc,e^g,gabc=1-Pr⁡Ag,ga,gb,gc,Z=1,where a,b,c←$Zq∗ and Z←$G2. Moreover, we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the DBDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the DBDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Definition 5.
The advantage of an algorithmA in solving the Computational Bilinear Diffie-Hellman Problem (CBDHP) in (G1,G2) is(8)AdvACBDHPk=Pr⁡Ag,ga,gb,gc,e^g,gabc=h,where a,b,c←$Zq∗ and h=e^(g,g)abc←$G2. Moreover, we assume that parameters (G1,G2,e,q,g) as output by the algorithmPairingGen on input 1k are given to A as additional inputs. We say that the CBDHP is hard in (G1,G2) if no Polynomial Time Algorithm that solves the CBDHP in (G1,G2) has a nonnegligible advantage, as a function of the security parameter k.Considering the aforementioned, to break our protocol from the privacy point of view, first of all, attacker must break the atomic primitives our cryptographic protocol is based on in addition to getting nonnegligible advantage in the above definitions.


## 5. Results

In order to get a comparison between the proposed protocol and related work, results are shown from two points of view; Table1 shows the first one, which is viewed from the total number of PKI components that the proposed protocol would use to develop a voting process. In such table PKI Component 1 and PKI Component 2 mean certification and trust authorities, respectively. Both of them are main components in a PKI. In that table it is possible to see that the number of components required increases depending on the number of voters participating in the voting protocol. Moreover, the proposed electronic voting protocol meets privacy and robustness based on Diffie-Hellman problems, which become as secure as [5] and more secure than [1–4], as [5] reports. In this sense CBDHP means Computational Bilinear Diffie-Hellman Problem.Table 1
Proposed protocol does not need any component of a PKI.
Protocol
PKI Component 1
PKI Component 2
Privacy and robustness based on
Cramer et al. [1]
0
0
DHP
Mu et al. [2]
1
∗
V
0
DHP
Ohkubo et al. [3]
1
∗
v
0
DHP
Baudron et al. [4]
1
∗
L
0
RC
Gallegos-García et al. [5]
0
1
CBDHP
Proposed protocol
0
0
CBDHPOn the other hand, the second point of view is from the computations needed to develop the proposed protocol, which depends on the number of cryptographic operations used in comparison with the proposed one. Operations considered are modular addition (+), modular multiplication (∗), exponentiation (xy), inversion (x-1), point addition (P+Q), and scalar multiplication (nP). Moreover, v means voter and parameter n represents the total number of shareholders who participate during the voting process with 1≤i≤n and t denotes the threshold that the voting protocol considers for counting stage. It is important to say that our protocol involves operations based on groups, finite fields, and field extensions, which are made by using polynomials to represent the field elements that bilinear maps use.In Table2 it is possible to see that even though the proposed protocol does not involve exponentiations and point additions, it does use several computations of bilinear maps, which involves additions and multiplications over a finite field and its extensions, a technique called tower fields. However, even though the proposed protocol has the highest computational cost, bilinear maps can be addressed by using cryptoaccelerators, which efficiently develops such kind of cryptographic operations. The inclusion of such processors is considered to be cheaper and preferred than the components of a Public Key Infrastructure.Table 2
Cryptographic operations developed in the proposed protocol.
Op.
Ohkubo et al. [3]
Cramer et al. [1]
Baudron et al. [4]
Mu et al. [2]
Gallegos-García et al. [5]
Proposed protocol
+
3
1
2
(
i
-
2
)
+
2
1
0
(
t
-
1
)
∗
2
x
16
+
(
t
-
1
)
12
+
(
i
-
1
)
L
∗
10
+
8
+
2
(
t
-
1
)
6
0
(
t
-
1
)
∗
2
x
y
13
19
+
n
+
n
∗
i
L
(
n
!
+
13
)
+
9
+
t
11
0
0
x
-
1
2
3
L
∗
2
1
1
1
P
+
Q
NA
NA
NA
NA
0
0
n
P
NA
NA
NA
NA
2
+
1
∗
v
+
3
∗
i
2
∗
(
(
4
∗
i
)
+
(
1
∗
j
)
+
(
1
∗
j
∗
t
-
1
)
+
(
1
∗
i
∗
n
)
)
+
(
1
∗
i
)
+
(
2
∗
v
)
∗
(
1
∗
v
∗
i
)
Hash
5
NA
NA
NA
(
1
∗
i
)
+
(
3
∗
v
)
(
1
∗
i
)
+
(
3
∗
v
)
e
^
0
0
0
0
(
1
∗
v
)
+
(
1
∗
i
)
+
2
(
1
∗
v
)
+
(
1
∗
i
)
+
2


## 6. Conclusion

Electronic voting protocols that include as main construction blocks blind signatures and homomorphic and secret sharing techniques have been developed in last years. In this paper we present a protocol that is based on blind signatures and secret sharing techniques, using blind signatures and encryption schemes as the main construction blocks. The main difference with protocols proposed to date is that its functionality is based on bilinear maps and secret sharing schemes, which are used jointly with their respective properties to meet expectations of privacy and robustness. Bilinear maps develop high cost operations which can be addressed by using cryptoaccelerators to efficiently develop this sort of operations. As a result, we eliminate the need of implementing a Public Key Infrastructure (PKI).In addition the proposed protocol is based on the difficulty of solving the Computational Diffie-Hellman Problem (CDHP) and the Bilinear Diffie-Hellman Problem (BDHP); due to its construction it can be found on supersingular elliptic curves or hyperelliptic curves over finite fields; as a consequence no algorithm exists as yet capable of solving such problems in polynomial time.According to what was mentioned above, it is easy to see that proposed protocol highlights the balance between security and efficiency. In other words, from the security point of view, the proposed protocol is based on the difficulty of solving the Computational Diffie-Hellman Problem (CDHP) and the Bilinear Diffie-Hellman Problem (BDHP). From the efficiency point of view, we eliminate the need of implementing the components of a Public Key Infrastructure (PKI) and leave as consideration the development of cryptographic operations by using cryptoaccelerators.The protocol presented here could be used, for instance, in a voting system based on Direct Recording Electronic (DRE) systems, which provides authentication of the voter’s identity based on official documents presented to the electoral authority.Moreover, the voter’s receipt could be used to meet requirements of verifiability and accuracy. Thus, in order to verify if the votes were recorded and counted, the receipt should appear on a bulletin board in which it is displayed together with the final tally. If any voter does not find his/her hash value on the bulletin board, he/she can register a complaint with election officials.



---

*Source: 741031-2015-05-24.xml*