基于理想格的兩方隱私集合交集協議

趙宗渠 王書靜 湯永利 霍亞超 楊麗

摘 要：當前大多數現有的隱私集合交集（PSI）協議的安全性都是基于數論假設，而隨著量子計算理論的發展，基于數論假設的PSI協議將變得不再安全。針對該問題，利用格上函數加密的函數策略解密特性，通過二進制分解將參與方元素設計成符合LWE加法同態的向量形式，提出了一種基于理想格的半誠實安全的兩方PSI協議。安全性方面，使用基于環上錯誤學習問題（RLWE）的函數加密系統來構造PSI協議，實現了抗量子的安全性。效率方面，協議的通信復雜度為O（w+v），與參與方元素成正比，保證了較高的通信效率；并且利用理想格，減小了公鑰的大小，提高了存儲效率，降低了通信成本。

關鍵詞：隱私集合交集；量子攻擊；函數加密；理想格；錯誤學習問題

中圖分類號：TP309?? 文獻標志碼：A??? 文章編號：1001-3695（2023）12-043-3795-05

doi： 10.19734/j.issn.1001-3695.2023.03.0140

Twoparty privacy set intersection protocol based on ideal lattice

Abstract：Nowadays， the security of most existing PSI protocols are based on number theoretic assumptions， and with the development of quantum computing theory， these PSI protocols will become insecure. In order to solve this problem， this paper proposed a twoparty PSI protocol based on ideal lattice in semihonest model by using the decrypted features of function encryption on lattice and designing the party elements into vector forms conforming to LWE additive homomorphisms through binary decomposition. In terms of security， the PSI protocol achieves quantumresistant security by using a function cryptographic system based on the ring learning with errors（RLWE）. In terms of efficiency， the communication complexity of the proposed protocol is O（w+v） and proportional to the party elements， which ensures higher communication efficiency. And the use of ideal lattice reduces the size of the public key， which improves storage efficiency and reduces communication costs.

Key words：privacy set intersection; quantum attack; function encryption; ideal lattice; learning with errors

0 引言

隨著互聯網技術的快速發展和云計算技術的廣泛應用，共享信息的需求迅速增加。在很多現實場景中，這些信息往往需要在相互不信任的各方之間共享，當參與者希望對其輸入集進行秘密操作時，PSI就變得至關重要。PSI是安全多方計算［1］領域的特定應用問題，它允許持有各自私有集合的參與方去計算它們的交集元素，而不泄露除交集以外的任何信息。該技術能夠滿足人們利用隱私數據進行保密計算的需求，有效解決數據的保密性和共享性之間的矛盾。

在現實生活中，很多數據都可以用集合表示，并用集合間的隱私保護計算來處理一些涉及隱私計算的問題。因此在網絡迅速發展的今天，PSI協議具有重要意義，如隱私保護的近鄰檢測、隱私通信錄查找［2］、在線廣告實際效果計算［3］、基因序列匹配檢測［4］等。1986年，Meadows［5］提出了第一個基于公鑰加密體制的兩方PSI協議，該協議基于離散對數困難問題實現了DiffieHellman密鑰交換協議，將兩個集合的明文對比轉換為會話密鑰的對比，以此實現PSI的功能，比如隱私保護場景下選擇偏好的匹配。Freedman等人［6］提出了經典的基于公鑰的兩方PSI協議，該協議使用了不經意多項式求值技術（OPE）和同態加密技術。結合通信復雜度低的優點，Chen等人［7，8］提出使用基于RLWE的同態加密構造的PSI協議，該協議在隨機預言假設和半誠實模型下被證明是安全的。Kolesnikov等人［9］利用不經意偽隨機函數來計算交集，可消除PSI協議對參與方集合長度的依賴。Hazay［10］使用多項式求值進行可驗證委托的技術實現PSI協議。Andreea［11］提出了基于秘密共享的PSI協議的優化，實現了更高效的通信復雜度和運行時間。文獻［12］提出了基于混淆布隆過濾器（GBF）的PSI協議，該協議實現了線性通信復雜度和計算復雜度。

目前，大多數現有PSI協議的安全性都是基于數論假設，比如有限域離散對數問題和大整數因子分解問題。但是如同設計密碼體制一樣，一方面，大整數的模指數等運算的復雜性會導致協議的效率不高；另一方面，數論假設問題在量子攻擊下多項式時間內是不安全的。所以，一旦高效的量子計算機進入市場，基于數論難題的PSI協議將變得不再安全。為應對量子計算機給當前公鑰密碼體制帶來的巨大威脅，美國國家標準與技術研究院（NIST）于2016年面向全球征集抗量子密碼算法標準。在所有候選算法中，格密碼目前被廣泛認為是最有希望被標準化的后量子密碼。除了可以抵抗量子攻擊，基于格的加密體制也提供了其他有用的特性，比如最壞情況下的安全性、有效的并行計算和同態計算。因此，基于格的公鑰加密方案已經成為公鑰加密的重要部分。Debnath等人［13］提出了第一個基于星型拓撲結構的抗量子PSI協議，該協議使用布隆過濾器（BF）和基于LWE的公鑰加密構造，實現了在半誠實敵手模型下的安全性。

隨著密碼學的發展，新的公鑰密碼原語不斷被提出，其中包括函數加密（FE），作為一個廣義上的概念，函數加密包含了諸多已有和新提出的公鑰密碼機制，例如身份基加密（IBE）、屬性基加密（ABE）、內積加密（IPE）。FE最早由Boneh等人［14］正式提出，近年來獲得了巨大的進步［15］。FE采用函數策略對數據加密，是一種可支持訪問控制的數據加密方式。它是在傳統加密算法上構造的解密函數，只有滿足函數求解要求的參與方才能解密，而且解密結果并非簡單的原有明文，而是對明文的運算。近年，王生玉等人［16］在效率方面對經典ABE進行擴展，參與方私鑰對應一個訪問結構，密文對應一個屬性集合，當且僅當屬性集合滿足訪問結構才可成功解密，該方案將解密算法中的雙線性運算轉換成模冪運算或其他高效運算，從而將雙線性運算次數減少到常數來提升解密效率。

本文協議使用格上的左采樣算法為用戶生成密鑰，采用基于密文策略的函數加密算法來實現PSI半誠實模型的安全需求。即函數加密可以防止元素的真實內容在通信過程中被泄露；同時構造參與方交集不為空的條件解密函數，再根據解密是否成功來判斷隱私集合交集。本文主要貢獻如下：

a）通過設計合理的函數，構造出格上基于密文策略的函數加密系統構造PSI，實現抗量子的安全性。在函數加密基礎上，通過二進制分解，將參與方元素設計成符合LWE加法同態的向量形式，當且僅當元素集合滿足函數條件才可成功解密，繼而根據盲化消息判斷交集元素。與依賴于數論問題的公鑰密碼系統不同，基于格的密碼構造可在未來量子計算機和現實敵手的雙重威脅下，實現更完備的隱私保護需求。

b）使用理想格優化函數加密系統的參數，提高了存儲和通信效率。將基于理想格的函數加密系統代替q元格實現PSI，減小了公鑰的大小，降低了格表示的空間尺寸，提高了存儲效率。同時利用傅里葉變換（FFT）加速其運算，提高了整個系統的通信效率。

1 基礎知識

1.1 整數格和高斯分布

定義1 q元格。 設q是素數，A∈Zn×mq，u∈Ζnq，則：

Λuq（A）：={e∈Zm，Ae=u mod q}

Λuq（A）：={e∈Zm，Ae=0 mod q}

Λq（A）：={e∈Zm，s∈Znq使ATs=e mod q}

（1）

GPV08［17］提出了高斯采樣技術，其使用一組短基作為陷門而不泄露短基的任何信息。

引理2 設e∈Rk，y←DRkq，σ，當|〈e，y〉|的系數被看做（－q/2，q/2）中的整數時，以極大的概率滿足

對于模數q，定義多項式環Rq為R/qR=Z［X］/（q，Φ（X）），取一個n次整系數首一多項式Φ（X）=Xn+1作為模多項式。Zn到環Z［X］/（q，Φ（X））的同構：（r0，r1，…，rn－1）→ r0+r1x+…+rn－1xn－1，對于環Rq上由v1，…，vm生成的理想I，任意的f∈I可表示為v1，…，vm的模f（x）倍式組合：

f（x）=u1（x）g1（x）+…+um（x）gm（x）（mod Φ（x））

定義2 理想格。環Zn的理想I是格Zn的子格，稱這個子格為格Zn的理想格。

定義3 RLWE問題［18］。令s=s（x）∈Rq是一個均勻隨機的環元素，成為私鑰。與標準LWE類似，攻擊者的目的是從真正均勻的線性等式中區分被小噪聲擾亂過的線性等式。具體來說，被小噪聲擾亂過的線性抽樣的形式為（（a，b≈a·s）∈Rq×Rq）。a、b為公鑰，其中a為均勻隨機的，b的具體格式為bi=〈ai·s〉+ei，內積a·s被一些小的隨機錯誤所干擾。這些錯誤ei選自R上的一個特定分布，則已知公鑰求私鑰的問題就是RLWE問題。

定義4 決策RLWE［19，20］。給定一個具有m個均勻隨機多項式a=（a1，…，am）T∈Rmq的向量和b=as+e，其中s∈Rq，e∈DRm，σ，則如何區分（a，b=as+e）與（a，b）上的均勻分布問題就是決策RLWE問題。

1.2 格中陷門

1.3 左采樣算法

左采樣算法［23］在協議中用來采樣密鑰，下面是可以從特定格中采樣短向量的多項式時間算法。

算法1 SampleLeft（A，M1，TA，u，σ）→e：

輸入：多項式向量A，M1∈Rkq。其中rot（AT）T，rot（MT1）T∈Zn×nkq是滿秩矩陣，多項式u∈Rq，矩陣TA∈Rk×kq，TA是Λ⊥q（A）的陷門。

輸出：向量e∈R2k。

a）采樣一個隨機向量e2∈DRk，σ；

1.4 半誠實模型

設viewΠ1（X，Y）和viewΠ2（X，Y）分別是協議Π中P1和P2的視圖，outΠ（X，Y）是協議Π中P2的輸出，f（X，Y）是在理想功能函數中P2的輸出。如果存在概率多項式時間的模擬器SIM1和SIM2，使得對于所有的輸入X和Y，有

則協議Π是半誠實安全的。

2 隱私集合交集

本章將構造格上公鑰加密的隱私集合交集協議，該方案利用格上基于密文策略的函數加密系統實現PSI協議。設參與方P1、P2的元素分別為X={x1，…，xw}，Y={y1，…，yv}，其中xi和yj是l比特的字符串，消息空間M={0，1}nR，安全參數n∈Z+。散列函數H：{0，1}l→{0，1}n1，本文的安全性證明要求映射滿足單射，若x≠x′，則H（x）≠H（x′）。

該協議在函數加密基礎上將參與方元素做了特殊的處理，xi=（2l－2，…，20，－xi），i∈（1，w），yj=（yl－2j，…，y0j，1），j∈（1，v），xsi表示xi的第s個比特，yrj表示yj的第r個比特，即采用二進制分解的方式設計了參與方元素yj。例如l=5，xj=yj=12，xi=（8，4，2，1，－12），yj=（1，1，0，0，1）。解密時在對LWE進行同態操作時滿足加法運算的同態性，即“同態加”操作，使噪聲足夠小而不影響解密的正確性。元素xi不需要完全二進制化，當滿足內積〈xi，yj〉為零時，元素xi被消去，對解密沒有影響。故當參與方P1、P2中元素xi=yj，解密方密鑰中的yj與密文中的xi滿足內積為0，此時解密方可訪問密文，根據盲化的消息來判斷交集元素。系統模型如圖1所示。該協議由初始化和隱私集合求交兩個階段組成。

1）初始化階段

該方案將理想格應用于函數加密［24］系統，是一種基于RLWE的公鑰加密方案。與文獻［24］安全性證明類似，該方案在決策RLWE假設下是語義安全的。

算法2 PKE.Setup（1n，1l）

a）輸入安全參數n和l，其中l表示內積向量和屬性向量的長度；

b）（A，TA）←TrapGen（1n，1k，q，σ），其中A∈Rkq，其陷門TA∈Rk×kq；

c）挑選l個均勻隨機向量A1，…，Al∈Rkq和均勻隨機多項式u∈Rq；

d）輸出公共參數PP=（A，A1，…，Al，u），主私鑰MK=（TA）。

算法3 PKE.KeyGen（PP，MK，yj）

a）輸入公共參數PP，主私鑰MK和內積向量yj={y1j，…，ylj};

d）輸出私鑰SKyj=e∈R2k，公鑰PK=u∈Rq。

算法4 PKE.Encrypt（PP，xi，M）

a）輸入公共參數PP，屬性向量xi，消息M={0，1}n;

c）均勻隨機選擇一個環多項式s∈Rq和l個環多項式矩陣R1，…，Rl∈Rk×k，其系數為{-1，1}；

c′=AT·s+noise∈Rkq，

cs=（As+xsiB）Ts+Rs·noise∈Rkq；

f）輸出密文C=（c，c′，cs）。

算法5 PKE.Decrypt（PP，SKyj，C）：

2）隱私集合求交階段

a）對于每個xi∈X，參與方P1執行以下操作：

（b）使用加密算法PKE.Encrypt（PP，xi，Mi）對消息Mi進行加密，得到密文Ci←PKE.Encrypt（PP，xi，Mi）；

（c）將C={C1，…，Ci}，i∈（1，w）發送給P2。

b）P2收到密文C，執行以下操作：

（a）對于每個yi∈Y，通過密鑰生成算法PKE.KeyGen（PP，MK，yj）提取私鑰ej；

（b）ej解密Ci得到Mj=（H（y′j）|M′j）；

（c）如果M′j是特殊的隨機值，且|H（yj）－H（y′j）|為0，故yj∈X∩Y，此時將Mj發送給P1；反之結果不為0，不發送任何消息給P1。

c）P1收到Mj，滿足|M′i－M′j|和|H（xi）－H（y′j）|同時為0，則說明xi∈X∩Y。

3 正確性和安全性分析

3.1 正確性分析

該構造中，密鑰e中嵌入一個與元素有關的函數，加密時在密文中嵌入元素，當參與方P1、P2中元素xi=yj時，解密方的密鑰中的yj與密文中的xi滿足內積為0，這時解密方就可以成功解密這個密文，根據盲化的消息進而判斷交集元素。為了滿足正確性要求，本文的參數選擇如下：

證明 Decrypt的第一步是計算出組合密文cy：

當xi=yj時，滿足內積〈xi，yj〉=0（mod q），因此組合密文cy就剩下：

Decrypt的第二步是正確使用密鑰e解密。本文首先拼接c′與cy，然后乘以對應的密鑰e：

最后，本文可以從c中減去這一項就可以得到密文：

為了正確解密，本文應該設置合適的參數，以極大的概率使

只要像引理中的要求選擇q和α，式（12）的絕對值就會小于q/4。

3.2 安全性分析

下面證明該兩方PSI協議的安全性。

定理3 如果第2章初始化階段中的加密方案在語義上是安全的，則該兩方PSI協議在標準模型中是針對半誠實敵手的安全計算協議。

證明 假設Ad是破壞參與方P1和P2之間PSI協議安全性的敵手。然后通過Game0和Game1來構造一個模擬兩方PSI協議的模擬器SIM，并允許SIM訪問腐敗方的輸入和輸出，使其滿足模擬視圖和真實世界視圖在計算上難以區分。通常，實體的視圖由實體的輸入消息、實體內部擲硬幣的結果和該實體在協議執行期間收到的消息組成。令參與方P1、P2的元素分別為X={x1，…，xw}，Y={y1，…，yv}，從以下兩種情況證明兩方PSI的安全性：

a）caseⅠ。Ad腐敗P2。假設模擬器SIM訪問P2的輸入集合Y，輸出X∩Y。

Game0：該游戲對應于真實的游戲，其中模擬器SIM模擬P1與Ad交互。因此Pr［Game0］=Pr［REALPSI］，其中Pr［REALPSI］表示真實的游戲。

b）caseⅡ。Ad腐敗P1。假設模擬器SIM訪問P1的輸入集合X，輸出X∩Y。

Game0：該游戲對應于真實的游戲，其中模擬器SIM模擬P2與Ad交互。因此Pr［Game0］=Pr［REALPSI］，其中Pr［REALPSI］表示真實的游戲。

4 效率分析

如表1所示，將本文協議同文獻［9～12］協議在安全性、通信復雜度和計算復雜度等方面進行比較總結，來說明本文協議在總體上有較好的性能。其中w和v分別表示參與方P1和P2集合中的元素個數，n、k、l為安全參數。

a）通信復雜度。通信復雜度以交互過程中的組元素個數衡量。參與方P1需要發送w（n+2nk）+（l+1）nk+n個組元素C={C1，…，Ci}，i∈（1，w），參與方P2需要發送vn個組元素Mj。因此，該協議的通信復雜度與w、v成正比，即O（w+v）。

b）計算復雜度。在分析協議效率時，使用函數加密算法加密數據時的計算開銷為協議的主要開銷，故該協議的計算復雜度以運算過程中的模乘運算來衡量。參與方P1在生成密文階段需要w（3n+1）個模乘得到密文C={C1，…，Ci}，i∈（1，w）；參與方P2在提取私鑰階段需要wvnk個模乘生成私鑰SK，解密階段需要2vnk個模乘得到Mj，如表2所示。

從安全性角度來看，協議的核心算法是基于決策RLWE安全假設的函數加密算法，安全性可歸約到格上的CVP困難問題，與傳統基于數論假設的協議文獻［9～12］不同，該協議可在未來量子計算機和現實敵手的雙重威脅下實現更完備的隱私保護需求。所以該PSI協議在安全性方面優于先前的文獻［9～12］協議。

從通信復雜度角度來看，相比于文獻［9，10］，本文協議的通信復雜度與參與方集合大小成正比，在通信復雜度上本文協議有較大的優勢。本文協議與文獻［11，12］相比，盡管兩者的通信復雜度均為線性，但是與大多數協議不同，本文協議只需要模乘運算而不是昂貴的模冪運算，因此通信成本低。

從計算復雜度角度來看，本文協議與文獻［9～12］相比，雖然在計算復雜度方面犧牲了些許效率，但是相較于其他協議，本文協議可以在離線階段對相關操作進行預計算，無須在線階段完成，適用于資源受限的環境。

5 結束語

本文提出一種有效的基于理想格的兩方PSI協議，使其在抵抗量子攻擊的同時具備較好的通信和計算效率，其安全性是基于決策RLWE困難問題的標準模型下實現的。該協議采用了基于格的函數加密方案，通過二進制分解將參與方元素設計成符合LWE加法同態的向量形式，利用格上基于密文策略的函數加密系統實現PSI。使用基于理想格的函數加密系統代替q元格實現PSI協議，優化了函數加密系統的公鑰，降低了格表示的空間尺寸，同時利用傅里葉變換（FFT）加速其運算，提高了整個系統的通信效率。該協議的數據內容的隱私通過函數加密算法所具備的機密性來實現，將隱私性綁定到密碼系統的安全性上，而格上密碼系統的安全性則依賴于已知難解的困難問題，故本文協議相較于基于數論難題的協議安全假設困難性更高，更具有安全性。

參考文獻：

［1］宋祥福，蓋敏，趙圣楠，等. 面向集合計算的隱私保護統計協議［J］. 計算機研究與發展，2020，57（10）： 2221-2231. （Song Xiangfu，Gai Min，Zhao Shengnan，et al. Privacypreserving statistics protocol for setbased computation［J］. Journal of Computer Research and Development，2020，57（10）： 2221-2231.）

［2］Demmler D，Rindal P，Rosulek M，et al. PIRPSI： scaling private contact discovery［J］. Proceedings on Privacy Enhancing Technologie，2018，2018（4）： 159-178.

［3］Lyu Siyi，Ye Jinhui，Yin Sijie，et al. Unbalanced private set intersection cardinality protocol with low communication cost［J］. Future Generation Computer Systems，2020，102： 1054-1061.

［4］Shen Liyan，Chen Xiaojun，Wang Dakui，et al. Efficient and private set intersection of human genomes［C］// Proc of IEEE International Conference on Bioinformatics and Biomedicine. Piscataway，NJ： IEEE Press，2018： 761-764.

［5］Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party［C］// Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ： IEEE Press，1986： 134.

［6］Freedman M J，Nissim K，Pinkas B. Efficient private matching and set intersection［C］// Proc of International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer，2004： 1-19.

［7］Chen Hao，Huang Zhicong，Laine K，et al. Labeled PSI from fully homomorphic encryption with malicious security［C］// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press，2018： 1223-1237.

［8］Chen Hao，Laine K，Rindal P. Fast private set intersection from homomorphic encryption［C］// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press，2017： 1243-1255.

［9］Kolesnikov V，Kumaresan R，Rosulek M，et al. Efficient batched oblivious PRF with applications to private set intersection［C］// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press，2016： 818-829.

［10］Hazay C. Oblivious polynomial evaluation and secure setintersection from algebraic PRFs［J］. Journal of Cryptology，2018，31（2）： 537-586.

［11］Andreea I. Private set intersection： past，present and future ［C］// Proc of the 18th International Conference on Security and Cryptograph. 2021： 680-685.

［12］Karako F，Kyupyu A. Linear complexity private set intersection for secure twoparty protocols［C］// Proc of the 19th International Conference on the Cryptology and Network Security. Berlin： Springer，2020： 409-429.

［13］Debnath S K，Choudhury T，Kundu N，et al. Postquantum secure multiparty private setintersection in star network topology［J］. Journal of Information Security and Applications，2021，58： 102731.

［14］Boneh D，Sahai A，Waters B. Functional encryption： definitions and challenges ［C］// Proc of Theory of Cryptography Conference. Berlin： Springer，2011： 253-273.

［15］Lai Qiqi，Liu Fenghao，Wang Zhedong. New lattice twostage sampling technique and its applications to functional encryptionstronger security and smaller ciphertexts［C］// Proc of the 40th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer，2021： 498-527.

［16］王生玉，汪金苗，董清風，等. 基于屬性加密技術研究綜述［J］. 信息網絡安全，2019，19（9）： 76-80. （Wang Shengyu，Wang Jinmiao，Dong Qingfeng，et al. A survey of attributebased encryption technology［J］. Netinfo Security，2019，19（9）： 76-80.）

［17］Gentry C，Peikert C，Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions［C］// Proc of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM Press，2008： 197-206.

［18］賽煒. 基于理想格的公鑰密碼中模多項式的應用研究［D］. 西安： 西安電子科技大學，2015. （Sai Wei.Research on modulus polynomials in public key encryption based on ideal lattices ［D］. Xian： Xidian University，2015.）

［19］Imaa J L，He Pengzhou，Bao Tianyou，et al. Efficient hardware arithmetic for inverted binary RingLWE based postquantum cryptography［J］. IEEE Trans on Circuits and Systems I： Regular Papers，2022，69（8）： 3297-3307.

［20］Boura C，Gama N，Georgieva M，et al. CHIMERA： combining ringLWEbased fully homomorphic encryption schemes［J］. Journal of Mathematical Cryptology，2020，14（1）： 316-338.

［21］Agrawal S，Freeman D M，Vaikuntanathan V. Functional encryption for inner product predicates from learning with errors［M］// Lee D H，Wang Xiaoyun. Proc of the 17th International Conference on Theory and Application of Cryptology and Information Security. Berlin： Springer，2011： 21-40.

［22］Tao Xufeng，Qiang Yan，Wang Peng，et al. LMIBE： latticebased matchmaking identitybased encryption for Internet of Things［J］. IEEE Access，2023，11： 9851-9858.

［23］唐慧，汪學明. 基于格的多授權密文屬性加密方案［J］. 計算機應用研究，2022，39（2）： 563-566，571. （Tang Hui，Wang Xueming. Lattice-based multi-authorization ciphertext attribute encryption scheme［J］. Application Research of Computers，2022，39（2）： 563-566，571.）

［24］Agrawal S，Freeman D M，Vaikuntanathan V. Functional encryption for inner product predicates from learning with errors［C］// Proc of the 17th International Conference on Theory and Application of Cryptology and Information Security. Berlin： Springer，2011： 21-40.