(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210558985.4 (22)申请日 2022.05.22 (71)申请人 深圳前海新心数字科技有限公司 地址 518000 广东省深圳市前海合作区前 湾一路1号A栋201室 (72)发明人 谈扬　 (74)专利代理 机构 深圳市百瑞专利商标事务所 (普通合伙) 44240 专利代理师 金辉 (51)Int.Cl. H04L 9/00(2022.01) H04L 9/08(2006.01) G06F 21/62(2013.01) (54)发明名称 一种基于同态加密的隐私基因序列距离矩 阵计算方法 (57)摘要 本发明提供一种基于同态加密的隐私基因 序列距离矩阵计算方法， 包括重复的编码： 密钥 生成和碱基加密、 密文运算、 密文解密、 统计距离 等步骤， 直到计算出参与方之间所有基因序列的 距离分数； 进一步计算基因序列组的距离矩阵以 及最终生 成进化树。 本发明使用高效的半同态加 密算法Paillier， 实现安全 求解两方基因序列之 间的距离矩阵， 并以此进行进化 树分析。 权利要求书2页 说明书5页 附图1页 CN 114978468 A 2022.08.30 CN 114978468 A 1.一种基于同态加密的隐私基因序列距离矩阵计算方法， 其特 征在于： 包括以下步骤： 步骤1、 编码： 将A、 B 双方需要做比较的碱基编码成整数； 步骤2、 密钥生成和碱基加密： 其中A方生成同态加密公、 私钥， 并将本地基因序列编码 后整数做同态加密， 同时将密文和公钥发给B方； 步骤3、 密文运算： B方通过同态加密对 同位置碱基密文进行隐私求相等协议中的密文 计算， 生成计算后的密文， 并发送给A方； 步骤4、 密文解密： A方将B方发回的密文解密； 步骤5、 统计距离： 统计时， 若在同位置A方， B方的碱基相同， 解密结果为一 固定常数； 若 同位置A方， B方的碱基不相同， 那么解密结果 不等于这个固定常数， 且大小在一定范围内； 步骤6、 重复上述步骤， 直到计算出参与方之间所有基因序列的距离分数； 进一步计算 基因序列组的距离矩阵以及最终生成进化 树。 2.根据权利要求1所述的基于同态加密的隐私基因序列距离矩阵计算方法， 其特征在 于： 步骤1中碱基编码成整数， 编码规则如下： 步骤1‑1、 4大碱基， 编码如下： A:1 C:2 G:3 T:4； 步骤1‑2、 碱基缺省值编码， 缺省值 N,n,‑:1000； 步骤1‑3、 其他异常值： 与字母A的距离+4； A方本地某条基因序列X编码为(x1,x2, …,xn),B方本地基因序列Y编码为(y1,y2, …, yn)。 3.根据权利要求1所述的基于同态加密的隐私基因序列距离矩阵计算方法， 其特征在 于： 步骤2中A方选择同态加密算法Pai llier及安全参数， 并生成公私钥pk， sk。 4.根据权利要求3所述的基于同态加密的隐私基因序列距离矩阵计算方法， 其特征在 于： 所述的步骤2中， A方将本地基因序列编码后整数做同态加密时， A方使用公钥pk对本地 的基因序列 X＝(x1,…,xn)进行加密生成(Enc(x1),Enc(x2), …,Enc(xn))， 将这些密文以 及pk发送给B方； 所述的步骤3中， 密文运 算包括： B方接收A方发送过来的公钥pk， 使用公钥pk加密本地基因序列Y＝(y1, …,yn)生成密 文(Enc(y1),Enc(y2), …,Enc(yn) )； B方计算{ki＝(Enc(xi) ‑Enc(yi))*v1+v0}并将{ki}发送给A方； 其中i＝1, …,n， v0为 固定值5， v1为10 0‑500之间的随机值。 5.根据权利要求4所述的基于同态加密的隐私基因序列距离矩阵计算方法， 其特征在 于： 在B方将{ki}发送给A方之前， 要将其 顺序随机打散 。 6.根据权利要求5所述的基于同态加密的隐私基因序列距离矩阵计算方法， 其特征在 于： 所述的步骤4中， A方将B方发回的密文解密包括： A方使用私钥sk解密ki， v＝Dec(ki),统 计不等于5且小于60000的v的个数count， 确定两个基因序列之间距离分数等于score＝权　利　要　求　书 1/2 页 2 CN 114978468 A 2count/n。权　利　要　求　书 2/2 页 3 CN 114978468 A 3