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

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

Journal on Communications ›› 2015, Vol. 36 ›› Issue (9): 188-192.doi: 10.11959/j.issn.1000-436x.2015186

• academic paper • Previous Articles Next Articles

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

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

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.

Figures/Tables 2

方案	单个服务器证明回合数	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)

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

方案	诚实洗牌的证明大小服务器参与的证明大小	总大小	备注
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)

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 15

Related Articles 0

Metrics

Recommended 0