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

Privacy preserving Hamming distance computing problem of DNA sequences

作　　者：马敏耀 徐艺[1,2] 刘卓 MA Minyao;XU Yi;LIU Zhuo(School of Mathematics and Big Data,Guizhou Education University,Guiyang Guizhou 550018,China;Key Laboratory of Cyberspace Security,Guizhou Education University,Guiyang Guizhou 550018,China)

机构地区：[1]贵州师范学院数学与大数据学院,贵阳550018 [2]贵州师范学院网络空间安全重点实验室,贵阳550018

出　　处：《计算机应用》2019年第9期2636-2640,共5页journal of Computer Applications

基　　金：贵州省科学技术基金计划项目(黔科合基础[2016] 1115,黔科合基础[2019] 1249);贵州省教育厅青年科技人才成长项目(黔教合KY字[2016]220,黔教合KY字[2017]210,黔教合KY字[2018]260)~~

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

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构]