基于双线性对的乐观Mix-net协议

doi:10.3969/j.issn.1000-436x.2013.11.017

摘要/Abstract

摘要：

提出了一种新的基于双线性对的乐观Mix-net协议。利用双线性对工具简化了密钥管理，在不同的协议会话中服务器端不用重新生成密钥，并且当前会话不会为其他会话提供解密预言机服务。采用了“哑元追踪法”保证混洗过程的完整性，简化了正确性证明的构造。对ElGamal联合解密过程做了优化，降低了每个服务器节的指数运算量。在没有服务器作弊的情况下，对输入密文组的混洗和解密速度比其他可公开验证的Mix-net方案高得多。

关键词: 匿名通信, 乐观混合网络, 双线性对, 秘密混洗证明

Abstract:

A novel pairing-based optimistic Mix-net scheme was proposed. The key management is made easier by em-ploying bilinear paring primitives and there is no need for the participating mix servers to re-generate keys jointly be-tween mix-sessions to avoid providing decryption oracle service to other mix-sessions. Integrity of messages during mix-ing is partially guaranteed by using dummy messages tracing technology resulting in a simpler construction for proofs“ ”of correctness. An optimization method for the joint E mal decryption involved in the protocol was also proposed, which can reduce the number of exponentiations computed by each mix server. The Mix-net will shuffle and decrypt in-put ciphertexts much faster than all previous Mix-nets with public verifiability when all mix servers execute the mixing protocol honestly.

Key words: anonymous communication, optimistic mix network, bilinear pairings, proof of secret shuffling

李龙海,付少锋,苏锐丹. 基于双线性对的乐观Mix-net协议[J]. 通信学报, 2013, 34(11): 153-161.

Long-hai LI,Shao-feng FU,Rui-dan SU. Optimistic Mix-net protocol based on bilinear pairings[J]. Journal on Communications, 2013, 34(11): 153-161.

图/表 2

参考文献 39

[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]	FUJIOKA A , OKAMOTO T , OHTA K . A practical secret votin scheme for large scale elections[A]. Cryptology- Asiacrypt '92[C]. Queensland, Australia, 1992.244-251.
[4]	NEFF A . A verifiable secret shuffle and its applicatio 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]. Financia Crypto-graphy '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]	SEBE F , MIRET J , PUJOLIS J , et al. Simple and efficient hash-based verifiable mixing for remote electronic voting[J]. Computer Commu-nications, 2010,33 (6): 667-675.
[8]	GOLLE P , ZHONG S , BONEH D , et al. Optimistic mixing for ex-it-polls[A]. Cryptology-Asiacrypt '02[C]. Queenstown, New Zealand, 2002.451-465.
[9]	ABE M . Flaws in some robust optimistic Mix-nets[A]. Proceedings of the 8th Australasian Conference on Information Security and Priva-cy[C]. Wollongong, Australia, 2003.39-50.
[10]	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.
[11]	LI L H , FU S F , CHE X Q . A new relation attack on the imistic Mix-net[A]. International Symposium on Computer Network and Multimedia Technology(CNMT 2009)[C]. Wuhan, China, 2009.1-4.
[12]	PFITZMANN A , PFITZMANN B . How to break the direct RSA-implementation of mixes[A]. Cryptology- Eurocrypt '89[C]. Houthalen, Belgium, 1989.373-381.
[13]	PARK C , ITOH K , KUROSAWA K . Efficient anoymous channel and all/nothing election scheme[A]. Cryptology-Eurocrypt'93[C]. Lofthus, Norway, 1994.248-259.
[14]	SAKO K , KILIAN J . Receipt-free mix-type voting scheme[A]. Cryp-tology-Eurocrypt '95[C]. Saint-Malo France, 1995.393-403.
[15]	OGATA W , KUROSAWA K , SAKO K , et al. Fault tolerant anonym-ous channel[A]. Proceedings of ICICS '97[C]. Beijing, China, 1997.440-444.
[16]	ABE M . Mix-networks on permutation networks[A]. Cryptology-Asiacrypt'99[C]. Singapore, 1999.258-273.
[17]	JAKOBSSON M , JUELS A . Millimix: Mixing in Small Batches[R]. DIMACS Technical Report, 1999.99-133.
[18]	WAKSMAN A . A permutation network[J]. Journal of the Association for Computing Machinery, 1968,15 (1): 159-163.
[19]	FURUKAWA J , SAKO K . An efficient scheme for proving a shuf-fle[A]. Cryptology- Crypto'01[C]. Santa Barbara, California, USA, 2001.368-387.
[20]	NEFF A . A verifiable secret shuffle and its applicatio to E-voting[A]. Proceedings of ACM CCS '01[C]. Philadelphia, Pennsylva ia, USA, 2001.116-125.
[21]	GROTH J . A verifiable secret shuffle of homomorphic encryptions[J]. Journal of Cryptology, 2010,23 (4): 546-579.
[22]	NGUYEN L , SAFAVI R , KUROSAWA K . Verifiable shuffles: a for-mal model and a paillier-based efficient construction with provable security[A]. Proceedings of ACNS '04[C]. Yellow Mountain, China, 2004.61-75.
[23]	PENG K , BOYD C , DAWSON E . Simple and efficient shuffli g with provable correctness and ZK privacy[A]. Cryptology- CRYPTO 2005[C]. Santa Barbara, California, USA, 2005.188-204.
[24]	WIKSTROM D . A sender verifiable mix-net and a new proof of a shuffle[A]. Cryptology-Asiacrypt '05[C]. Chennai, India, 2005.273-292.
[25]	PENG K . Failure of a mix network[J]. International Journal of Net-work Security ＆ Its Applications, 2011,3 (1): 81-97.
[26]	JAKOBSSON M . A practical mix[A]. Cryptology-Eurocrypt '98[C]. Espoo, Finland, 1998.448-461.
[27]	JAKOBSSON M . Flash mixing[A]. Proceedings of PODC '99[C]. Atlanta, Georgia, USA, 1999.83-89.
[28]	DESMEDT Y , KUROSAWA K . How to break a practical mix and design a new one[A]. Proceedings of PODC '99[C]. Bruges, Belgium, 2000.557-572.
[29]	MITOMO M , KUROSAWA K . Attack for flash mix[A]. Proceedings of Asiacrypt 2000[C]. Kyoto Japan, 2000.192-204.
[30]	JAKOBSSON M , JUELS A , RIVEST R . Making Mix-net robust for electronic voting by randomized partial checking[A]. Proceedings of USENIX'02[C]. San Francisco USA, 2002.339-353.
[31]	GOLLE P , BONEH D . Almost entirely correct mixing with lica-tions to voting[A]. Proceedings of ACM CCS'02[C]. Washington DC, USA, 2002.68-77.
[32]	BONEH D , FRANKLIN M . Identity based encryption from the Weil pairing[J]. SIAM J of Computing, 2003,32 (3): 586-615.
[33]	PEDERSEN P . Non-interactive and information theoretic secure veri-fiable secret sharing[A]. Cryptology-Crypto'91[C]. Santa Barbara, California, USA, 1991.129-140.
[34]	BELLARE M , ROGAWAY P . Random oracles are practical: a para-digm for designing efficient protocols[A]. Proceedings of ACM CCS' 93[C]. Fairfax, Virginia, USA, 1993.62-73.
[35]	CRAMER R , DAMGAARD I , SCKOENMAKERS B . Proofs of partial knowledge and simplified design of witness hid ng proto-cols[A]. Cryptology –Crypto '94[C]. Santa Barbara, California, USA, 1994.174-187.
[36]	FIAT A , SHAMIR A . How to prove yourself: practical sol ions to identification and signature problems[A]. Cryptology-Crypto '86[C]. Santa Barbara, California, USA, 1987.186-194.
[37]	KATE A , ZAVERUCHA G , GOLDBERG I . Pairing based onion tout-ing[A]. The 7th Workshop on Privacy Enhancing Technologies[C]. Ottawa, Canada, 2007.95-112.
[38]	FURUKAWA J , MIYAUCHI H , MORI K , et al. An implementation of a universally verifiable electronic voting scheme based on shuffling[A]. Financial Cryptography'02[C]. Southampton, Bermuda, 2002.16-30.
[39]	FURUKAWA J . Efficient, verifiable shuffle decryption a its re-quirements of unlinkability[A]. Proceedings of PKC 2004[C]. Singa-pore, 2004.319-332.

相关文章 15

[1]	姜占鹏, 孙铭玮, 黄海, 徐江, 刘志伟, 白瑞, 方舟, 曲家兴. 面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究[J]. 通信学报, 2022, 43(2): 100-108.
[2]	赵蕙, 王良民. 基于SDN节点淆乱机制的接收方不可追踪的混合匿名通道[J]. 通信学报, 2019, 40(10): 55-66.
[3]	徐明,李旭如,刘朝斌,马尧. 基于双重代理密钥的船舶自组网门限签名方案[J]. 通信学报, 2018, 39(7): 166-175.
[4]	宋成,张明月,彭维平,贾宗璞,刘志中,闫玺玺. 基于双线性对的车联网批量匿名认证方案研究[J]. 通信学报, 2017, 38(6): 49-57.
[5]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[6]	周彦伟,吴振强,杨波. 多样化的可控匿名通信系统[J]. 通信学报, 2015, 36(6): 105-115.
[7]	王洁,蔡永泉,田有亮. 基于博弈论的门限签名体制分析与构造[J]. 通信学报, 2015, 36(5): 148-155.
[8]	赵振国. 无证书签密机制的安全性分析与改进[J]. 通信学报, 2015, 36(3): 75-80.
[9]	王啸,方滨兴,刘培朋,郭莉,时金桥. Tor匿名通信网络节点家族的测量与分析[J]. 通信学报, 2015, 36(2): 80-87.
[10]	张宇，杜瑞颖，陈晶，侯健，周庆，王文武. 对一个基于身份签密方案的分析与改[J]. 通信学报, 2015, 36(11): 174-179.
[11]	李龙海,黄诚强,许尚妹,付少锋. 选择密文安全的可验证Mix-Net协议[J]. 通信学报, 2015, 36(10): 17-27.
[12]	杜红珍,温巧燕. 改进的无证书有序多重签名方案[J]. 通信学报, 2015, 36(10): 56-61.
[13]	李龙海，黄诚强，许尚妹，付少锋. 高效的基于混合加密的乐观Mix-net协议[J]. 通信学报, 2014, 35(Z2): 21-164.
[14]	李龙海,黄诚强,许尚妹,付少锋. 高效的基于混合加密的乐观Mix-net协议[J]. 通信学报, 2014, 35(Z2): 154-164.
[15]	郭晓军，程光，朱琛刚，TRUONG Dinh-Tu，周爱平. 主动网络流水印技术研究进展[J]. 通信学报, 2014, 35(7): 22-192.

协议	再加密	混洗证明的构造与验证	外层解密	内层解密
Golle的协议^[8]	6N	12n-6	6nN	2nN
所提协议	6N＋6 D	6 D+4n-2	3N+4n-2	2nN

协议	再加密	构造Mix证明与验证	解密
OKST97^[15]	2N	642Nn	(2+4n)N
Abe99^[16], JJ99^[17]	2N	7NlogN(2n-1)	(2+4n)N
FS01^[19]	2N	10N(2n-1)	(2+4n)N
Neff01^[4]	2N	8N(2n-1)	(2+4n)N
FMOS^[38]	2N	(10n-1)N	N
Groth^[21]	2N	(8n-1)N	N
Furukawa04^[39]	2N	(6n+2)N	N
Golle^[8]	6N	12n-6	8nN
所提协议	6N＋6D	6 D+4n-2	(3+2n)N+4n-2