选择密文安全的可验证Mix-Net协议

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

摘要/Abstract

摘要：

提出了一种在选择密文攻击下可证明安全的可验证Mix-Net协议。在Wikstr?m Mix-Net方案基础上，引入了新的密钥生成算法和秘密混洗零知识证明构造方法，提高了安全性。在不暴露输入密文与输出明文匹配关系的条件下，任何人都可以根据Mix服务器公布的证据验证输出结果的正确性，即满足可公开验证性；任意发送者还可以追踪和检验自己输入的密文的处理过程，即满足发送者可验证性。基于随机预言机假设证明了该协议在适应性选择密文攻击模型下的安全性。与之前具有类似安全属性的方案相比，所提协议无需信任中心，无需用户与服务器之间的多轮交互，计算和通信复杂度更低，因此是构建安全电子选举协议的理想密码学工具。

关键词: 混合网络, 秘密混洗证明, 选择密文安全, 电子选举

Abstract:

A CCA-secure verifiable Mix-Net protocol with provable security was proposed.The protocol was based on Wikstr?m’s Mix-Net and improves its security by introducing an improved key generation algorithm and a new method for constructing proof of secret shuffling.Without revealing the correspondence between inputs and outputs,proposed protocol enables everyone to verify the correctness of output plaintexts through checking evidences broadcasted by each server.Thus,it satisfies public verifiability.Any sender can trace and examine the processing procedure of its ciphertext.Thus,proposed protocol satisfies sender verifiability.It is prored to be CCA-secure under the assumption of random oracle.Compared with previous mix-net schemes which are CCA-secure,proposed protocol does not require any trusted center,and incurs fewer interactions between servers which also resulting in a lower computation and communication complexity.Hence,the protocol is an ideal cryptographic tool for constructing secure electronic election protocol.

Key words: mix network, proof of secret shuffling, CCA-secure; electronic election

李龙海,黄诚强,许尚妹,付少锋. 选择密文安全的可验证Mix-Net协议[J]. 通信学报, 2015, 36(10): 17-27.

Long-hai LI,Cheng-qiang HUANG,Shang-mei XU,Shao-feng FU. CCA-secure verifiable Mix-Net protocol[J]. Journal on Communications, 2015, 36(10): 17-27.

图/表 1

参考文献 31

[1]	CHAUM D . Untraceable electronic mail,return addresses,and digital pseudonyms[J]. Communications of the ACM, 1981,24(2): 84-88.
[2]	DINGLEDINE R , MATHEWSON N , SYVERSON P . Tor:the second-generation onion router[A]. Proceedings of the 13th USENIX Security Symposium[C]. San Antonio,USA, 2004. 303-320.
[3]	DEMIREL D , HENNING M , VANDEGRAAF J ,et al. Prêt à voter providing everlasting privacy[A]. Proceedings of the 4th International Conference on E-Voting and Identity[C]. Guildford,UK, 2013. 156-175.
[4]	YI X , OKAMOTO E . Practical Internet voting system[J]. Journal of Network and Computer Applications, 2013,36(1): 378-387.
[5]	GABBER E , BIBBONS P , MATIAS Y . How to make personalized Web browsing simple,secure,and anonymous[A]. Financial Cryptography ’97[C]. Anguilla,UK, 1997. 17-31.
[6]	JAKOBSSON M , RAIHI D . Mix-based electronic payments[A]. Proceedings of SAC ’98[C]. London,UK, 1998. 157-173.
[7]	JAKOBSSON M . Flash mixing[A]. Proceedings of PODC ’99[C]. Atlanta,Georgia,USA, 1999. 83-89.
[8]	JAKOBSSON M , JUELS A . An optimally robust hybrid mix network[A]. Twentieth ACM Symposium on Principles of Distributed Computing[C]. New York,NY,USA, 2001. 284-292.
[9]	GOLLE P , ZHONG S , BONEH D ,et al. Optimistic mixing for exit-polls[A]. Advances in Cryptology-Asiacrypt ’02[C]. Queenstown,New Zealand, 2002. 451-465.
[10]	WIKSTR?M D . A sender verifiable mix-net and a new proof of a shuffle[A]. Advances in Cryptology-Asiacrypt ’05[C]. Chennai,India, 2005. 273-292.
[11]	ABE M . Flaws in robust optimistic mix-nets and stronger security notions[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2006,89(1): 99-105.
[12]	WIKSTR?M D . Five practical attacks for “optimistic mixing for exit-polls”[A]. Proceedings of Selected Areas of Cryptography(SAC)[C]. Ottawa Canada, 2003. 160-174.
[13]	MITOMO M , KUROSAWA K . Attack for flash mix[A]. Proceedings of ASIACRYPT 2000[C]. Kyoto,Japan, 2000. 192-204.
[14]	LI L H , FU S F , CHE X Q . A new relation attack on the optimistic mix-net[A]. International Symposium on Computer Network and Multimedia Technology(CNMT 2009)[C]. Wuhan,China, 2009. 1-4.
[15]	PENG K . Failure of a mix network[J]. International Journal of Network Security ＆ Its Applications, 2011,3(1): 81-97.
[16]	WIKSTR?M D . A universally composable mix-net[A]. 1st Theory of Cryptography Conference[C]. 2004. 315-335.
[17]	WIKSTR?M D , GROTH J . An adaptively secure mix-net without erasures[A]. 33rd International Colloquium on Automata,Languages and Programming[C]. 2006. 276-287.
[18]	CAMENISCH J , MITYAGIN A . Mix-network with stronger security[A]. 5th International Workshop on Privacy Enhancing Technologies[C]. Cavtat,Croatia, 2005. 128-146.
[19]	KHAZAEI S , MORAN T,WIKSTR?M D . A mix-net from any CCA2 secure cryptosystem[A]. Advances in Cryptology – ASIACRYPT 2012[C]. Beijing,China, 2012. 607-625.
[20]	JAKOBSSON M , JUELS A , RIVEST R . Making mix nets robust for electronic voting by randomized partial checking[A]. Proceedings of USENIX'02[C]. San Francisco,USA, 2002. 339-353.
[21]	FURUKAWA J , SAKO K . An efficient scheme for proving a shuffle[A]. Advances in Cryptology- Crypto’01[C]. Santa Barbara,California,USA, 2001. 368-387.
[22]	NEFF A . A verifiable secret shuffle and its application to E-Voting[A]. Proceedings of ACM CCS ’01[C]. Philadelphia,Pennsylvania,USA, 2001. 116-125.
[23]	GROTH J . A verifiable secret shuffle of homomorphic encryptions[J]. Journal of Cryptology, 2010,23(4): 546-579.
[24]	CANETTI R . Universally composable security:a new paradigm for cryptographic protocols[A]. 42nd IEEE Symposium on Foundations of Computer Science[C]. NY,USA, 2001. 136-145.
[25]	BELLARE M , ROGAWAY P . Random oracles are practical:a paradigm for designing efficient protocols[A]. Proceedings of ACM CCS’ 93[C]. Fairfax,Virginia,USA, 1993. 62-73.
[26]	FIAT A , SHAMIR A . How to prove yourself:practical solutions to identification and signature problems[A]. CRYPTO 1986[C]. 1986. 186-194.
[27]	PEDERSEN P . Non-interactive and information theoretic secure verifiable secret sharing[A]. Advances in Cryptology-Crypto'91[C]. Santa Barbara,California,USA, 1991. 129-140.
[28]	DOLEV D , STRONG H . Authenticated algorithms for byzantine agreement[J]. SIAM Journal on Computing, 1983,12(4): 656-666.
[29]	SHOUP V , GENNARO R . Securing threshold cryptosystems against chosen ciphertext attack[J]. Journal of Cryptology, 2002,15(2): 75-96.
[30]	KHAZAEI S,WIKSTR?M D . Randomized partial checking Revisited[A]. Proceedings of the 13th International Conference on Topics in Cryptology[C]. San Francisco,CA,February, 2013. 115-128.
[31]	KüSTERS R , TRUDERUNG T , VOGT A . Formal analysis of chaumian mix nets with randomized partial checking[A]. Proceedings of the 2014 IEEE Symposium on Security and Privacy[C]. Washington,DC,USA, 2014. 343-358.

性能	本方案	文献[23]的方案
验证消息合法性	3n	2n
再加密	0	2n
构造混洗证明	8n	6n
验证混洗证明	6(k?1)n	6(k?1)n
解密	2n	n
构造解密证明	0	2n
验证解密证明	0	2(k?1)n
计算量合计	(6k+7)n	(8k+5)n
发送比特数	2nl_G+3nl_q	3nl_G+5nl_q
接收比特数	2knl_G+3(k-1)nl_q	3knl_G+5(k?1)nl_q