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

在審

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

1.基于多方安全計算的隱私保護序列NJ樹構建方法，其特征在于，包括：

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

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

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

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

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

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

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

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

3.根據權利要求1所述的基于多方安全計算的隱私保護序列NJ樹構建方法，其特征在于，所述在第一參與方和第二參與方計算完成后，將計算結果通過秘密共享協議將份額分享給對方，具體包括：

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

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

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

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

5.根據權利要求1所述的基于多方安全計算的隱私保護序列NJ樹構建方法，其特征在于，所述通過得到的距離矩陣計算結果，在雙方只持有距離矩陣的份額矩陣條件下進行NJ樹構建，具體包括：

雙方在份額矩陣條件下計算橫向差異矩陣，將整體距離矩陣進行標準化處理即可得到橫向差異矩陣，且橫向差異矩陣計算結果也通過秘密份額形式輸出給各方；

雙方在只持有橫向差異矩陣份額條件下計算選取距離最小的兩個節點；

將兩個節點連接產生新的節點，并更新新節點到其它未連接節點的距離；

重復以上步驟，雙方在秘密共享條件下不斷用新的節點連接合并原節點并更新距離，只到所有節點均連接在一起，即完成NJ樹構建。

6.根據權利要求5所述的基于多方安全計算的隱私保護序列NJ樹構建方法，其特征在于，所述將兩個節點連接到新的節點上并更新距離。具體包括：

選取的節點為f,g，f,g連接到新的節點u上，則f,g到新節點u距離計算公式為：

δ(g，u)＝d(f，g)-δ(f，u)。

7.一種基于多方安全計算的隱私保護序列NJ樹構建系統，其特征在于，所述系統包括：

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

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

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

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