[發(fā)明專利]一種安全多方數(shù)值型記錄匹配方法

有效

• 申請?zhí)枺?/td>: 201810067980.5
• 申請日: 2018-01-24
• 公開（公告）號: CN108334577B
• 公開（公告）日: 2020-02-07
• 發(fā)明（設計）人: 申德榮;韓姝敏;聶鐵錚;寇月;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/215
• 分類號: G06F16/215;G06F16/2458;G06F16/28;G06F21/62
• 代理公司: 21234 沈陽優(yōu)普達知識產(chǎn)權代理事務所(特殊普通合伙)
• 代理人: 張志偉

1.一種安全多方數(shù)值型記錄匹配方法，其特征在于：包括以下步驟：

步驟1.多方數(shù)據(jù)源數(shù)值型記錄的加密；給定參與方個數(shù)P，利用類模運算smod對數(shù)值型記錄加密，P個參與方統(tǒng)一公共匹配屬性A＝{a_n|1≤n≤d}；

數(shù)值型記錄的定義：1)某一條記錄中全部屬性的屬性值均為數(shù)值型，則該記錄為數(shù)值型記錄；2)某一條記錄中部分屬性的屬性值為數(shù)值型，則提取全部或部分數(shù)值型屬性即可視為數(shù)值型記錄；

步驟1-1.數(shù)值型記錄加密密鑰生成；參與方P₁生成P個密鑰K_i，分配給P個參與方，其中1≤i≤P，每個密鑰包含d個子密鑰K_i＝{k_in|1≤n≤d}分別加密數(shù)值屬性{a_i1,a_i2,…,a_id}，每個數(shù)值屬性的加密密鑰不同，加強了數(shù)據(jù)的安全性；

步驟1-2.數(shù)值型記錄加密；給定一條數(shù)值型記錄r_i及匹配屬性{a_i1,a_i2,…,a_id}，加密密鑰為K_i＝{k_i1,k_i2,…,k_id}，利用類模運算加密記錄，加密方式及類模運算如下：

Enc(V(a_id))＝smod{(V(a_id)+k_id*p),p*q} (1)

其中V(a_id)表示記錄r_i中屬性a_d的值，m代表原文信息，p和q均為質(zhì)數(shù)；

各參與方利用各自密鑰加密記錄，然后各方記錄做笛卡爾積運算生成候選記錄對；

步驟2.迭代優(yōu)化地處理候選記錄對；迭代優(yōu)化地處理候選記錄對，并逐漸地輸出匹配成功的候選記錄對，方法如下：

步驟2-1.各數(shù)值型屬性中最大、最小值安全查詢；給定來自于P個參與方的P條記錄，安全地查找出P條記錄各數(shù)值型屬性中的最大、最小值，給定一個數(shù)值型屬性a_n，已知該屬性下加密后的各屬性值C_in＝Enc(r_i(a_n))，1≤i≤P，若加密后的屬性值具有原值的大小關系，則查找出密文中的最大、最小值解密后即為原值中的最大、最小值；為了滿足若r₁(a_n)≥r₂(a_n)，則Enc(r₁(a_n))≥Enc(r₂(a_n))，且若Enc(r₁(a_n))≥Enc(r₂(a_n))，則r₁(a_n)≥r₂(a_n)，經(jīng)推理記錄r₁，r₂的密鑰k₁，k₂需滿足如下關系：

k₂＝k₁+hq (3)

h為整數(shù)；接著將各參與方加密后的密文傳給匹配單元，由于類模運算具有同態(tài)減法的性質(zhì)，因此密文在匹配單元中進行安全減法計算，查找出密文中的最大、最小值；

步驟2-2.優(yōu)化地對候選記錄對進行相似度計算；計算候選記錄對中P條記錄的相似度，利用步驟2-1得到P條數(shù)值型記錄在各屬性下的密文最大、最小值，通過安全減法，計算P條記錄在各屬性下的相似度，若均大于等于閾值則P條記錄匹配成功；否則，匹配失敗；如(4)所示，

式(4)中r₁,r₂,r_i,…,r_P代表來自P個參與方的記錄，a_nmax,a_nmin分別代表屬性n中的最大最小值，θ_n代表屬性n中的相似度閾值；這是因為若最大、最小值的相似度大于閾值，證明可得P條記錄在該屬性下的任意兩個屬性值的相似度都大于閾值，證明如下：

若sim(a_nmin,a_nmax)>θ_n,可以推出sim(a,b)>θ_n,a_nmin≤a,b≤a_nmax；

若a>b,sim(a,b)＝1-(a-b)/d_max，在等式(5)中可知；

當a＝a_nmax,b＝a_nmin；

sim(a,b)取得最小值與sim(a_nmin,a_nmax)相等；

因此,sim(a,b)>θ_n，

同理可證，當a<b or a＝b,sim(a,b)>θ_n；

兩個數(shù)值n₁，n₂的相似度計算公式表達如下：

其中d_max為兩個數(shù)值相差的最大差值；

最終將匹配成功的重復數(shù)據(jù)對象對輸出。