基于QA-NIZK证明系统的高效简短可验证洗牌方案

doi:10.11959/j.issn.1000-436x.2015186

通信学报 ›› 2015, Vol. 36 ›› Issue (9): 188-192.doi: 10.11959/j.issn.1000-436x.2015186

基于QA-NIZK证明系统的高效简短可验证洗牌方案

程小刚^1,²,王箭¹,陈永红²

¹ 南京航空航天大学计算机科学与技术学院，江苏南京 210016
² 华侨大学计算机科学与技术学院，福建厦门 361021

出版日期:2015-09-25 发布日期:2017-09-15
基金资助:
国家自然科学基金资助项目;福建省自然科学基金资助项目

Highly efficient compact verifiable shuffle scheme based on QA-NIZK proof

Xiao-gang CHENG^1,²,Jian WANG¹,Yong-hong CHEN²

¹ College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
² College of Computer Science and Technology,Huaqiao University,Xiamen 361021,China

Online:2015-09-25 Published:2017-09-15
Supported by:
The National Natural Science Foundation of China;The Natural Science Foundation of Fujian Prov-ince

摘要/Abstract

摘要：

电子投票中为保护投票者的隐私，要由一系列混合服务器对选票进行洗牌操作，为保证洗牌操作的诚实性，需要可验证洗牌方案。现有简短可验证洗牌方案的证明大小要依赖于混合服务器的数量和投票者的数量，效率较低。基于近来的一个高效的 QA-NIZK 证明系统构建了一个高效的简短可验证洗牌方案，不管有多少混合器和投票者其证明大小都是O(1)，即常量大小。具有其独立的意义是在构建中指出原QA-NIZK证明系统是可变的。

关键词: 简短可验证洗牌, 可变性, 电子投票, QA-NIZK

Abstract:

To protect the privacy of voters in e-voting,votes should be shuffled by a series of mix servers.To guarantee the honesty of mix servers,verifiable shuffle scheme was needed.However the proof size of existed CVS (compact veri-fiable shuffle) scheme was dependent on the number of mix servers and the number of voters,which could be very ineffi-cient when there were lots of mix servers and voters.A new CVS scheme was presented with the proof size of only O(1),i.e.constant no matter how many mix servers and voters were involved.The construction is based on an efficient proof system QA-NIZK (quasi-adaptive non-interactive zero knowledge) presented recently.It also points out that the QA-NIZK proof system is malleable,which is of independent interest.

Key words: compact verifiable shuffle, malleability, e-voting, QA-NIZK

程小刚,王箭,陈永红. 基于QA-NIZK证明系统的高效简短可验证洗牌方案[J]. 通信学报, 2015, 36(9): 188-192.

Xiao-gang CHENG,Jian WANG,Yong-hong CHEN. Highly efficient compact verifiable shuffle scheme based on QA-NIZK proof[J]. Journal on Communications, 2015, 36(9): 188-192.

图/表 2

表1

表2

本文方案与交互式VS方案效率对比"

方案	单个服务器证明回合数	l个服务器证明回合数	单服务器通信复杂度	l个服务器通信复杂度
BG方案	9	9l	$Θ (n^{\frac{1}{2}})$	$l Θ (n^{\frac{1}{2}})$
GI方案	7	7l	$Θ (n^{\frac{2}{3}})$	$l Θ (n^{\frac{2}{3}})$
Groth方案	7	7l	Θ(n)	lΘ(n)
TW方案	5	5l	Θ(n)	lΘ(n)
Peng方案	3	3l	Θ(n)	lΘ(n)
本文方案	1	1	O(1)	O(1)

表2

参考文献 15

[1]	CHAUM D . Untraceable electronic mail,return addresses,and digital pseudonyms[J]. Communications of ACM, 2008,32(5): 98-101.
[2]	SAKO K , KILIAN J . Receipt-free mix-type voting scheme[A]. EUROCRYPT 1995[C]. Springer, 1995.393-403.
[3]	BAYER S , GROTH J . Efficient zero-knowledge argument for cor-rectness of a shuffle[A]. EUROCRYPT 2012[C]. Springer, 2012.281-300.
[4]	GROTH J , ISHAI Y . Sub-linear zero-knowledge argument for correctness of a shuffle[A]. EUROCRYPT 2008[C]. Springer, 2008.379-396.
[5]	GROTH J . A verifiable secret shuffle of homomorphic encryptions[J]. Journal of Cryptology, 2010,23(4): 546-579.
[6]	TERELIUS B , WIKSTROM D . Proofs of restricted shuffles[A]. AF-RICACRYPT 2010[C]. Springer, 2010.100-113.
[7]	PENG K . A shuffle to achieve high efficiency through pre-computa-tion and batch verification[J]. International Journal of Information Se-curity, 2013,12(4): 337-345.
[8]	GROTH J , LU S . A non-interactive shuffle with pairing based verifi-ability[A]. ASIACRYPT 2007[C]. Springer, 2007.51-67.
[9]	LIPMAA H , ZHANG B . A more efficient computationally sound non-interactive zero-knowledge shuffle argument[A]. SCN 2012[C]. Springer, 2012.477-502.
[10]	CHASE M , KOHLWEISS M , LYSYANSKAYA A , et al. Malleable proof systems and applications[A]. EUROCRYPT 2012[C]. Springer, 2012.281-300.
[11]	CHASE M , KOHLWEISS M , LYSYANSKAYA A , et al. Verifiable elections that scale for free[A]. PKC 2013[C]. Springer, 2013.479-496.
[12]	CHENG X , WANG J , CHEN Y . Improvement of a compact verifiable shuffle scheme[J]. ICIC Express Letters,Part B:Applications, 2014,5(4): 1115-1119.
[13]	CHASE M , KOHLWEISS M , LYSYANSKAYA A , et al. Succinct malleable NIZKs and an application to compact shuffles[A]. TCC 2013[C]. Springer, 2013.100-119.
[14]	JUTLA C , ROY A . Shorter quasi-adaptive NIZK proofs for linear subspaces[A]. ASIACRYPT 2013 Part I[C]. Springer, 2013.1-20.
[15]	GROTH J , SAHAI A . Efficient non-interactive proof systems for bilinear groups[A]. EUROCRYPT 2008[C]. Springer, 2008.415-432.

方案	诚实洗牌的证明大小服务器参与的证明大小	总大小	备注
GL方案	每个服务器生成一个 O(n)大小的证明证明其诚实的洗牌操作	O(nl)	n是投票者数量l是混合服务器数量
LZ方案	每个服务器生成一个 O(n)大小的证明证明其诚实的洗牌操作	O(nl)	效率只比GL方案有少许提高，渐近复杂度是一致的
原CVS方案	O(l)O(n)	O(n+l)
本文方案	O(1)O(1)	O(1)

基于QA-NIZK证明系统的高效简短可验证洗牌方案

Highly efficient compact verifiable shuffle scheme based on QA-NIZK proof

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 15

相关文章 1

Metrics

推荐阅读 0