实用安全两方计算及其在基因组序列比对中的应用
|
摘要
安全两方计算(secure two-party computation)是密码学领域中的一个重要研究方向.作为安全多方计算中的一个特殊情形,安全两方计算中参与计算的实体仅为两方.相比于三方及更多参与方的情况,安全两方计算不仅在理论研究方面更具挑战性,在应用研究方面也具有更加广泛的应用场景.近年来,安全两方计算在实用性方面的研究取得了飞速发展,不仅在通用协议构造的效率上取得了重要突破,而且在涉及数据隐私计算的各个应用领域得到了广泛关注,比如基因组数据的隐私保护等.本文介绍了安全两方计算的基本概念、基本工具等基础知识,简要概述了安全两方计算近年来在实用性方面取得的重要研究成果,并重点介绍了安全两方计算在基因组序列比对中的应用及其研究进展.为了更加清晰地介绍相关研究进展,本文从安全两方计算的两个主要构造方法 (即同态加密和混乱电路)出发,分别给出了基于这两种不同底层工具的研究脉络.此外,本文指出了现阶段基于安全两方计算的基因组序列比对研究中存在的几点不足,并分析了未来可能的研究方向.
Secure two-party computation is an important research direction in cryptography. As a special case of secure multi-party computation, secure two-party computation involves only two participants. Compared with the cases of three or more parties, secure two-party computation is more challenging in theory and has a wider range of applications. In recent years, research on practical secure two-party computation has achieved rapid development. Development has made important breakthroughs in the efficiency of generic protocol construction, and has received extensive attention in various applications involving data privacy computation, such as privacy-preserving genomic data analysis. This paper introduces basic concepts and tools of secure two-party computation, and gives a brief overview of some important research results of secure two-party computation in recent years.In addition, the application of secure two-party computation in genomic sequence comparison and its research progress is summarized. For a clear introduction on related work, we start with introducing two major construction techniques(i.e., homomorphic encryption and garbled circuit), and give a clear development direction. In addition, the existing deficiencies in this research area and some possible research directions are pointed out.
Secure two-party computation is an important research direction in cryptography. As a special case of secure multi-party computation, secure two-party computation involves only two participants. Compared with the cases of three or more parties, secure two-party computation is more challenging in theory and has a wider range of applications. In recent years, research on practical secure two-party computation has achieved rapid development. Development has made important breakthroughs in the efficiency of generic protocol construction, and has received extensive attention in various applications involving data privacy computation, such as privacy-preserving genomic data analysis. This paper introduces basic concepts and tools of secure two-party computation, and gives a brief overview of some important research results of secure two-party computation in recent years.In addition, the application of secure two-party computation in genomic sequence comparison and its research progress is summarized. For a clear introduction on related work, we start with introducing two major construction techniques(i.e., homomorphic encryption and garbled circuit), and give a clear development direction. In addition, the existing deficiencies in this research area and some possible research directions are pointed out.
引文
[1]AYDAY E,HUBAUX J P.Privacy and security in the genomic era[C].In:Proceedings of the 2016 ACMSIGSAC Conference on Computer and Communications Security(CCS’16).ACM,2016:1863-1865.[DOI:10.1145/2976749.2976751]
[2]GYMREK M,MCGUIRE A L,GOLAN D,et al.Identifying personal genomes by surname inference[J].Science,2013,339(6117):321-324.[DOI:10.1126/science.1229566]
[3]ATALLAH M J,KERSCHBAUM F,DU W.Secure and private sequence comparisons[C].In:Proceedings of the2003 ACM Workshop on Privacy in the Electronic Society.ACM,2003:39-44.[DOI:10.1145/1005140.1005147]
[4]YAO A C.Protocols for secure computations[C].In:Proceedings of 23rd Annual Symposium on Foundations of Computer Science(FOCS’82).IEEE,1982:160-164.[DOI:10.1109/sfcs.1982.38]
[5]LINDELL Y,PINKAS B.An efficient protocol for secure two-party computation in the presence of malicious adversaries[C].In:Advances in Cryptology-EUROCRYPT 2007.Springer Berlin Heidelberg,2007:52-78.[DOI:10.1007/978-3-540-72540-4_4]
[6]JIANG H,XU Q L.Secure multiparty computation in cloud computing[J].Journal of Computer Research and Development,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]蒋瀚,徐秋亮.基于云计算服务的安全多方计算[J].计算机研究与发展,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]
[7]JIANG H,XU Q L.Advances in key techniques of practical secure multi-party computation[J].Journal of Computer Research and Development,2015,52(10):2247-2257.[DOI:10.7544/issn1000-1239.2015.20150763]蒋瀚,徐秋亮.实用安全多方计算协议关键技术研究进展[J].计算机研究与发展,2015,52(10):2247-2257.[DOI:10.7544/issn1000-1239.2015.20150763]
[8]ZAHUR S,ROSULEK M,EVANS D.Two halves make a whole[C].In:Advances in Cryptology-EUROCRYPT2015,Part II.Springer Berlin Heidelberg,2015:220-250.[DOI:10.1007/978-3-662-46803-6_8]
[9]WANG X,RANELLUCCI S,KATZ J.Authenticated garbling and efficient maliciously secure two-party computation[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:21-37.[DOI:10.1145/3133956.3134053]
[10]FAN X,GANESH C,KOLESNIKOV V.Hashing garbled circuits for free[C].In:Advances in CryptologyEUROCRYPT 2017,Part III.Springer Cham,2017:456-485.[DOI:10.1007/978-3-319-56617-7_16]
[11]GARG S,SRINIVASAN A.Adaptively secure garbling with near optimal online complexity[C].In:Advances in Cryptology-EUROCRYPT 2018,Part II.Springer Cham,2018:535-565.[DOI:10.1007/978-3-319-78375-8_18]
[12]LINDELL Y,YANAI A.Fast garbling of circuits over 3-valued logic[C].In:Public-Key Cryptography-PKC2018,Part I.Springer Cham,2018:620-643.[DOI:10.1007/978-3-319-76578-5_21]
[13]ZHU R Y,HUANG Y,KATZ J,et al.The cut-and-choose game and its application to cryptographic protocols[C].In:Proceedings of 25th USENIX Security Symposium.Austin,TX,USA.2016:1085-1100.
[14]ZHU R Y,HUANG Y.Cost-aware cut-and-choose games with applications in cryptography and prefix-free codes[J].IACR Cryptology ePrint Archive,2017:2017/174.
[15]KOLESNIKOV V,NIELSEN J B,ROSULEK M,et al.DUPLO:Unifying cut-and-choose for garbled circuits[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:3-20.[DOI:10.1145/3133956.3133991]
[16]ZHU R Y,HUANG Y.JIMU:Faster LEGO-based secure computation using additive homomorphic Hashes[C].In:Advances in Cryptology-ASIACRYPT 2017,Part II.Springer Cham,2017:529-572.[DOI:10.1007/978-3-319-70697-9_19]
[17]ASHAROV G,LINDELL Y,SCHNEIDER T,et al.More efficient oblivious transfer extensions[J].Journal of Cryptology,2017,30(3):805-858.[DOI:10.1007/s00145-016-9236-6]
[18]SCHOLL P.Extending oblivious transfer with low communication via key-homomorphic PRFs[C].In:Public-Key Cryptography-PKC 2018,Part I.Springer Cham,2018:554-583.[DOI:10.1007/978-3-319-76578-5_19]
[19]ZOHNER M.Faster Oblivious Transfer Extension and Its Impact on Secure Computation[D].Technische University,Darmstadt,2017.
[20]HUANG Y,KATZ J,KOLESNIKOV V,et al.Amortizing garbled circuits[C].In:Advances in CryptologyCRYPTO 2014,Part II.Springer Berlin Heidelberg,2014:458-475.[DOI:10.1007/978-3-662-44381-1_26]
[21]LINDELL Y,RIVA B.Cut-and-choose Yao-based secure computation in the online/offline and batch settings[C].In:Advances in Cryptology-CRYPTO 2014,Part II.Springer Berlin Heidelberg,2014:476-494.[DOI:10.1007/978-3-662-44381-1_27]
[22]LINDELL Y,RIVA B.Blazing fast 2PC in the offline/online setting with security for malicious adversaries[C].In:Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security(CCS’15).ACM,2015:579-590.[DOI:10.1145/2810103.2813666]
[23]RINDAL P,ROSULEK M.Faster malicious 2-party secure computation with online/offline dual execution[C].In:Proceedings of 25th USENIX Security Symposium.Austin,TX,USA.2016:297-314.
[24]MOHASSEL P,ROSULEK M.Non-interactive secure 2PC in the offline/online and batch settings[C].In:Advances in Cryptology-EUROCRYPT 2017,Part III.Springer Cham,2017:425-455.[DOI:10.1007/978-3-319-56617-7_15]
[25]YERUKHIMOVICH A,GROCE A,MALOZEMOFF A J,et al.CompGC:Efficient offline/online semi-honest two-party computation[R].MIT Lincoln Laboratory,Lexington,MA,USA,2017.
[26]KREUTER B,SHELAT A,SHEN C H.Billion-gate secure computation with malicious adversaries[C].In:Proceedings of 21th USENIX Security Symposium.Bellevue,WA,USA.2012:285-300.
[27]BOYLE E,CHUNG K M,PASS R.Large-scale secure computation:Multi-party computation for(parallel)RAMprograms[C].In:Advances in Cryptology-CRYPTO 2015,Part II.Springer Berlin Heidelberg,2015:742-762.[DOI:10.1007/978-3-662-48000-7_36]
[28]ZHU R,HUANG Y,CASSEL D.Pool:Scalable on-demand secure computation service against malicious adversaries[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:245-257.[DOI:10.1145/3133956.3134070]
[29]DAMG?RD I,PASTRO V,SMART N,et al.Multiparty computation from somewhat homomorphic encryption[C].In:Advances in Cryptology-CRYPTO 2012.Springer Berlin Heidelberg,2012:643-662.[DOI:10.1007/978-3-642-32009-5_38]
[30]DAMG?RD I,ZAKARIAS S.Constant-overhead secure computation of Boolean circuits using preprocessing[C].In:Theory of Cryptography-TCC 2013.Springer Berlin Heidelberg,2013:621-641.[DOI:10.1007/978-3-642-36594-2_35]
[31]DAMG?RD I,NIELSEN J B,NIELSEN M,et al.The tinytable protocol for 2-party secure computation,or:Gate-scrambling revisited[C].In:Advances in Cryptology-CRYPTO 2017,Part I.Springer Cham,2017:167-187.[DOI:10.1007/978-3-319-63688-7_6]
[32]LINDELL Y.Fast secure two-party ECDSA signing[C].In:Advances in Cryptology-CRYPTO 2017,Part II.Springer Cham,2017:613-644.[DOI:10.1007/978-3-319-63715-0_21]
[33]DAMG?RD I,ZAKARIAS R.Fast oblivious AES:A dedicated application of the MiniMac protocol[C].In:Progress in Cryptology-AFRICACRYPT 2016.Springer Cham,2016:245-264.[DOI:10.1007/978-3-319-31517-1_13]
[34]KELLER M,ORSINI E,ROTARU D,et al.Faster secure multi-party computation of AES and DES using lookup tables[C].In:Applied Cryptography and Network Security-ACNS 2017.Springer Cham,2017:229-249.[DOI:10.1007/978-3-319-61204-1_12]
[35]COUTEAU G,PETERS T,POINTCHEVAL D.Encryption switching protocols[C].In:Advances in CryptologyCRYPTO 2016,Part I.Springer Berlin Heidelberg,2016:308-338.[DOI:10.1007/978-3-662-53018-4_12]
[36]CASTAGNOS G,IMBERT L,LAGUILLAUMIE F.Encryption switching protocols revisited:Switching modulo p[C].In:Advances in Cryptology-CRYPTO 2017,Part I.Springer Cham,2017:255-287.[DOI:10.1007/978-3-319-63688-7_9]
[37]NAVEED M,AYDAY E,CLAYTON E W,et al.Privacy and security in the genomic era[J].arXiv preprint arXiv:1405.1891,2014.
[38]AKGüN M,BAYRAK A O,OZER B,et al.Privacy preserving processing of genomic data:A survey[J].Journal of Biomedical Informatics,2015,56:103-111.[DOI:10.1016/j.jbi.2015.05.022]
[39]NAVEED M,AYDAY E,CLAYTON E W,et al.Privacy in the genomic era[J].ACM Computing Surveys(CSUR),2015,48(1):6.[DOI:10.1145/2767007]
[40]OHNO-MACHADO L,JIANG X Q,TANG H X,et al.Secure genome analysis competition[C/OL].In:IDASHPrivacy&Security Workshop 2018.http://www.humangenomeprivacy.org/2018/index.html.
[41]GRIBSKOV M,MCLACHLAN A D,EISENBERG D.Profile analysis:Detection of distantly related proteins[J].Proceedings of the National Academy of Sciences of the United States of America,1987,84(13):4355-4358.[DOI:10.1073/pnas.84.13.4355]
[42]GENTRY C.Fully homomorphic encryption using ideal lattices[C].In:Proceedings of the Forty-first Annual ACMSymposium on Theory of Computing(STOC’09).ACM,2009:169-178.[DOI:10.1145/1536414.1536440]
[43]CRAMER R,DAMG?RD I,NIELSEN J B.Multiparty computation from threshold homomorphic encryption[C].In:Advances in Cryptology-EUROCRYPT 2001.Springer Berlin Heidelberg,2001:280-300.[DOI:10.1007/3-540-44987-6_18]
[44]DAMG?RD I,NIELSEN J B.Universally composable efficient multiparty computation from threshold homomorphic encryption[C].In:Advances in Cryptology-CRYPTO 2003.Springer Berlin Heidelberg,2003:247-264.[DOI:10.1007/978-3-540-45146-4_15]
[45]BENDLIN R,DAMG?RD I,ORLANDI C,et al.Semi-homomorphic encryption and multiparty computation[C].In:Advances in Cryptology-EUROCRYPT 2011.Springer Berlin Heidelberg,2011:169-188.[DOI:10.1007/978-3-642-20465-4_11]
[46]LóPEZ-ALT A,TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C].In:Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing(STOC’12).ACM,2012:1219-1234.[DOI:10.1145/2213977.2214086]
[47]PETER A,TEWS E,KATZENBEISSER S.Efficiently outsourcing multiparty computation under multiple keys[J].IEEE Transactions on Information Forensics and Security(TIFS),2013,8(12):2046-2058.[DOI:10.1109/tifs.2013.2288131]
[48]MUKHERJEE P,WICHS D.Two round multiparty computation via multi-key FHE[J].IACR Cryptology ePrint Archive,2015:2015/345.
[49]WAGNER R A,FISCHER M J.The string-to-string correction problem[J].Journal of the ACM(JACM),1974,21(1):168-173.[DOI:10.1145/321796.321811]
[50]ATALLAH M J,LI J.Secure outsourcing of sequence comparisons[J].International Journal of Information Security,2005,4(4):277-287.[DOI:10.1007/11423409_5]
[51]CHEON J H,KIM M,LAUTER K.Homomorphic computation of edit distance[C].In:Financial Cryptography and Data Security-FC 2015.Springer Berlin Heidelberg,2015:194-212.[DOI:10.1007/978-3-662-48051-9_15]
[52]CHEN X,LI J,MA J,et al.New algorithms for secure outsourcing of modular exponentiations[C].In:Computer Security-ESORICS 2012.Springer Berlin Heidelberg,2012:541-556.[DOI:10.1007/978-3-642-33167-1_31]
[53]CHEN X,LI J,MA J,et al.New algorithms for secure outsourcing of modular exponentiations[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2386-2396.[DOI:10.1109/TPDS.2013.180]
[54]WANG Y,WU Q,WONG D S,et al.Securely outsourcing exponentiations with single untrusted program for cloud storage[C].In:Computer Security-ESORICS 2014,Part I.Springer Cham,2014:326-343.[DOI:10.1007/978-3-319-11203-9_19]
[55]YE J,XU Z,DING Y.Secure outsourcing of modular exponentiations in cloud and cluster computing[J].Cluster Computing,2016,19(2):811-820.[DOI:10.1007/s10586-016-0571-z]
[56]NIE H,CHEN X,LI J,et al.Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming[C].In:Proceedings of 2014 IEEE 28th International Conference on Advanced Information Networking and Applications(AINA).IEEE,2014:591-596.[DOI:10.1109/aina.2014.147]
[57]HU X,PEI D Y,TANG C M,el al.Veriable and secure outsourcing of matrix calculation and its application[J].SCIENTIA SINICA Informationis,2013,43(7):842-852.[DOI:10.1360/zf2013-43-7-842]胡杏,裴定一,唐春明,等.可验证安全外包矩阵计算及其应用[J].中国科学:信息科学,2013,43(7):842-852.[DOI:10.1360/zf2013-43-7-842]
[58]SUN M H,GONG Z.A privacy-preserving outsourcing set union protocol[J].Journal of Cryptologic Research,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]孙茂华,宫哲.一种保护隐私集合并集外包计算协议[J].密码学报,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]
[59]LI S D,ZHOU S F,GUO Y M,et.al.Secure set computing in cloud environment[J].Journal of Software,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]李顺东,周素芳,郭奕旻,等.云环境下集合隐私计算[J].软件学报,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]
[60]MA X,LI J,ZHANG F.Refereed computation delegation of private sequence comparison in cloud computing[J].International Journal of Network Security,2015,17(6):743-753.
[61]YAO A C.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science(FOCS’86).IEEE,1986:162-167.[DOI:10.1109/sfcs.1986.25]
[62]KOLESNIKOV V,SCHNEIDER T.Improved garbled circuit:Free XOR gates and applications[C].In:Automata,Languages and Programming-ICALP 2008.Springer Berlin Heidelberg,2008:486-498.[DOI:10.1007/978-3-540-70583-3_40]
[63]LINDELL Y,PINKAS B,SMART N P.Implementing two-party computation efficiently with security against malicious adversaries[C].In:Security and Cryptography for Networks-SCN 2008.Springer Berlin Heidelberg,2008:2-20.[DOI:10.1007/978-3-540-85855-3_2]
[64]PINKAS B,SCHNEIDER T,SMART N P,et al.Secure two-party computation is practical[C].In:Advances in Cryptology-ASIACRYPT 2009.Springer Berlin Heidelberg,2009:250-267.[DOI:10.1007/978-3-642-10366-7_15]
[65]HUANG Y,EVANS D,KATZ J,et al.Faster secure two-party computation using garbled circuits[C].In:Proceedings of 20th USENIX Security Symposium.San Francisco,CA,USA.2011:1-16.
[66]BELLARE M,HOANG V T,ROGAWAY P.Foundations of garbled circuits[C].In:Proceedings of the2012 ACM Conference on Computer and Communications Security(CCS’12).ACM,2012:784-796.[DOI:10.1145/2382196.2382279]
[67]PINKAS B.Fair secure two-party computation[C].In:Advances in Cryptology-EUROCRYPT 2003.Springer Berlin Heidelberg,2003:87-105.[DOI:10.1007/3-540-39200-9_6]
[68]LINDELL Y,PINKAS B.Secure two-party computation via cut-and-choose oblivious transfer[C].In:Theory of Cryptography-TCC 2011.Springer Berlin Heidelberg,2011:329-346.[DOI:10.1007/978-3-642-19571-6_20]
[69]LINDELL Y.Fast cut-and-choose based protocols for malicious and covert adversaries[C].In:Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:1-17.[DOI:10.1007/978-3-642-40084-1_1]
[70]HUANG Y,KATZ J,EVANS D.Efficient secure two-party computation using symmetric cut-and-choose[C].In:Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:18-35.[DOI:10.1007/978-3-642-40084-1_2]
[71]ZHAO C,JIANG H,WEI X,et al.Cut-and-choose bilateral oblivious transfer and its application[C].In:Proceedings of 2015 IEEE TrustCom/BigDataSE/ISPA.IEEE,2015,Vol.1:384-391.[DOI:10.1109/Trustcom.2015.398]
[72]LINDELL Y.Fast cut-and-choose-based protocols for malicious and covert adversaries[J].Journal of Cryptology,2016,29(2):456-490.[DOI:10.1007/s00145-015-9198-0]
[73]WEI X,JIANG H,ZHAO C,et al.Fast cut-and-choose bilateral oblivious transfer for malicious adversaries[C].In:Proceedings of TrustCom/BigDataSE/ISPA.IEEE,2016:418-425.[DOI:10.1109/trustcom.2016.0092]
[74]ZHAO C,JIANG H,XU Q,et al.Fast two-output secure computation with optimal error probability[J].Chinese Journal of Electronics,2017,26(5):933-941.[DOI:10.1049/cje.2016.06.025]
[75]AFSHAR A,MOHASSEL P,ROSULEK M.Efficient maliciously secure two party computation for mixed programs[J].IACR Cryptology ePrint Archive,2017:2017/062.
[76]KAMARA S,MOHASSEL P,RAYKOVA M.Outsourcing multi-party computation[J].IACR Cryptology ePrint Archive,2011:2011/272.
[77]KAMARA S,MOHASSEL P,RIVA B.Salus:A system for server-aided secure function evaluation[C].In:Proceedings of the 2012 ACM Conference on Computer and Communications Security(CCS’12).ACM,2012:797-808.[DOI:10.1145/2382196.2382280]
[78]CARTER H,MOOD B,TRAYNOR P,et al.Secure outsourced garbled circuit evaluation for mobile devices[C].In:Proceedings of 22th USENIX Security Symposium.Washington,DC,USA.2013:289-304.
[79]CARTER H,LEVER C,AND TRAYNOR P.Whitewash:Outsourcing garbled circuit generation for mobile devices[C].In:Proceedings of the 30th Annual Computer Security Applications Conference(ACSAC 2014).ACM,2014:266-275.[DOI:10.1145/2664243.2664255]
[80]MOOD B,GUPTA D,BUTLER K,et al.Reuse it or lose it:More efficient secure computation through reuse of encrypted values[C].In:Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security(CCS’14).ACM,2014:582-596.[DOI:10.1145/2660267.2660285]
[81]JAKOBSEN T P,NIELSEN J B,ORLANDI C.A framework for outsourcing of secure computation[C].In:Proceedings of the 6th Edition of the ACM Workshop on Cloud Computing Security.ACM,2014:81-92.[DOI:10.1109/cloud.2014.145]
[82]CARTER H,MOOD B,TRAYNOR P,et al.Outsourcing secure two-party computation as a black box[J].Security and Communication Networks,2016,9(14):2261-2275.[DOI:10.1002/sec.1486]
[83]JHA S,KRUGER L,SHMATIKOV V.Towards practical privacy for genomic computation[C].In:2008 29th IEEE Symposium on Security and Privacy(S&P).IEEE,2008:216-230.[DOI:10.1109/sp.2008.34]
[84]BLANTON M,ATALLAH M J,FRIKKEN K B,et al.Secure and efficient outsourcing of sequence comparisons[C].In:European Symposium on Research in Computer Security-ESORICS 2012.Springer Berlin Heidelberg,2012:505-522.[DOI:10.1007/978-3-642-33167-1_29]
[85]BLANTON M,BAYATBABOLGHANI F.Efficient server-aided secure two-party function evaluation with applications to genomic computation[J].Proceedings on Privacy Enhancing Technologies,2016,2016(4):144-164.[DOI:10.1515/popets-2016-0033]
[86]WANG X S,HUANG Y,ZHAO Y,et al.Efficient genome-wide,privacy-preserving similar patient query based on private edit distance[C].In:Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security(CCS’15).ACM,2015:492-503.[DOI:10.1145/2810103.2813725]
[87]ASHAROV G,HALEVI S,LINDELL Y,et al.Privacy-preserving search of similar patients in genomic data[J].IACR Cryptology ePrint Archive,2017:2017/144.[DOI:10.1515/popets-2018-0034]
[88]AL AZIZ M M,ALHADIDI D,MOHAMMED N.Secure approximation of edit distance on genomic data[J].BMCMedical Genomics,2017,10(2):41.[DOI:10.1186/s12920-017-0279-9]
[89]ZHU R,HUANG Y.Efficient privacy-preserving general edit distance and beyond[J].IACR Cryptology ePrint Archive,2017:2017/683.http://eprint.iacr.org/2017/683.
[2]GYMREK M,MCGUIRE A L,GOLAN D,et al.Identifying personal genomes by surname inference[J].Science,2013,339(6117):321-324.[DOI:10.1126/science.1229566]
[3]ATALLAH M J,KERSCHBAUM F,DU W.Secure and private sequence comparisons[C].In:Proceedings of the2003 ACM Workshop on Privacy in the Electronic Society.ACM,2003:39-44.[DOI:10.1145/1005140.1005147]
[4]YAO A C.Protocols for secure computations[C].In:Proceedings of 23rd Annual Symposium on Foundations of Computer Science(FOCS’82).IEEE,1982:160-164.[DOI:10.1109/sfcs.1982.38]
[5]LINDELL Y,PINKAS B.An efficient protocol for secure two-party computation in the presence of malicious adversaries[C].In:Advances in Cryptology-EUROCRYPT 2007.Springer Berlin Heidelberg,2007:52-78.[DOI:10.1007/978-3-540-72540-4_4]
[6]JIANG H,XU Q L.Secure multiparty computation in cloud computing[J].Journal of Computer Research and Development,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]蒋瀚,徐秋亮.基于云计算服务的安全多方计算[J].计算机研究与发展,2016,53(10):2152-2162.[DOI:10.7544/issn1000-1239.2016.20160685]
[7]JIANG H,XU Q L.Advances in key techniques of practical secure multi-party computation[J].Journal of Computer Research and Development,2015,52(10):2247-2257.[DOI:10.7544/issn1000-1239.2015.20150763]蒋瀚,徐秋亮.实用安全多方计算协议关键技术研究进展[J].计算机研究与发展,2015,52(10):2247-2257.[DOI:10.7544/issn1000-1239.2015.20150763]
[8]ZAHUR S,ROSULEK M,EVANS D.Two halves make a whole[C].In:Advances in Cryptology-EUROCRYPT2015,Part II.Springer Berlin Heidelberg,2015:220-250.[DOI:10.1007/978-3-662-46803-6_8]
[9]WANG X,RANELLUCCI S,KATZ J.Authenticated garbling and efficient maliciously secure two-party computation[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:21-37.[DOI:10.1145/3133956.3134053]
[10]FAN X,GANESH C,KOLESNIKOV V.Hashing garbled circuits for free[C].In:Advances in CryptologyEUROCRYPT 2017,Part III.Springer Cham,2017:456-485.[DOI:10.1007/978-3-319-56617-7_16]
[11]GARG S,SRINIVASAN A.Adaptively secure garbling with near optimal online complexity[C].In:Advances in Cryptology-EUROCRYPT 2018,Part II.Springer Cham,2018:535-565.[DOI:10.1007/978-3-319-78375-8_18]
[12]LINDELL Y,YANAI A.Fast garbling of circuits over 3-valued logic[C].In:Public-Key Cryptography-PKC2018,Part I.Springer Cham,2018:620-643.[DOI:10.1007/978-3-319-76578-5_21]
[13]ZHU R Y,HUANG Y,KATZ J,et al.The cut-and-choose game and its application to cryptographic protocols[C].In:Proceedings of 25th USENIX Security Symposium.Austin,TX,USA.2016:1085-1100.
[14]ZHU R Y,HUANG Y.Cost-aware cut-and-choose games with applications in cryptography and prefix-free codes[J].IACR Cryptology ePrint Archive,2017:2017/174.
[15]KOLESNIKOV V,NIELSEN J B,ROSULEK M,et al.DUPLO:Unifying cut-and-choose for garbled circuits[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:3-20.[DOI:10.1145/3133956.3133991]
[16]ZHU R Y,HUANG Y.JIMU:Faster LEGO-based secure computation using additive homomorphic Hashes[C].In:Advances in Cryptology-ASIACRYPT 2017,Part II.Springer Cham,2017:529-572.[DOI:10.1007/978-3-319-70697-9_19]
[17]ASHAROV G,LINDELL Y,SCHNEIDER T,et al.More efficient oblivious transfer extensions[J].Journal of Cryptology,2017,30(3):805-858.[DOI:10.1007/s00145-016-9236-6]
[18]SCHOLL P.Extending oblivious transfer with low communication via key-homomorphic PRFs[C].In:Public-Key Cryptography-PKC 2018,Part I.Springer Cham,2018:554-583.[DOI:10.1007/978-3-319-76578-5_19]
[19]ZOHNER M.Faster Oblivious Transfer Extension and Its Impact on Secure Computation[D].Technische University,Darmstadt,2017.
[20]HUANG Y,KATZ J,KOLESNIKOV V,et al.Amortizing garbled circuits[C].In:Advances in CryptologyCRYPTO 2014,Part II.Springer Berlin Heidelberg,2014:458-475.[DOI:10.1007/978-3-662-44381-1_26]
[21]LINDELL Y,RIVA B.Cut-and-choose Yao-based secure computation in the online/offline and batch settings[C].In:Advances in Cryptology-CRYPTO 2014,Part II.Springer Berlin Heidelberg,2014:476-494.[DOI:10.1007/978-3-662-44381-1_27]
[22]LINDELL Y,RIVA B.Blazing fast 2PC in the offline/online setting with security for malicious adversaries[C].In:Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security(CCS’15).ACM,2015:579-590.[DOI:10.1145/2810103.2813666]
[23]RINDAL P,ROSULEK M.Faster malicious 2-party secure computation with online/offline dual execution[C].In:Proceedings of 25th USENIX Security Symposium.Austin,TX,USA.2016:297-314.
[24]MOHASSEL P,ROSULEK M.Non-interactive secure 2PC in the offline/online and batch settings[C].In:Advances in Cryptology-EUROCRYPT 2017,Part III.Springer Cham,2017:425-455.[DOI:10.1007/978-3-319-56617-7_15]
[25]YERUKHIMOVICH A,GROCE A,MALOZEMOFF A J,et al.CompGC:Efficient offline/online semi-honest two-party computation[R].MIT Lincoln Laboratory,Lexington,MA,USA,2017.
[26]KREUTER B,SHELAT A,SHEN C H.Billion-gate secure computation with malicious adversaries[C].In:Proceedings of 21th USENIX Security Symposium.Bellevue,WA,USA.2012:285-300.
[27]BOYLE E,CHUNG K M,PASS R.Large-scale secure computation:Multi-party computation for(parallel)RAMprograms[C].In:Advances in Cryptology-CRYPTO 2015,Part II.Springer Berlin Heidelberg,2015:742-762.[DOI:10.1007/978-3-662-48000-7_36]
[28]ZHU R,HUANG Y,CASSEL D.Pool:Scalable on-demand secure computation service against malicious adversaries[C].In:Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(CCS’17).ACM,2017:245-257.[DOI:10.1145/3133956.3134070]
[29]DAMG?RD I,PASTRO V,SMART N,et al.Multiparty computation from somewhat homomorphic encryption[C].In:Advances in Cryptology-CRYPTO 2012.Springer Berlin Heidelberg,2012:643-662.[DOI:10.1007/978-3-642-32009-5_38]
[30]DAMG?RD I,ZAKARIAS S.Constant-overhead secure computation of Boolean circuits using preprocessing[C].In:Theory of Cryptography-TCC 2013.Springer Berlin Heidelberg,2013:621-641.[DOI:10.1007/978-3-642-36594-2_35]
[31]DAMG?RD I,NIELSEN J B,NIELSEN M,et al.The tinytable protocol for 2-party secure computation,or:Gate-scrambling revisited[C].In:Advances in Cryptology-CRYPTO 2017,Part I.Springer Cham,2017:167-187.[DOI:10.1007/978-3-319-63688-7_6]
[32]LINDELL Y.Fast secure two-party ECDSA signing[C].In:Advances in Cryptology-CRYPTO 2017,Part II.Springer Cham,2017:613-644.[DOI:10.1007/978-3-319-63715-0_21]
[33]DAMG?RD I,ZAKARIAS R.Fast oblivious AES:A dedicated application of the MiniMac protocol[C].In:Progress in Cryptology-AFRICACRYPT 2016.Springer Cham,2016:245-264.[DOI:10.1007/978-3-319-31517-1_13]
[34]KELLER M,ORSINI E,ROTARU D,et al.Faster secure multi-party computation of AES and DES using lookup tables[C].In:Applied Cryptography and Network Security-ACNS 2017.Springer Cham,2017:229-249.[DOI:10.1007/978-3-319-61204-1_12]
[35]COUTEAU G,PETERS T,POINTCHEVAL D.Encryption switching protocols[C].In:Advances in CryptologyCRYPTO 2016,Part I.Springer Berlin Heidelberg,2016:308-338.[DOI:10.1007/978-3-662-53018-4_12]
[36]CASTAGNOS G,IMBERT L,LAGUILLAUMIE F.Encryption switching protocols revisited:Switching modulo p[C].In:Advances in Cryptology-CRYPTO 2017,Part I.Springer Cham,2017:255-287.[DOI:10.1007/978-3-319-63688-7_9]
[37]NAVEED M,AYDAY E,CLAYTON E W,et al.Privacy and security in the genomic era[J].arXiv preprint arXiv:1405.1891,2014.
[38]AKGüN M,BAYRAK A O,OZER B,et al.Privacy preserving processing of genomic data:A survey[J].Journal of Biomedical Informatics,2015,56:103-111.[DOI:10.1016/j.jbi.2015.05.022]
[39]NAVEED M,AYDAY E,CLAYTON E W,et al.Privacy in the genomic era[J].ACM Computing Surveys(CSUR),2015,48(1):6.[DOI:10.1145/2767007]
[40]OHNO-MACHADO L,JIANG X Q,TANG H X,et al.Secure genome analysis competition[C/OL].In:IDASHPrivacy&Security Workshop 2018.http://www.humangenomeprivacy.org/2018/index.html.
[41]GRIBSKOV M,MCLACHLAN A D,EISENBERG D.Profile analysis:Detection of distantly related proteins[J].Proceedings of the National Academy of Sciences of the United States of America,1987,84(13):4355-4358.[DOI:10.1073/pnas.84.13.4355]
[42]GENTRY C.Fully homomorphic encryption using ideal lattices[C].In:Proceedings of the Forty-first Annual ACMSymposium on Theory of Computing(STOC’09).ACM,2009:169-178.[DOI:10.1145/1536414.1536440]
[43]CRAMER R,DAMG?RD I,NIELSEN J B.Multiparty computation from threshold homomorphic encryption[C].In:Advances in Cryptology-EUROCRYPT 2001.Springer Berlin Heidelberg,2001:280-300.[DOI:10.1007/3-540-44987-6_18]
[44]DAMG?RD I,NIELSEN J B.Universally composable efficient multiparty computation from threshold homomorphic encryption[C].In:Advances in Cryptology-CRYPTO 2003.Springer Berlin Heidelberg,2003:247-264.[DOI:10.1007/978-3-540-45146-4_15]
[45]BENDLIN R,DAMG?RD I,ORLANDI C,et al.Semi-homomorphic encryption and multiparty computation[C].In:Advances in Cryptology-EUROCRYPT 2011.Springer Berlin Heidelberg,2011:169-188.[DOI:10.1007/978-3-642-20465-4_11]
[46]LóPEZ-ALT A,TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C].In:Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing(STOC’12).ACM,2012:1219-1234.[DOI:10.1145/2213977.2214086]
[47]PETER A,TEWS E,KATZENBEISSER S.Efficiently outsourcing multiparty computation under multiple keys[J].IEEE Transactions on Information Forensics and Security(TIFS),2013,8(12):2046-2058.[DOI:10.1109/tifs.2013.2288131]
[48]MUKHERJEE P,WICHS D.Two round multiparty computation via multi-key FHE[J].IACR Cryptology ePrint Archive,2015:2015/345.
[49]WAGNER R A,FISCHER M J.The string-to-string correction problem[J].Journal of the ACM(JACM),1974,21(1):168-173.[DOI:10.1145/321796.321811]
[50]ATALLAH M J,LI J.Secure outsourcing of sequence comparisons[J].International Journal of Information Security,2005,4(4):277-287.[DOI:10.1007/11423409_5]
[51]CHEON J H,KIM M,LAUTER K.Homomorphic computation of edit distance[C].In:Financial Cryptography and Data Security-FC 2015.Springer Berlin Heidelberg,2015:194-212.[DOI:10.1007/978-3-662-48051-9_15]
[52]CHEN X,LI J,MA J,et al.New algorithms for secure outsourcing of modular exponentiations[C].In:Computer Security-ESORICS 2012.Springer Berlin Heidelberg,2012:541-556.[DOI:10.1007/978-3-642-33167-1_31]
[53]CHEN X,LI J,MA J,et al.New algorithms for secure outsourcing of modular exponentiations[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2386-2396.[DOI:10.1109/TPDS.2013.180]
[54]WANG Y,WU Q,WONG D S,et al.Securely outsourcing exponentiations with single untrusted program for cloud storage[C].In:Computer Security-ESORICS 2014,Part I.Springer Cham,2014:326-343.[DOI:10.1007/978-3-319-11203-9_19]
[55]YE J,XU Z,DING Y.Secure outsourcing of modular exponentiations in cloud and cluster computing[J].Cluster Computing,2016,19(2):811-820.[DOI:10.1007/s10586-016-0571-z]
[56]NIE H,CHEN X,LI J,et al.Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming[C].In:Proceedings of 2014 IEEE 28th International Conference on Advanced Information Networking and Applications(AINA).IEEE,2014:591-596.[DOI:10.1109/aina.2014.147]
[57]HU X,PEI D Y,TANG C M,el al.Veriable and secure outsourcing of matrix calculation and its application[J].SCIENTIA SINICA Informationis,2013,43(7):842-852.[DOI:10.1360/zf2013-43-7-842]胡杏,裴定一,唐春明,等.可验证安全外包矩阵计算及其应用[J].中国科学:信息科学,2013,43(7):842-852.[DOI:10.1360/zf2013-43-7-842]
[58]SUN M H,GONG Z.A privacy-preserving outsourcing set union protocol[J].Journal of Cryptologic Research,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]孙茂华,宫哲.一种保护隐私集合并集外包计算协议[J].密码学报,2016,3(2):114-125.[DOI:10.13868/j.cnki.jcr.000114]
[59]LI S D,ZHOU S F,GUO Y M,et.al.Secure set computing in cloud environment[J].Journal of Software,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]李顺东,周素芳,郭奕旻,等.云环境下集合隐私计算[J].软件学报,2016,27(6):1549-1565.[DOI:10.13328/j.cnki.jos.004996]
[60]MA X,LI J,ZHANG F.Refereed computation delegation of private sequence comparison in cloud computing[J].International Journal of Network Security,2015,17(6):743-753.
[61]YAO A C.How to generate and exchange secrets[C].In:Proceedings of 27th Annual Symposium on Foundations of Computer Science(FOCS’86).IEEE,1986:162-167.[DOI:10.1109/sfcs.1986.25]
[62]KOLESNIKOV V,SCHNEIDER T.Improved garbled circuit:Free XOR gates and applications[C].In:Automata,Languages and Programming-ICALP 2008.Springer Berlin Heidelberg,2008:486-498.[DOI:10.1007/978-3-540-70583-3_40]
[63]LINDELL Y,PINKAS B,SMART N P.Implementing two-party computation efficiently with security against malicious adversaries[C].In:Security and Cryptography for Networks-SCN 2008.Springer Berlin Heidelberg,2008:2-20.[DOI:10.1007/978-3-540-85855-3_2]
[64]PINKAS B,SCHNEIDER T,SMART N P,et al.Secure two-party computation is practical[C].In:Advances in Cryptology-ASIACRYPT 2009.Springer Berlin Heidelberg,2009:250-267.[DOI:10.1007/978-3-642-10366-7_15]
[65]HUANG Y,EVANS D,KATZ J,et al.Faster secure two-party computation using garbled circuits[C].In:Proceedings of 20th USENIX Security Symposium.San Francisco,CA,USA.2011:1-16.
[66]BELLARE M,HOANG V T,ROGAWAY P.Foundations of garbled circuits[C].In:Proceedings of the2012 ACM Conference on Computer and Communications Security(CCS’12).ACM,2012:784-796.[DOI:10.1145/2382196.2382279]
[67]PINKAS B.Fair secure two-party computation[C].In:Advances in Cryptology-EUROCRYPT 2003.Springer Berlin Heidelberg,2003:87-105.[DOI:10.1007/3-540-39200-9_6]
[68]LINDELL Y,PINKAS B.Secure two-party computation via cut-and-choose oblivious transfer[C].In:Theory of Cryptography-TCC 2011.Springer Berlin Heidelberg,2011:329-346.[DOI:10.1007/978-3-642-19571-6_20]
[69]LINDELL Y.Fast cut-and-choose based protocols for malicious and covert adversaries[C].In:Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:1-17.[DOI:10.1007/978-3-642-40084-1_1]
[70]HUANG Y,KATZ J,EVANS D.Efficient secure two-party computation using symmetric cut-and-choose[C].In:Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:18-35.[DOI:10.1007/978-3-642-40084-1_2]
[71]ZHAO C,JIANG H,WEI X,et al.Cut-and-choose bilateral oblivious transfer and its application[C].In:Proceedings of 2015 IEEE TrustCom/BigDataSE/ISPA.IEEE,2015,Vol.1:384-391.[DOI:10.1109/Trustcom.2015.398]
[72]LINDELL Y.Fast cut-and-choose-based protocols for malicious and covert adversaries[J].Journal of Cryptology,2016,29(2):456-490.[DOI:10.1007/s00145-015-9198-0]
[73]WEI X,JIANG H,ZHAO C,et al.Fast cut-and-choose bilateral oblivious transfer for malicious adversaries[C].In:Proceedings of TrustCom/BigDataSE/ISPA.IEEE,2016:418-425.[DOI:10.1109/trustcom.2016.0092]
[74]ZHAO C,JIANG H,XU Q,et al.Fast two-output secure computation with optimal error probability[J].Chinese Journal of Electronics,2017,26(5):933-941.[DOI:10.1049/cje.2016.06.025]
[75]AFSHAR A,MOHASSEL P,ROSULEK M.Efficient maliciously secure two party computation for mixed programs[J].IACR Cryptology ePrint Archive,2017:2017/062.
[76]KAMARA S,MOHASSEL P,RAYKOVA M.Outsourcing multi-party computation[J].IACR Cryptology ePrint Archive,2011:2011/272.
[77]KAMARA S,MOHASSEL P,RIVA B.Salus:A system for server-aided secure function evaluation[C].In:Proceedings of the 2012 ACM Conference on Computer and Communications Security(CCS’12).ACM,2012:797-808.[DOI:10.1145/2382196.2382280]
[78]CARTER H,MOOD B,TRAYNOR P,et al.Secure outsourced garbled circuit evaluation for mobile devices[C].In:Proceedings of 22th USENIX Security Symposium.Washington,DC,USA.2013:289-304.
[79]CARTER H,LEVER C,AND TRAYNOR P.Whitewash:Outsourcing garbled circuit generation for mobile devices[C].In:Proceedings of the 30th Annual Computer Security Applications Conference(ACSAC 2014).ACM,2014:266-275.[DOI:10.1145/2664243.2664255]
[80]MOOD B,GUPTA D,BUTLER K,et al.Reuse it or lose it:More efficient secure computation through reuse of encrypted values[C].In:Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security(CCS’14).ACM,2014:582-596.[DOI:10.1145/2660267.2660285]
[81]JAKOBSEN T P,NIELSEN J B,ORLANDI C.A framework for outsourcing of secure computation[C].In:Proceedings of the 6th Edition of the ACM Workshop on Cloud Computing Security.ACM,2014:81-92.[DOI:10.1109/cloud.2014.145]
[82]CARTER H,MOOD B,TRAYNOR P,et al.Outsourcing secure two-party computation as a black box[J].Security and Communication Networks,2016,9(14):2261-2275.[DOI:10.1002/sec.1486]
[83]JHA S,KRUGER L,SHMATIKOV V.Towards practical privacy for genomic computation[C].In:2008 29th IEEE Symposium on Security and Privacy(S&P).IEEE,2008:216-230.[DOI:10.1109/sp.2008.34]
[84]BLANTON M,ATALLAH M J,FRIKKEN K B,et al.Secure and efficient outsourcing of sequence comparisons[C].In:European Symposium on Research in Computer Security-ESORICS 2012.Springer Berlin Heidelberg,2012:505-522.[DOI:10.1007/978-3-642-33167-1_29]
[85]BLANTON M,BAYATBABOLGHANI F.Efficient server-aided secure two-party function evaluation with applications to genomic computation[J].Proceedings on Privacy Enhancing Technologies,2016,2016(4):144-164.[DOI:10.1515/popets-2016-0033]
[86]WANG X S,HUANG Y,ZHAO Y,et al.Efficient genome-wide,privacy-preserving similar patient query based on private edit distance[C].In:Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security(CCS’15).ACM,2015:492-503.[DOI:10.1145/2810103.2813725]
[87]ASHAROV G,HALEVI S,LINDELL Y,et al.Privacy-preserving search of similar patients in genomic data[J].IACR Cryptology ePrint Archive,2017:2017/144.[DOI:10.1515/popets-2018-0034]
[88]AL AZIZ M M,ALHADIDI D,MOHAMMED N.Secure approximation of edit distance on genomic data[J].BMCMedical Genomics,2017,10(2):41.[DOI:10.1186/s12920-017-0279-9]
[89]ZHU R,HUANG Y.Efficient privacy-preserving general edit distance and beyond[J].IACR Cryptology ePrint Archive,2017:2017/683.http://eprint.iacr.org/2017/683.