Secure Electronic Voting Scheme Based on Blockchain and Short Linkable Ring Signature

doi:10.12068/j.issn.1005-3026.2024.05.002

Abstract

Abstract:

Surrounding the problems that most of the current electronic voting schemes are centralized and unable to achieve anonymous voting， a secure electronic voting scheme based on blockchain and short linkable ring signature is proposed. By designing a short linkable ring signature scheme and combining with blockchain technology， a specific， secure and efficient electronic voting scheme is constructed. The system model， the formal definition of the algorithms， and the detailed description are provided. Compared with the existing schemes， this scheme allows for large‐scale voting， and supports multiple voting options and automatic counting of votes. The security analysis and experimental results show that this scheme can meet more security goals such as anonymity， unforgeability， and privacy， while still with advantages in terms of computational overhead.

Key words: electronic voting, blockchain, short linkable ring signature, secure computation, decentralizaiton

CLC Number:

TP 309.2

Qi-yu WU, Fan YANG, Fu-cai ZHOU, Da FENG. Secure Electronic Voting Scheme Based on Blockchain and Short Linkable Ring Signature[J]. Journal of Northeastern University(Natural Science), 2024, 45(5): 619-627.

Figures/Tables 12

Fig.1 System Model

Table 1 Setup algorithm

初始化算法：

s e t u p (1 λ, t) → (P, ? T)

输入： $1 λ, t$

输出： $P, ? T$

1 Get $p p ← S L R S . s e t u p 1 λ$

2 Generate $P = p p$

3 Set $t r, ? t b, ? t e, t s, s, ? t b, s, ? t e, s, ? t d$ from $t$

4 Get $T = (t r, ? t b, ? t e, t s, s, ? t b, s, ? t e, s, ? t d)$

5 Return

P, ? T

Table 1 Setup algorithm

初始化算法：

s e t u p (1 λ, t) → (P, ? T)

输入： $1 λ, t$

输出： $P, ? T$

1 Get $p p ← S L R S . s e t u p 1 λ$

2 Generate $P = p p$

3 Set $t r, ? t b, ? t e, t s, s, ? t b, s, ? t e, s, ? t d$ from $t$

4 Get $T = (t r, ? t b, ? t e, t s, s, ? t b, s, ? t e, s, ? t d)$

5 Return

P, ? T

Table 2 Registration algorithm

注册算法：

r e g i s t e r P, T, t, I D i → k i ? o r ? ⊥

输入： $P, T, t, I D i$

输出： $k i ? o r ? ⊥$

1 If $t < t r$

2 For $i = 1$ to $i = n$ do

3 If $I D i = t r u e$

4 Get （ $k p, i, k s, i$ ） $← S L R S . k e y g e n P, I D i$

5 Get $k R p ← S L R S . k R p g e n P, U$

6 Get $k R s, i ← S L R S . k R p g e n P, U, k s, i$

7 Save $I D i, k p, i$

8 Return $k i = (k s, i, k R p, k R s, i)$

9 Else

10 Return $⊥$

11 End For

12 Else

13 Return

⊥

Table 2 Registration algorithm

注册算法：

r e g i s t e r P, T, t, I D i → k i ? o r ? ⊥

输入： $P, T, t, I D i$

输出： $k i ? o r ? ⊥$

1 If $t < t r$

2 For $i = 1$ to $i = n$ do

3 If $I D i = t r u e$

4 Get （ $k p, i, k s, i$ ） $← S L R S . k e y g e n P, I D i$

5 Get $k R p ← S L R S . k R p g e n P, U$

6 Get $k R s, i ← S L R S . k R p g e n P, U, k s, i$

7 Save $I D i, k p, i$

8 Return $k i = (k s, i, k R p, k R s, i)$

9 Else

10 Return $⊥$

11 End For

12 Else

13 Return

⊥

Table 3 Key generation algorithm

密钥生成算法： $K e y g e n e r a t i o n P, t, k s, i → s i, K P$
输入： $P, t, k s, i$
输出： $s i, K P$
1 If $t b, s ≤ t ≤ t s, s$
2 Generate $a i, k \| k = 1,2, ?, t - 1 ∈ F p$ , $a i, k ≠ 0$
3 Compute $f i x = K S, i + a i, 1 x + ? + a i, t - 1 x t - 1 ? (m o d ? p)$
4 Compute $f i 0 = K S, i$
5 For $i = 1$ to $i = n$ do 6 For $j = 1$ to $j = n$ do
7 Compute $s i, j = f i x j ? (m o d ? p)$
8 End For
9 End For
10 Compute $λ i, k = a i, k · G$ , $k ∈ 1,2, ?, t - 1$
11 Compute $l e f t = s i, j · G ? (m o d ? p)$
12 Compute $r i g h t = s k · G + ∑ k = 1 t - 1 x j k λ i, k ? (m o d ? p)$
13 If $l e f t = r i g h t$
14 Compute $s i = ∑ j = 1 n s j, i ? (m o d ? p)$
15 Else
16 Compute $s i, j = f i x j ? (m o d ? p)$
17 Compute $β i = s i · G ? (m o d ? p)$
18 Set $x = 0$
19 Compute $K P = (∑ i = 1 t s i ∏ i = 1, i ≠ j t x - x i x j - x i) · G ? (m o d ? p)$
20 Return $s i, K P$
21 Else
22 Return $⊥$

Table 3 Key generation algorithm

密钥生成算法： $K e y g e n e r a t i o n P, t, k s, i → s i, K P$
输入： $P, t, k s, i$
输出： $s i, K P$
1 If $t b, s ≤ t ≤ t s, s$
2 Generate $a i, k \| k = 1,2, ?, t - 1 ∈ F p$ , $a i, k ≠ 0$
3 Compute $f i x = K S, i + a i, 1 x + ? + a i, t - 1 x t - 1 ? (m o d ? p)$
4 Compute $f i 0 = K S, i$
5 For $i = 1$ to $i = n$ do 6 For $j = 1$ to $j = n$ do
7 Compute $s i, j = f i x j ? (m o d ? p)$
8 End For
9 End For
10 Compute $λ i, k = a i, k · G$ , $k ∈ 1,2, ?, t - 1$
11 Compute $l e f t = s i, j · G ? (m o d ? p)$
12 Compute $r i g h t = s k · G + ∑ k = 1 t - 1 x j k λ i, k ? (m o d ? p)$
13 If $l e f t = r i g h t$
14 Compute $s i = ∑ j = 1 n s j, i ? (m o d ? p)$
15 Else
16 Compute $s i, j = f i x j ? (m o d ? p)$
17 Compute $β i = s i · G ? (m o d ? p)$
18 Set $x = 0$
19 Compute $K P = (∑ i = 1 t s i ∏ i = 1, i ≠ j t x - x i x j - x i) · G ? (m o d ? p)$
20 Return $s i, K P$
21 Else
22 Return $⊥$

Table 4 Voting algorithm

投票算法：

v o t e P, t, K P, k i, v i → 1,0

输入： $P, t, K P, k i, v i$

输出：1 or 0

1 If $t b ≤ t ≤ t e$

2 Choose a random element $d ∈ [1, p - 1]$

3 Compute $C = d · G ? (m o d ? p)$

4 Compute $C m = v i + d · K P ? (m o d ? p)$

5 Set $C v i = (C, C m)$

6 Get $σ (C v i) ← S L R S . s i g n P, C v i, k s, i, K R p, K R s, i$

7 If $1 ← S L R S . v e r i f y P, ? σ (C v i), K R p$

8 If $0 ← S L R S . l i n k (σ (C v i))$

9 Return 1

10 Else

11 Return 0

12 Else

13 Return 0

14 Else

15 Return

⊥

Table 4 Voting algorithm

投票算法：

v o t e P, t, K P, k i, v i → 1,0

输入： $P, t, K P, k i, v i$

输出：1 or 0

1 If $t b ≤ t ≤ t e$

2 Choose a random element $d ∈ [1, p - 1]$

3 Compute $C = d · G ? (m o d ? p)$

4 Compute $C m = v i + d · K P ? (m o d ? p)$

5 Set $C v i = (C, C m)$

6 Get $σ (C v i) ← S L R S . s i g n P, C v i, k s, i, K R p, K R s, i$

7 If $1 ← S L R S . v e r i f y P, ? σ (C v i), K R p$

8 If $0 ← S L R S . l i n k (σ (C v i))$

9 Return 1

10 Else

11 Return 0

12 Else

13 Return 0

14 Else

15 Return

⊥

Table 5 Result counting algorithm

结果统计算法：

c o u n t P, t, s 1, s 2, ?, s t → r e s

输入： $P, t, s 1, s 2, ?, s t$

输出： $r e s$

1 If $t > t e$

2 If $t b, s ≤ t ≤ t e, s$

3 Generate $x 1, F x 1, x 2, F x 2, ?, x t, F x t$ by

$s 1, s 2, ?, s t$

4 Compute $F x = ∑ i = 1 t s i ∏ i = 1, i ≠ j t x - x i x j - x i$

5 Compute $K S = F 0$

6 Compute $v i = C m - K S ? C ? (m o d ? p)$

7 For $i = 1$ to $i = n$ do

8 Compute $v i = v i + 1$

9 End For

10 Return $r = v i$

11 Else

12 Return $⊥$

13 Else

14 Return

⊥

Table 5 Result counting algorithm

结果统计算法：

c o u n t P, t, s 1, s 2, ?, s t → r e s

输入： $P, t, s 1, s 2, ?, s t$

输出： $r e s$

1 If $t > t e$

2 If $t b, s ≤ t ≤ t e, s$

3 Generate $x 1, F x 1, x 2, F x 2, ?, x t, F x t$ by

$s 1, s 2, ?, s t$

4 Compute $F x = ∑ i = 1 t s i ∏ i = 1, i ≠ j t x - x i x j - x i$

5 Compute $K S = F 0$

6 Compute $v i = C m - K S ? C ? (m o d ? p)$

7 For $i = 1$ to $i = n$ do

8 Compute $v i = v i + 1$

9 End For

10 Return $r = v i$

11 Else

12 Return $⊥$

13 Else

14 Return

⊥

Table 6 Comparisons with existing schemes

功能	文献[5]	文献[6]	文献[7]	本文方案
去中心化	×	×	√	√
可扩展	√	×	×	√
支持弃权	√	√	√	√
自动计票	×	×	√	√
支持多个候选项	√	√	×	√
七大安全性要求	×	×	×	√
适合大规模投票	√	×	×	√

Table 7 Comparisons of storage overhead

性能	文献[15]	文献[16]	本文方案
链接复杂度	$O ω$	$O ω$	$O 1$
签名大小	$O ω$	$O ω$	$O 1$

Table 7 Comparisons of storage overhead

性能	文献[15]	文献[16]	本文方案
链接复杂度	$O ω$	$O ω$	$O 1$
签名大小	$O ω$	$O ω$	$O 1$

Table 8 Comparisons of computational overhead of signatures

性能	文献[15]	文献[16]	本文方案
生成签名	$8 + 4 ω E + 4 + 2 ω M$	$2 ω E + M + 2 I$	$7 E + 19 S + 9 B$
验证签名	$2 E + 8 ω + 8 B$	$2 ω E$	$9 E + 6 S + 10 B$
总计算代价	$1 ? 565 ω + 3 ? 004 M$	$(960 ω + 25) M$	$5 ? 993.25 M$

Table 8 Comparisons of computational overhead of signatures

性能	文献[15]	文献[16]	本文方案
生成签名	$8 + 4 ω E + 4 + 2 ω M$	$2 ω E + M + 2 I$	$7 E + 19 S + 9 B$
验证签名	$2 E + 8 ω + 8 B$	$2 ω E$	$9 E + 6 S + 10 B$
总计算代价	$1 ? 565 ω + 3 ? 004 M$	$(960 ω + 25) M$	$5 ? 993.25 M$

Table 9 Comparisons of performance

阶段	文献[5]	文献[6]	文献[7]	本文方案
初始化	$O 1$	$O n$	—	$O 1$
投票	$O 1$	$O n 2$	$O n 2$	$O n 2$
结果统计与公布	$O n$	$O n$	$O n$	$O n$

Table 9 Comparisons of performance

阶段	文献[5]	文献[6]	文献[7]	本文方案
初始化	$O 1$	$O n$	—	$O 1$
投票	$O 1$	$O n 2$	$O n 2$	$O n 2$
结果统计与公布	$O n$	$O n$	$O n$	$O n$

Fig.2 Test of consumed Gas

Fig.3 Test of computational overhead

References 16

1	Kubjas I， Pikma T， Willemson J.Estonian voting verification mechanism revisited again［C］//International Joint Conference on Electronic Voting.Bregenz：Springer，2017：306-317.
2	Lubis M， Kartiwi M， Zulhuda S.Current state of personal data protection in electronic voting：criteria and indicator for effective implementation［J］.Telkomnika：Indonesian Journal of Electrical Engineering，2018，16（1）：290-301.
3	袁勇，王飞跃.区块链技术发展现状与展望［J］.自动化学报，2016，42（4）：481-494.
	Yuan Yong， Wang Fei‐yue.Blockchain：the state of the art and future trends［J］.Acta Automatica Sinica，2016，42（4）：481-494.
4	Zhao Z， Chan T H.How to vote privately using bitcoin［C］ //International Conference on Information and Communications Security. Beijing：Springer，2015：82-96.
5	Lee K， James J I， Ejeta T G，et al.Electronic voting service using block‐chain［J］.Journal of Digital Forensics，Security and Law，2016，11（2）：123-136.
6	Jason P C， Yuichi K.E‐voting system based on the bitcoin protocol and blind signatures［J］.IPSJ Transactions on Mathematical Modeling and Its Applications，2017，10（1）：14-22.
7	McCorry P， Shahandashti S F， Hao F.A smart contract for boardroom voting with maximum voter privacy［C］//International Conference on Financial Cryptography and Data Security. Sliema：Springer，2017：357-375.
8	Dimitriou T.Efficient，coercion‑free and universally verifiable blockchain‐based voting［J］.Computer Networks，2020，174：107234.
9	Russo A， Anta A F， Vasco M I G，et al.Chirotonia：a scalable and secure e‐voting framework based on blockchains and linkable ring signatures［C］//2021 IEEE International Conference on Blockchain.Melbourne：IEEE，2021：417-424.
10	Liu J K， Wong D S.Linkable ring signatures：security models and new schemes［C］//International Conference on Computational Science and Its Applications.Heidelberg：Springer，2005：614-623.
11	Rivest R L， Shamir A， Tauman Y.How to leak a secret［C］//Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security. Gold Coast：Springer，2001：552–565
12	Nguyen L.Accumulators from bilinear pairings and applications［C］//Topics in Cryptology‐CT‐RSA 2005.San Francisco：Springer，2005：275-292.
13	Desmedt Y G.Threshold cryptography［J］.European Transactions on Telecommunications，1994，5（4）：449-458.
14	Boneh D， Boyen X.Short signatures without random oracles［C］//EUROCRYPT 2004.Interlaken：Springer，2004：56-73.
15	Yuen T H， Liu J K， Au M H，et al.Efficient linkable and/or threshold ring signature without random oracles［J］.The Computer Journal，2013，56（4）：407-421.
16	张文芳，熊丹，王小敏，等.基于RSA公钥密码体制的可选择可转换关联环签名［J］.计算机学报，2017，40（5）：1168-1180.
	Zhang Wen‑fang， Xiong Dan， Wang Xiao‑min，et al.Selectively linkable and convertible ring signature based on RSA public key cryptosystem［J］.Chinese Journal of Computers，2017，40（5）：1168-1180.

[1]	Xiao-hu SHI, Xin YAO, Yan-feng SUN, De-yin MA. Contribution Degree and Data Validity Verification Based Consensus Algorithm [J]. Journal of Northeastern University(Natural Science), 2024, 45(2): 160-169.
[2]	JIANG Ji-ning， XIN Jun-chang， HAO Kun， HUANG Min5. Spatio-Temporal Keyword Query in Hybrid-Storage Blockchain [J]. Journal of Northeastern University(Natural Science), 2023, 44(12): 1696-1704.
[3]	JIAO Zi， ZHOU Fu-cai， WANG Qiang. Easily to Expand and Efficient Decentralized Cross Chain Exchange Protocol Based on Smart Contract [J]. Journal of Northeastern University(Natural Science), 2022, 43(5): 618-624.
[4]	TANG Dan， ZHUANG Xin-tian. Manufacturers’ Financing Strategy: Bank Credit， Retailer Credit or Blockchain-Driven SCF [J]. Journal of Northeastern University(Natural Science), 2021, 42(8): 1202-1209.
[5]	WANG Ke-yuan， YU Lei， YAN Yong， SUN Yi. Capitalization and Trading System Design of Power Data Based on Blockchain [J]. Journal of Northeastern University(Natural Science), 2021, 42(2): 166-173.
[6]	GAO Yan-fang， YAO Lan， MA Yan-song， LI Feng-yun. Research on Cloud Storage Integrity of Wireless Body Area Network Data Based on Blockchain Technology [J]. Journal of Northeastern University Natural Science, 2020, 41(3): 337-342.