Privacy preserving Hamming distance computing problem of DNA sequences

doi:10.11772/j.issn.1001-9081.2019020247

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (9): 2636-2640.DOI: 10.11772/j.issn.1001-9081.2019020247

• Cyber security • Previous Articles Next Articles

Privacy preserving Hamming distance computing problem of DNA sequences

MA Minyao1,2, XU Yi1,2, LIU Zhuo1,2

1. School of Mathematics and Big Data, Guizhou Education University, Guiyang Guizhou 550018, China;
2. Key Laboratory of Cyberspace Security, Guizhou Education University, Guiyang Guizhou 550018, China

Received:2019-02-25 Revised:2019-05-12 Online:2019-09-10 Published:2019-06-17
Supported by:
This work is partially supported by the Science and Technology Foundation Project of Guizhou Province (QianKeHeJiChu[2016]1115, QianKeHeJiChu[2019]1249), the Youth Science and Technology Talent Project of Guizhou Provincial Education Department (QianJiaoHe-KY-Zi[2016]220, QianJiaoHe-KY-Zi[2017]210, QianJiaoHe-KY-Zi [2018]260).

隐私保护DNA序列汉明距离计算问题

马敏耀^1,2, 徐艺^1,2, 刘卓^1,2

1. 贵州师范学院数学与大数据学院, 贵阳 550018;
2. 贵州师范学院网络空间安全重点实验室, 贵阳 550018

通讯作者: 马敏耀
作者简介:马敏耀(1979-),男,贵州威宁人,副教授,博士,CCF会员,主要研究方向:密码学、信息安全;徐艺(1986-),女,贵州石阡人,讲师,博士研究生,主要研究方向:密码学、信息安全;刘卓(1987-),女,河南驻马店人,讲师,博士研究生,主要研究方向:密码学、信息安全。
基金资助:
贵州省科学技术基金计划项目（黔科合基础[2016]1115，黔科合基础[2019]1249）；贵州省教育厅青年科技人才成长项目（黔教合KY字[2016]220，黔教合KY字[2017]210，黔教合KY字[2018]260）。

Abstract

Abstract:

DNA sequences carry important biological information of human bodies, how to compare multiple DNA sequences correctly with privacy preserving is an important problem. To a certain extent, Hamming distance characterizes the similarity between two DNA sequences. Therefore, the privacy preserving Hamming distance computing problem of DNA sequences was researched. First of all, the "0-1 Coding" of the DNA sequence was defined, which codes the DNA sequence with length n to a 0-1 string with length 4n, proving that the Hamming distance of two DNA sequences is a half of the Hamming distance of their "0-1 Coding" strings. Then, with the help of this conclusion, with the Goldwasser-Micali (GM) encryption algorithm taken as main encryption tool, a secure two-party computation protocol for computing the Hamming distance of two DNA sequences was proposed. It was shown that the protocol is both secure and correct under semi-honest attacker model. The proof of security based on a simulator was given. After then, the efficiency of the protocol was analyzed.

Key words: Hamming distance, DNA sequence, privacy preserving, secure multi-party computation, homomorphic encryption

摘要：

DNA序列承载着人体重要的生物学信息，如何在保护隐私的情况下正确地对不同的DNA序列进行比对，成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度，在保护隐私的情况下，研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。

关键词: 汉明距离, DNA序列, 隐私保护, 安全多方计算, 同态加密

CLC Number:

TP309

MA Minyao, XU Yi, LIU Zhuo. Privacy preserving Hamming distance computing problem of DNA sequences[J]. Journal of Computer Applications, 2019, 39(9): 2636-2640.

马敏耀, 徐艺, 刘卓. 隐私保护DNA序列汉明距离计算问题[J]. 计算机应用, 2019, 39(9): 2636-2640.

References

[1] YAO A C. Protocols for secure computations[C]//SFCS'82:Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 1982:160-164.
[2] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game-a completeness theorem for protocols with honest majority[C]//STOC'87:Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York:ACM, 1987:218-229.
[3] BEN-OR M, GOLDWASSER S, WIGDERSON A. Completeness theorems for non-cryptographic fault-tolerant distributed computation[C]//STOC'88:Proceedings of the 29th Annual ACM Symposium on Theory of Computing. New York:ACM, 1988:1-10.
[4] YAO A C. How to generate and exchange secrets[C]//SFCS'86:Proceedings of the 27th Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 1986:162-167.
[5] ZHOU Y H, SHI W M, YANG Y G. A quantum protocol for millionaire problem with continuous variables[J]. Communications in Theoretical Physics, 2014, 61(4):452-456.
[6] MOHASSEL P, WEINREB E. Efficient secure linear algebra in the presence of covert or computationally unbounded adversaries[C]//Proceedings of the Annual International Cryptology Conference, LNCS 5157. Berlin:Springer, 2008:481-496.
[7] SHI R, MU Y, ZHONG H, et al. An efficient quantum scheme for private set intersection[J]. Quantum Information Processing, 2016, 15(1):363-371.
[8] CHUN J Y, HONG D, JEONG I R, et al. Privacy-preserving disjunctive normal form operations on distributed sets[J]. Information Sciences, 2013, 231:113-122.
[9] RINDAL P, ROSULEK M. Improved private set intersection against malicious adversaries[C]//Proceedings of the 2017 Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 10210. Berlin:Springer, 2017:235-259.
[10] 罗小双,杨晓元,王绪安.一类可抵抗恶意攻击的隐私集合交集协议[J].计算机应用,2017,37(6):1593-1598.(LUO X S, YANG X Y, WANG X A. A private set intersection protocol against malicious attack[J]. Journal of Computer Applications, 2017, 37(6):1593-1598.)
[11] 张恩,金刚刚.基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J].计算机应用,2018,38(8):2256-2260.(ZHANG E, JIN G G. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter[J]. Journal of Computer Applications, 2018, 38(8):2256-2260.)
[12] 马敏耀,陈松良,左羽.基于Goldwasser-Micali加密系统的隐私交集基数协议研究[J].计算机应用研究,2018,35(9):2748-2751.(MA M Y, CHEN S L, ZUO Y. Research on private set intersection cardinality protocol based on Goldwasser-Micali encryption system[J]. Application Research of Computers, 2018, 35(9):2748-2751.)
[13] MOHASSEL P, RINDAL P. ABY3:a mixed protocol framework for machine learning[C]//CCS'18:Proceedings of ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2018:35-52.
[14] GOLDWASSER S, MICALI S. Probabilistic encryption & how to play mental poker keeping secret all partial information[C]//STOC'82:Proceedings of the 14th Annual ACM Symposium on Theory of Computing. New York:ACM, 1982:365-377.
[15] GOLDREICH O. Foundations of Cryptography:Basic Applications[M]. Cambridge:Cambridge University Press, 2004:620-621.

Privacy preserving Hamming distance computing problem of DNA sequences

隐私保护DNA序列汉明距离计算问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHENG Shangwen, LIU Yao, ZHOU Tanping, YANG Xiaoyuan. Optimized CKKS scheme based on learning with errors problem [J]. Journal of Computer Applications, 2021, 41(6): 1723-1728.
[2]	ZHANG Lihua, WANG Xinyi, HU Fangzhou, HUANG Yang, BAI Jiayi. Data sharing model of smart grid based on double consortium blockchains [J]. Journal of Computer Applications, 2021, 41(4): 963-969.
[3]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[4]	WANG Yunye, CHENG Yage, JIA Zhijuan, FU Junjun, YANG Yanyan, HE Yuchu, MA Wei. Auditable signature scheme for blockchain based on secure multi-party [J]. Journal of Computer Applications, 2020, 40(9): 2639-2645.
[5]	MA Minyao, LIU Zhuo, XU Yi, WU Lian. Private-preserving determination problem of integer-interval positional relationship [J]. Journal of Computer Applications, 2020, 40(9): 2657-2664.
[6]	CHE Xiaoliang, ZHOU Haonan, ZHOU Tanping, LI Ningbo, YANG Xiaoyuan. Decryption structure of multi-key homomorphic encryption scheme based on NTRU [J]. Journal of Computer Applications, 2020, 40(7): 1959-1964.
[7]	MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship [J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.
[8]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[9]	YU Qingfei, TU Guangsheng, LI Ningbo, ZHOU Tanping. Multi-hop multi-policy attributed-based fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(8): 2326-2332.
[10]	ZHANG Shuxuan, KANG Haiyan, YAN Han. Privacy preserving for social network relational data based on Skyline computing [J]. Journal of Computer Applications, 2019, 39(5): 1394-1399.
[11]	TU Guangsheng, YANG Xiaoyuan, ZHOU Tanping. Efficient identity-based multi-identity fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(3): 750-755.
[12]	SHI Zhicai, WANG Yihan, ZHANG Xiaomei, CHEN Shanshan, CHEN Jiwei. Provable radio frequency identification authentication protocol with scalability [J]. Journal of Computer Applications, 2019, 39(3): 774-778.
[13]	XIU Chunbo, MA Yunfei, PAN Xiaonan. Image feature point matching method based on distance fusion [J]. Journal of Computer Applications, 2019, 39(11): 3158-3162.
[14]	LI Xinchun, CAO Zhiqiang, LIN Sen, ZHANG Chunhua. Palmprint and palmvein image fusion recognition algorithm based on super-wavelet domain [J]. Journal of Computer Applications, 2018, 38(8): 2205-2210.
[15]	ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.