[發明專利]基于多方安全計算的隱私保護序列NJ樹構建方法及系統

在審

• 申請號: 202210565096.0
• 申請日: 2022-05-23
• 公開（公告）號: CN115102693A
• 公開（公告）日: 2022-09-23
• 發明（設計）人: 劉洋;普艷紅
• 申請（專利權）人: 清華大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;G16B20/00;G06F21/62
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 張金玲

本發明提供基于多方安全計算的隱私保護序列NJ樹構建方法及系統，包括：基于對齊的基因序列，第一參與方和第二參與方在明文條件下計算距離矩陣中各自持有序列對應部分；在第一參與方和第二參與方計算完成后，將計算結果通過秘密共享協議將份額分享給對方；根據雙方秘密共享的結果，第一參與方和第二參與方在原對齊序列秘密共享條件下聯合計算距離矩陣中剩余部分，并通過秘密共享協議輸出距離矩陣計算份額給各方；通過得到的距離矩陣計算結果，在雙方只持有距離矩陣的份額矩陣條件下進行NJ樹構建。本發明解決了現有NJ樹構建過程中容易出現基因序列泄露的問題，以實現在NJ樹構建過程中對基因序列的隱私保護。

技術領域

本發明涉及基因工程技術領域，尤其涉及基于多方安全計算的隱私保護序列NJ樹構建方法及系統。

背景技術

在基因工程當中，面對眾多的基因序列，需要觀察相互堿基序列之間的關聯度、相似度等信息，比對之后才能進行更深入的研究，目前為了比對堿基序列的關聯度，一般通過建立NJ樹的形式完成相似度的分析。

NJ樹的構建過程是：先假定一棵無根星狀樹，再兩兩比較，將親源近的聚成聚合分類群，然后再將聚合分類群看作一個整體與另外的在進行聚合分類，這樣重復下去，直至構出完整的NJ樹。但是，在傳統構建NJ樹過程中，均是在明文條件下進行，難以保證基因序列的安全性和私密性，容易造成基因信息泄露，導致嚴重后果。

發明內容

本發明提供基于多方安全計算的隱私保護序列NJ樹構建方法及系統，用以解決現有NJ樹構建過程中容易出現基因序列泄露的問題，以實現在NJ樹構建過程中對基因序列的隱私保護。

本發明提供基于多方安全計算的隱私保護序列NJ樹構建方法，包括：

基于對齊的基因序列，第一參與方和第二參與方在明文條件下計算距離矩陣中各自持有序列對應部分；

在第一參與方和第二參與方計算完成后，將計算結果通過秘密共享協議將份額分享給對方；

根據雙方秘密共享的結果，第一參與方和第二參與方在原對齊序列秘密共享條件下聯合計算距離矩陣中剩余部分，并通過秘密共享協議輸出距離矩陣計算份額給各方；

通過得到的距離矩陣計算結果，在雙方只持有距離矩陣的份額矩陣條件下進行NJ樹構建。

根據本發明提供的基于多方安全計算的隱私保護序列NJ樹構建方法，所述基于對齊的基因序列，第一參與方和第二參與方在明文條件下計算距離矩陣中各自持有序列對應部分，具體包括：

所述第一參與方在明文條件下計算擁有的m條序列對應的距離矩陣的得分；

所述第二參與方在明文條件下計算擁有的n條序列對應的距離矩陣的得分；

第一參與方和第二參與方單獨計算完成后，將計算結果通過秘密共享協議將份額發送給對方。

根據本發明提供的基于多方安全計算的隱私保護序列NJ樹構建方法，所述在第一參與方和第二參與方計算完成后，將計算結果通過秘密共享協議將份額分享給對方，具體包括：

在整數秘密共享過程中，第一參與方生成第一隨機數，并將第一隨機數發送給第二參與方，自己保留序列中扣除第一隨機數的剩余部分；

第二參與方生成第二隨機數，并將第二隨機數發送給第一參與方，自己保留序列中扣除第二隨機數的剩余部分。

根據本發明提供的基于多方安全計算的隱私保護序列NJ樹構建方法，所述根據雙方秘密共享的結果，第一參與方和第二參與方在原對齊序列秘密共享條件下聯合計算距離矩陣中剩余部分，并通過秘密共享協議輸出距離矩陣計算份額給各方，具體包括：

第一參與方和第二參與方聯合計算距離矩陣中剩余部分后，輸出整體距離矩陣的秘密份額給各方，針對整體距離矩陣的結果中的每個元素與2¹⁵做乘積，進行小數表示。