高效的基于混合加密的乐观Mix-net协议

doi:10.3969/j.issn.1000-436x.2014.z2.021

摘要/Abstract

摘要：

提出了一种高效的基于混合加密算法的Mix-net协议。正常情况下，当所有Mix服务器都忠实地执行协议时，其运算速度优于其他所有已知的具有公开可验证性的Mix-net。采用一种“乐观的”、基于散列运算的方法验证混洗过程的正确性，避免了构造复杂的、耗时的零知识证明，因此获得了速度上的提升。只用两轮逐元素的测试过程确保消息未被恶意服务器篡改，并且测试中仅涉及低代价的散列运算。公钥加密和对称密钥加密的有效结合也加速了混洗。这些优化措施使单个Mix服务器的运算量几乎和服务器数目无关，除了少量可忽略的计算任务。此外，任何人都可以通过少量的指数运算快速验证输出结果的正确性。方案也满足健壮性。这些特点使该方案非常适合用在大规模的电子选举中。

关键词: 匿名通信, 电子选举, 混合网络, 混合加密

Abstract:

An efficient hybrid-encryption-based Mix-net is presented that is much faster than all previous Mix-nets with public verifiability when all mix-servers execute the mixing protocol honestly (the usual case).The improvement by taking an “optimistic” and hash-based approach to verify the correctness of mixing is achieved without requiring complex and costly zero-knowledge proofs.Only two element-wise testing processes with low-cost computations of hash functions are involved to make certain messages are not manipulated by a cheating server.An efficient integration of public-key and symmetric-key operations also speeds up the mixing.As a result,the computational task of each mix-server is almost independent of the number of mix-servers except for some negligible tasks.Anyone can verify the correctness of a result rapidly by computing a few exponentiations.The scheme is robust,too.Those characteristics make it very suitable for large scale electronic voting.

Key words: anonymous communication, electronic voting, mix network, hybrid encryption

李龙海,黄诚强,许尚妹,付少锋. 高效的基于混合加密的乐观Mix-net协议[J]. 通信学报, 2014, 35(Z2): 154-164.

Long-hai LI,Cheng-qiang HUANG,Shang-mei XU,Shao-feng FU. Efficient hybrid-encryption-based optimistic Mix-net protocol[J]. Journal on Communications, 2014, 35(Z2): 154-164.

图/表 2

参考文献 23

[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, 2004. 03-320.
[3]	FUJIOKA A , OKAMOTO T , OHTA K . A practical secret voting scheme for large scale elections[A]. Cryptology-Asiacrypt’92[C]. Queensland,Australia, 1992. 244-251.
[4]	NEFF A . A verifiable secret shuffle and its application to e-voting[A]. Proceedings of ACM CCS ’01[C]. New York,USA, 2001. 116-125.
[5]	GABBER E , BIBBONS P , MATIAS Y . How to make personalized Web browsing simple,secure,and anonymous[A]. Financial Cryptography ’97[C]. Anguilla, 1997. 17-31.
[6]	JAKOBSSON M , RAIHI D . Mix-based electronic payments[A]. Proceedings of SAC ’98[C]. Kingston,Canada, 1998. 157-173.
[7]	SEBE F , MIRET J , PUJOLIS J ,et al. Simple and efficient hash-based verifiable mixing for remote electronic voting[J]. Computer Communications, 2010,33(6): 667-675.
[8]	WIKSTROM D . A sender verifiable Mix-net and a new proof of a shuffle[A]. Advances in Cryptology-Asiacrypt ’05[C]. Chennai (Madras),India, 2005. 273-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]	ABE M . Flaws in some robust optimistic Mix-nets[A]. Proceedings of Information Security and Privacy,8th Australasian Conference[C]. Wollongong,Australia, 2003. 39-50.
[11]	WIKSTROM D . Five practical attacks for “optimistic mixing for exit-polls”[A]. Proceedings of Selected Areas of Cryptography (SAC)[C]. Ottawa,Canada, 2003. 160-174.
[12]	LONGHAI L , SHAOFENG F , XIANGQUAN C . A new relation attack on the optimistic Mix-net[A]. International Symposium on Computer Network and Multimedia Technology(CNMT 2009)[C]. Wuhan, 2009. 1-4.
[13]	FURUKAWA J . Efficient,verifiable shuffle decryption and its requirements of unlinkability[A]. Proceedings of PKC 2004[C]. Singapore, 2004. 319-332.
[14]	CRAMER R , DAMGAARD I , SCHOENMAKERS B . Proofs of partial knowledge and simplified design of witness hiding protocols[A]. Cryptology–Crypto’94[C]. California,USA, 1994. 174-187.
[15]	FIAT A , SHAMIR A . How to prove yourself:practical solutions to identification and signature problems[A]. Cryptology-Crypto’86[C]. California,USA, 1987. 186-194.
[16]	PEDERSEN P . Non-interactive and information theoretic secure verifiable secret sharing[A]. Advances in Cryptology:Crypto'91[C]. California,USA, 1991. 129-140.
[17]	FURUKAWA J , SAKO K . An efficient scheme for proving a shuffle[A]. Proceedings of Crypto’ 2001[C]. California,USA, 2001. 368-387.
[18]	NEFF A . A verifiable secret shuffle and its application to e-voting[A]. Proceedings of ACM CCS ’01[C]. New York,USA, 2001. 116-125.
[19]	GROTH J . A verifiable secret shuffle of homomorphic encryptions[J]. Journal of Cryptology, 2010,23(4): 546-579.
[20]	FURUKAWA J , MIYAUCHI H , MORI K . An implementation of a universally verifiable electronic voting scheme based on shuffling[A]. Proceedings of Financial Cryptography'02[C]. Southampton,Bermuda, 2002. 16-30.
[21]	OHKUBO M , ABE M . A length-invariant hybrid mix[A]. Cryptology-Asiacrypt’00[C]. Kyoto,Japan, 2000. 178-191.
[22]	OGATA W , KUROSAWA K , SAKO K ,et al. Fault tolerant anonymous channel[A]. Proceedings of.ICICS '97[C]. South Africa, 1997. 440-444.
[23]	ABE M . Mix-networks on permutation networks[A]. CryptologyAsiacrypt’99[C]. Singapore, 1999. 258-273.

协议	再加密	构造完整性证明与验证	解密
OKST97^[22]	2N	642Nn	(2+4n)N
Abe99^[23]	2N	7NlogN(2n-1)	(2+4n)N
FS01^[17]	2N	10N(2n-1)	(2+4n)N
Neff01^[4]	2N	8N(2n-1)	(2+4n)N
FMOS^[20]	2N	(10n-1)N	N
Groth^[19]	2N	(8n-1)N	N
Furukawa04^[13]	2N	(6n+2)N	N
WikStrom^[8]	2N	(2n+3)N	N
Golle^[9]	6N	12n-6	8nN
所提协议	2N	4n-2	4N+4n-2