[發明專利]隱私保護下的向量相似性判斷方法

有效

• 申請號: 201611145362.5
• 申請日: 2016-12-13
• 公開（公告）號: CN106788962B
• 公開（公告）日: 2020-04-14
• 發明（設計）人: 楊浩淼;何偉超;黃云帆;冉鵬;姚銘軒;金保隆
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L9/00
• 分類號: H04L9/00;G06F21/62;G06F21/32
• 代理公司: 成都希盛知識產權代理有限公司 51226
• 代理人: 濮云杉;楊冬

本發明涉及隱私保護下的向量相似性判斷方法，其中基于向量伸縮變換的隱私保護下的向量相似性判斷方法，包括：A.接收兩個標準向量x1、x2和待查詢向量x3；B.對x1、x2和x3進行伸縮，得到兩個標準輸出向量L1、L2和待查詢輸出向量L3；C.設置誤差閾值d后，分別計算||L1－L3||和||L2－L3||；D.比較||L1－L3||－||L2－L3||與d的大小關系，確定x3與x1或x2相似。本發明能夠在不公開向量每個維度的值的前提下，通過比較向量的模長高效的判斷向量之間的相似性，并且對密文比較的效率和明文比較對比，性能幾乎沒有下降。

技術領域

本發明涉及在隱私保護下的向量相似性判斷方法。

背景技術

在大數據時代，數據往往是被外包給第三方代理云的。然而在這個過程中用戶的數據可能隱含一些敏感信息，這直接使得隱私數據有泄漏的可能。解決這個問題的一種最直接的方式就是將數據加密之后發送到服務器端，然后服務器端在密文下實現機器學習，完成相關的數據挖掘算法。但是在這個過程中是比較困難的，比如實現密文下的比較。目前實現密文比較的方案都是基于整數密文的比較，從目前已有的方案來看效率是很低的。而在實際應用場景中，某些事物的特征往往可以用特征向量來表征。而在這個過程中，需要比較的往往是向量的某些屬性，比如夾角、模長、內積等等。比如基于生物特征的認證是通過用戶的生物特征，例如指紋、虹膜、DNA等來識別用戶的身份。首先用戶錄入其生物特征作為模板，當用戶要登錄系統，需要提供其生物特征和模板進行比對，如果足夠相似，則用戶通過系統的認證。另一方面，用戶的生物特征又事關用戶的隱私，需要對其保護。

在表征兩個向量之間的相似性的時候，可以用歐氏距離來度量兩者之間的相似性。在已有模板特征向量V＝(V₁,…,V_l)和用戶認證時的特征向量W＝(W₁,…,W_l)中的各個坐標盡可能多的匹配，來返回兩個向量的相似性。一種最常用的方法是計算兩個向量的歐式距離<V,W>＝∑_i(V_i-W_i)²，距離小者更相似。為了保護用戶的隱私，無論是向量V和向量W都應該加密。然而加密限制了數據的使用，服務器很難采用傳統的加密方法來比較哪兩個向量的歐氏距離更小。而全同態加密(Fully Homomorphic Encryption，FHE)在不解密的情況下能夠直接基于密文計算。于是一種可能的解決思路是使用向量的同態加密的方法來安全計算兩個密文歐氏距離：<V',W'>，用X'表示對X的加密。但是傳統的全同態加密都是基于整數的，它們對于向量的操作都是對向量的單維進行操作，效率極低。

除此之外，還可以使用內積來表征兩個向量之間的相似性。通過已有模板特征向量V＝(V₁,…,V_l)和用戶認證時的特征向量W＝(W₁,…,W_l)，來返回兩個向量的相似性分數。我們可以計算兩個向量的內積<V,W>＝∑_iV_i*W_i，距離大者更相似。同樣為了保護用戶的隱私，無論是向量V和向量W都應該加密。同樣的在密文下比較向量內積是困難的。

從實驗結果來看，目前的加密方案在對單維數據加密時是很快的，但對于乘法的同態運算需要計算的雙方多次交互。而在計算歐式距離或者向量內積的時候涉及到多次的乘法運算，這使得現有方法的效率很低。其次，對于密文的比較的處理涉及到非常復雜的計算，從已有的實驗結果來看，效率遠遠低于明文下的計算速度。

發明內容

本發明提供的隱私保護下的向量相似性判斷方法，在不公開向量每個維度的值的前提下，仍然可以通過比較向量的模長來判斷向量之間的相似性。