基于区块链和简短可链接环签名的安全电子投票方案

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

中图分类号:

TP 309.2

吴淇毓, 杨帆, 周福才, 冯达. 基于区块链和简短可链接环签名的安全电子投票方案[J]. 东北大学学报（自然科学版）, 2024, 45(5): 619-627.

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.

图/表 12

图1 系统模型

Fig.1 System Model

表1 初始化算法

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

表1 初始化算法

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

表2 注册算法

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

⊥

表2 注册算法

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

⊥

表3 密钥生成算法

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 $⊥$

表3 密钥生成算法

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 $⊥$

表4 投票算法

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

⊥

表4 投票算法

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

⊥

表5 结果统计算法

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

⊥

表5 结果统计算法

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

⊥

表6 现有方案对比

Table 6 Comparisons with existing schemes

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

表7 签名存储开销对比 (of signatures)

Table 7 Comparisons of storage overhead

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

表7 签名存储开销对比 (of signatures)

Table 7 Comparisons of storage overhead

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

表8 签名计算开销对比

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$

表8 签名计算开销对比

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$

表9 性能对比

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$

表9 性能对比

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$

图2 Gas消耗测试

Fig.2 Test of consumed Gas

图3 计算开销测试

Fig.3 Test of computational overhead

参考文献 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]	时小虎, 姚鑫, 孙延风, 马德印. 基于贡献度和数据有效性检验的共识机制[J]. 东北大学学报（自然科学版）, 2024, 45(2): 160-169.
[2]	姜吉宁，信俊昌，郝琨，黄敏5. 混合存储区块链中的时空关键字查询[J]. 东北大学学报（自然科学版）, 2023, 44(12): 1696-1704.
[3]	焦梓，周福才，王强. 基于智能合约的易扩展高效去中心化跨链交易协议[J]. 东北大学学报（自然科学版）, 2022, 43(5): 618-624.
[4]	唐丹，庄新田. 制造商融资决策:银行、商业信用或区块链供应链金融[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1202-1209.
[5]	王柯元，于雷，颜拥，孙毅. 基于区块链的电力数据资产化及交易系统设计[J]. 东北大学学报（自然科学版）, 2021, 42(2): 166-173.
[6]	高艳芳，姚兰，马衍崧，李凤云. 基于区块链的无线体域网数据云存储完整性研究[J]. 东北大学学报:自然科学版, 2020, 41(3): 337-342.