直方图与饼形图的保密生成协议
|
摘要
在密码学中,安全多方计算已经成为一个重要的研究方向,成为国际密码学界研究的热点之一.由于效率的要求,安全多方计算需要根据具体问题提出具体的解决方案.密码学者们已经研究出了许多问题的解决方案,但更多的安全多方计算问题还有待研究.保密生成直方图、饼形图的问题就是一个全新的问题,目前还没有看到这个问题的解决方案.为了保密地生成直方图与饼形图,本文首先基于Paillier加法同态加密算法,并结合一种新的编码方法设计了一个保密生成直方图与饼形图的协议;然后利用这种编码方法与椭圆曲线加法同态加密算法以及门限加密算法相结合,设计出保密性更好、计算复杂度与通信复杂度更低的新协议;最后利用模拟范例对协议进行了安全性分析,证明了方案对于半诚实参与者是安全的,并给出了相应的效率分析和实验验证.本文的协议能够很好地抵抗合谋攻击,尤其第二个协议可以用于抵抗任意数量的合谋攻击,因此应用本文所设计的协议或其设计思想,能够解决许多实际应用问题.
Secure multiparty computation(SMC) is an important aspect of cryptography and a research focus in the international cryptographic community. Though there are universal solutions to secure multiparty computation problems, for the efficiency reason, specific solutions should be developed for specific problems. Although many SMC problems have been investigated, more problems remain to be studied. How to privately generate a histogram or pie chart is a completely new problem which has not been studied. To privately generate a histogram or pie chart, this paper first proposes a new encoding scheme, based on the Paillier additively homomorphic encryption algorithm, and designs a protocol to privately generate a histogram or pie chart. Then a more efficient and more secure protocol is proposed based on elliptic curve additively homomorphic encryption algorithm and threshold encryption algorithms. Finally, the correctness of the proposed protocols are analyzed, and it is proved that these protocols are secure using simulation paradigm in the semi-honest model. The computational complexities and communication complexities of the proposed protocols are analyzed,which shows that these protocols are efficient. The second protocol can resist collision attack of any parties, and the ideas and the protocols in this paper can be used to solve other practical problems.
Secure multiparty computation(SMC) is an important aspect of cryptography and a research focus in the international cryptographic community. Though there are universal solutions to secure multiparty computation problems, for the efficiency reason, specific solutions should be developed for specific problems. Although many SMC problems have been investigated, more problems remain to be studied. How to privately generate a histogram or pie chart is a completely new problem which has not been studied. To privately generate a histogram or pie chart, this paper first proposes a new encoding scheme, based on the Paillier additively homomorphic encryption algorithm, and designs a protocol to privately generate a histogram or pie chart. Then a more efficient and more secure protocol is proposed based on elliptic curve additively homomorphic encryption algorithm and threshold encryption algorithms. Finally, the correctness of the proposed protocols are analyzed, and it is proved that these protocols are secure using simulation paradigm in the semi-honest model. The computational complexities and communication complexities of the proposed protocols are analyzed,which shows that these protocols are efficient. The second protocol can resist collision attack of any parties, and the ideas and the protocols in this paper can be used to solve other practical problems.
引文
[1]YAO A.Protocols for secure computations[C].In:Proceeding of the 23th IEEE Annual Symposium on Foundations of Computer Science(SFCS 1982).IEEE Computer Science Press,1982:160-164.[DOI:10.1109/SFCS.1982.38]
[2]BEN-OR M,GOLDWASSER S,WIGDERSON A.Completeness theorems for non-cryptographic fault-tolerant distributed computations[C].In:Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.ACM,1988:1-10.[DOI:10.1145/62212.62213]
[3]CANETTI R,COHEN A,LNDELL Y.A simpler variant of universally composable security for standard multiparty computation[C].In:Advances in Cryptology-CRYPTO 2015,Part II.Springer Berlin Heidelberg,2015:3-22.[DOI:10.1007/978-3-662-48000-7_1]
[4]HAZAY C,VENKLTASUBRAMANIAM M.On the power of secure two-party computation[C].In:Advances in Cryptology-CRYPTO 2016,Part II.Springer Berlin Heidelberg,2016:397-429.[DOI:10.1007/978-3-662-53008-5_14]
[5]DAMG?RD I,NIELSEN J B,OSTROVSKY R,et al.Unconditionally secure computation with reduced interaction[C].In:Advances in Cryptology-EUROCRYPT 2016,Part II.Springer Berlin Heidelberg,2016:420-447.[DOI:10.1007/978-3-662-49896-5_15]
[6]GOLDWASSER S.Multi-party computations:Past and present[C].In:Proceedings of the 16th Annual ACMSymposium on Principles of Distributed Computing.ACM,1997:1-6.[DOI:10.1145/259380.259405]
[7]CRAMER R,DAMG?RD I B,NIELSEN J B.Secure Multiparty Computation[M].Cambridge University Press,London:2015:6-14.[DOI:10.1017/CBO9781107337756]
[8]YAO A.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science.IEEE,1986:162-167.[DOI:10.1109/SFCS.1986.25]
[9]GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C].In:Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing.ACM,1987:218-229.[DOI:10.1145/28395.28420]
[10]GOLDREICH O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004.[DOI:10.1017/CBO9780511721656]
[11]FAGIN R,NAOR M,WINKLERY P.Comparing information without leaking it[J].Communications of the ACM,1996,39(5):77-85.[DOI:10.1145/229459.229469]
[12]SAMANTHULA B K,JIANG W.Secure multiset intersection cardinality and its application to Jaccard coefficient[J].IEEE Transactions on Dependable and Secure Computing,2016,13(5):591-604.[DOI:10.1109/TDSC.2015.2415482]
[13]FREEDMAN M J,NISSIM K,PINKAS B.Efficient private matching and set intersection[C].In:Advances in Cryptology-EUROCRYPT 2004.Springer Berlin Heidelberg,2004:1-19.[DOI:10.1007/978-3-540-24676-3_1]
[14]KISSNER L,SONG D.Privacy-preserving set operations[C].In:Advances in Cryptology-CRYPTO 2005.Springer Berlin Heidelberg,2005:241-257.[DOI:10.1007/11535218_15]
[15]YANG X Y,LI S D,KANG J.Private replacement and its applications in scientific computation[J].Chinese Journal of Computers,2018,41(5):1132-1142.[DOI:10.11897/SP.J.1016.2018.01132]杨晓艺,李顺东,亢佳.保密替换及其在保密科学计算中的应用[J].计算机学报,2018,41(5):1132-1142.[DOI:10.11897/SP.J.1016.2018.01132]
[16]BEIMEL A,GABIZON A,ISHAI Y,et al.Non-interactive secure multiparty computation[C].In:Advances in Cryptology-CRYPTO 2014.Springer Berlin Heidelberg,2014:387-404.[DOI:10.1007/978-3-662-44381-1_22]
[17]DOU J W,GONG L M,LI S D,et al.Efficient private subset computation[J].Security and Communication Networks,2016,9(18):5965-5976.[DOI:10.1002/sec.1749]
[18]ATALLAH M J,DU W.Secure multi-party computational geometry[C].In:Algorithms and Data StructuresWADS 2001.Springer Berlin Heidelberg,2001:165-179.[DOI:10.1007/3-540-44634-6_16]
[19]LI S D,WU C Y,WANG D S,DAI Y Q.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.[DOI:10.1016/j.ins.2014.04.004]
[20]QIN J,DUAN H,ZHAO H,et al.A new Lagrange solution to the privacy-preserving general geometric intersection problem[J].Journal of Network and Computer Applications,2014,46:94-99.[DOI:10.1016/j.jnca.2014.08.004]
[21]DU W L,ATALLAH M J.Privacy-preserving cooperative statistical analysis[C].In:Proceedings of the 17th Annual Conference of Computer Security Applications.IEEE,2001:102-110.[DOI:10.1109/ACSAC.2001.991526]
[22]JAWUREK M,KERSCHBAUM F.Fault-tolerant privacy-preserving statistics[C].In:Privacy Enhancing Technologies-PETS 2012.Springer Berlin Heidelberg,2012:221-238.[DOI:10.1007/978-3-642-31680-7_12]
[23]AGRAWAL R,SRIKANT R.Privacy-preserving data mining[J].ACM SIGMOD Record,2000,29(2):439-450.[DOI:10.1145/335191.335438]
[24]KANTARDZIC M.Data Mining:Concepts,Models,Methods and Algorithms[M].Second Edition.John Wiley&Sons,Inc.and IEEE Press,2011:300-326.
[25]AGGARWAL C C.Privacy preserving data mining[J].Application Research of Computers,2008,9(8):616-621.[DOI:10.1007/s00145-001-0019-2]
[26]DU W L,ATALLAH M J.Protocols for secure remote database access with approximate matching[C].In:E-Commerce Security and Privacy,Advances in Information Security,Vol.2.Springer Boston,2001:87-111.[DOI:10.1007/978-1-4615-1467-1_6]
[27]CACHIN C.Efficient private bidding and auctions with an oblivious third party[C].In:Proceedings of the 6th ACM Conference on Computer and Communications Security.ACM,1999:120-127.[DOI:10.1145/319709.319726]
[28]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.
[29]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[C].In:Advances in Cryptology-EUROCRYPT 99.Springer Berlin Heidelberg,1999:223-238.[DOI:10.1007/3-540-48910-X_16]
[30]YANG B.Foundations of Modern Cryptography[M].Beijing:Tsinghua University Press,2015:106-110.杨波.现代密码学基础[M].北京:清华大学出版社,2015:106-110.
[31]BH P,CHANDRAVATHI D,ROJA P P.Encoding and decoding of a message in the implementation of elliptic curve cryptography using Koblitz’s method[J].International Journal on Computer Science and Engineering,2010,2(5):1904-1907.
[32]DESMEDT Y,FRANKEL Y.Threshold cryptosystems[C].In:Advances in Cryptology-CRYPTO’89.Springer New York,1990:307-315.[DOI:10.1007/3-540-57220-1_47]
[33]LONG Y,CHEN K F,MAO X P.New constructions of dynamic threshold cryptosystem[J].Journal of Shanghai Jiao Tong University(Science),2014,19:431-435.[DOI:10.1007/s12204-014-1520-8]
[2]BEN-OR M,GOLDWASSER S,WIGDERSON A.Completeness theorems for non-cryptographic fault-tolerant distributed computations[C].In:Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing.ACM,1988:1-10.[DOI:10.1145/62212.62213]
[3]CANETTI R,COHEN A,LNDELL Y.A simpler variant of universally composable security for standard multiparty computation[C].In:Advances in Cryptology-CRYPTO 2015,Part II.Springer Berlin Heidelberg,2015:3-22.[DOI:10.1007/978-3-662-48000-7_1]
[4]HAZAY C,VENKLTASUBRAMANIAM M.On the power of secure two-party computation[C].In:Advances in Cryptology-CRYPTO 2016,Part II.Springer Berlin Heidelberg,2016:397-429.[DOI:10.1007/978-3-662-53008-5_14]
[5]DAMG?RD I,NIELSEN J B,OSTROVSKY R,et al.Unconditionally secure computation with reduced interaction[C].In:Advances in Cryptology-EUROCRYPT 2016,Part II.Springer Berlin Heidelberg,2016:420-447.[DOI:10.1007/978-3-662-49896-5_15]
[6]GOLDWASSER S.Multi-party computations:Past and present[C].In:Proceedings of the 16th Annual ACMSymposium on Principles of Distributed Computing.ACM,1997:1-6.[DOI:10.1145/259380.259405]
[7]CRAMER R,DAMG?RD I B,NIELSEN J B.Secure Multiparty Computation[M].Cambridge University Press,London:2015:6-14.[DOI:10.1017/CBO9781107337756]
[8]YAO A.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science.IEEE,1986:162-167.[DOI:10.1109/SFCS.1986.25]
[9]GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C].In:Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing.ACM,1987:218-229.[DOI:10.1145/28395.28420]
[10]GOLDREICH O.Foundations of Cryptography:Basic Applications[M].London:Cambridge University Press,2004.[DOI:10.1017/CBO9780511721656]
[11]FAGIN R,NAOR M,WINKLERY P.Comparing information without leaking it[J].Communications of the ACM,1996,39(5):77-85.[DOI:10.1145/229459.229469]
[12]SAMANTHULA B K,JIANG W.Secure multiset intersection cardinality and its application to Jaccard coefficient[J].IEEE Transactions on Dependable and Secure Computing,2016,13(5):591-604.[DOI:10.1109/TDSC.2015.2415482]
[13]FREEDMAN M J,NISSIM K,PINKAS B.Efficient private matching and set intersection[C].In:Advances in Cryptology-EUROCRYPT 2004.Springer Berlin Heidelberg,2004:1-19.[DOI:10.1007/978-3-540-24676-3_1]
[14]KISSNER L,SONG D.Privacy-preserving set operations[C].In:Advances in Cryptology-CRYPTO 2005.Springer Berlin Heidelberg,2005:241-257.[DOI:10.1007/11535218_15]
[15]YANG X Y,LI S D,KANG J.Private replacement and its applications in scientific computation[J].Chinese Journal of Computers,2018,41(5):1132-1142.[DOI:10.11897/SP.J.1016.2018.01132]杨晓艺,李顺东,亢佳.保密替换及其在保密科学计算中的应用[J].计算机学报,2018,41(5):1132-1142.[DOI:10.11897/SP.J.1016.2018.01132]
[16]BEIMEL A,GABIZON A,ISHAI Y,et al.Non-interactive secure multiparty computation[C].In:Advances in Cryptology-CRYPTO 2014.Springer Berlin Heidelberg,2014:387-404.[DOI:10.1007/978-3-662-44381-1_22]
[17]DOU J W,GONG L M,LI S D,et al.Efficient private subset computation[J].Security and Communication Networks,2016,9(18):5965-5976.[DOI:10.1002/sec.1749]
[18]ATALLAH M J,DU W.Secure multi-party computational geometry[C].In:Algorithms and Data StructuresWADS 2001.Springer Berlin Heidelberg,2001:165-179.[DOI:10.1007/3-540-44634-6_16]
[19]LI S D,WU C Y,WANG D S,DAI Y Q.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.[DOI:10.1016/j.ins.2014.04.004]
[20]QIN J,DUAN H,ZHAO H,et al.A new Lagrange solution to the privacy-preserving general geometric intersection problem[J].Journal of Network and Computer Applications,2014,46:94-99.[DOI:10.1016/j.jnca.2014.08.004]
[21]DU W L,ATALLAH M J.Privacy-preserving cooperative statistical analysis[C].In:Proceedings of the 17th Annual Conference of Computer Security Applications.IEEE,2001:102-110.[DOI:10.1109/ACSAC.2001.991526]
[22]JAWUREK M,KERSCHBAUM F.Fault-tolerant privacy-preserving statistics[C].In:Privacy Enhancing Technologies-PETS 2012.Springer Berlin Heidelberg,2012:221-238.[DOI:10.1007/978-3-642-31680-7_12]
[23]AGRAWAL R,SRIKANT R.Privacy-preserving data mining[J].ACM SIGMOD Record,2000,29(2):439-450.[DOI:10.1145/335191.335438]
[24]KANTARDZIC M.Data Mining:Concepts,Models,Methods and Algorithms[M].Second Edition.John Wiley&Sons,Inc.and IEEE Press,2011:300-326.
[25]AGGARWAL C C.Privacy preserving data mining[J].Application Research of Computers,2008,9(8):616-621.[DOI:10.1007/s00145-001-0019-2]
[26]DU W L,ATALLAH M J.Protocols for secure remote database access with approximate matching[C].In:E-Commerce Security and Privacy,Advances in Information Security,Vol.2.Springer Boston,2001:87-111.[DOI:10.1007/978-1-4615-1467-1_6]
[27]CACHIN C.Efficient private bidding and auctions with an oblivious third party[C].In:Proceedings of the 6th ACM Conference on Computer and Communications Security.ACM,1999:120-127.[DOI:10.1145/319709.319726]
[28]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.
[29]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[C].In:Advances in Cryptology-EUROCRYPT 99.Springer Berlin Heidelberg,1999:223-238.[DOI:10.1007/3-540-48910-X_16]
[30]YANG B.Foundations of Modern Cryptography[M].Beijing:Tsinghua University Press,2015:106-110.杨波.现代密码学基础[M].北京:清华大学出版社,2015:106-110.
[31]BH P,CHANDRAVATHI D,ROJA P P.Encoding and decoding of a message in the implementation of elliptic curve cryptography using Koblitz’s method[J].International Journal on Computer Science and Engineering,2010,2(5):1904-1907.
[32]DESMEDT Y,FRANKEL Y.Threshold cryptosystems[C].In:Advances in Cryptology-CRYPTO’89.Springer New York,1990:307-315.[DOI:10.1007/3-540-57220-1_47]
[33]LONG Y,CHEN K F,MAO X P.New constructions of dynamic threshold cryptosystem[J].Journal of Shanghai Jiao Tong University(Science),2014,19:431-435.[DOI:10.1007/s12204-014-1520-8]