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

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

關(guān)鍵詞：隱私集合交集；量子攻擊；函數(shù)加密；理想格；錯(cuò)誤學(xué)習(xí)問(wèn)題

中圖分類號(hào)：TP309?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：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 引言

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

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

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

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

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

a）通過(guò)設(shè)計(jì)合理的函數(shù)，構(gòu)造出格上基于密文策略的函數(shù)加密系統(tǒng)構(gòu)造PSI，實(shí)現(xiàn)抗量子的安全性。在函數(shù)加密基礎(chǔ)上，通過(guò)二進(jìn)制分解，將參與方元素設(shè)計(jì)成符合LWE加法同態(tài)的向量形式，當(dāng)且僅當(dāng)元素集合滿足函數(shù)條件才可成功解密，繼而根據(jù)盲化消息判斷交集元素。與依賴于數(shù)論問(wèn)題的公鑰密碼系統(tǒng)不同，基于格的密碼構(gòu)造可在未來(lái)量子計(jì)算機(jī)和現(xiàn)實(shí)敵手的雙重威脅下，實(shí)現(xiàn)更完備的隱私保護(hù)需求。

b）使用理想格優(yōu)化函數(shù)加密系統(tǒng)的參數(shù)，提高了存儲(chǔ)和通信效率。將基于理想格的函數(shù)加密系統(tǒng)代替q元格實(shí)現(xiàn)PSI，減小了公鑰的大小，降低了格表示的空間尺寸，提高了存儲(chǔ)效率。同時(shí)利用傅里葉變換（FFT）加速其運(yùn)算，提高了整個(gè)系統(tǒng)的通信效率。

1 基礎(chǔ)知識(shí)

1.1 整數(shù)格和高斯分布

定義1 q元格。 設(shè)q是素?cái)?shù)，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］提出了高斯采樣技術(shù)，其使用一組短基作為陷門而不泄露短基的任何信息。

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

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

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

定義2 理想格。環(huán)Zn的理想I是格Zn的子格，稱這個(gè)子格為格Zn的理想格。

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

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

1.2 格中陷門

1.3 左采樣算法

左采樣算法［23］在協(xié)議中用來(lái)采樣密鑰，下面是可以從特定格中采樣短向量的多項(xiàng)式時(shí)間算法。

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

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

輸出：向量e∈R2k。

a）采樣一個(gè)隨機(jī)向量e2∈DRk，σ；

1.4 半誠(chéng)實(shí)模型

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

則協(xié)議Π是半誠(chéng)實(shí)安全的。

2 隱私集合交集

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

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

1）初始化階段

該方案將理想格應(yīng)用于函數(shù)加密［24］系統(tǒng)，是一種基于RLWE的公鑰加密方案。與文獻(xiàn)［24］安全性證明類似，該方案在決策RLWE假設(shè)下是語(yǔ)義安全的。

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

a）輸入安全參數(shù)n和l，其中l(wèi)表示內(nèi)積向量和屬性向量的長(zhǎng)度；

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

c）挑選l個(gè)均勻隨機(jī)向量A1，…，Al∈Rkq和均勻隨機(jī)多項(xiàng)式u∈Rq；

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

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

a）輸入公共參數(shù)PP，主私鑰MK和內(nèi)積向量yj={y1j，…，ylj};

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

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

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

c）均勻隨機(jī)選擇一個(gè)環(huán)多項(xiàng)式s∈Rq和l個(gè)環(huán)多項(xiàng)式矩陣R1，…，Rl∈Rk×k，其系數(shù)為{-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）對(duì)于每個(gè)xi∈X，參與方P1執(zhí)行以下操作：

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

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

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

（a）對(duì)于每個(gè)yi∈Y，通過(guò)密鑰生成算法PKE.KeyGen（PP，MK，yj）提取私鑰ej；

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

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

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

3 正確性和安全性分析

3.1 正確性分析

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

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

當(dāng)xi=yj時(shí)，滿足內(nèi)積〈xi，yj〉=0（mod q），因此組合密文cy就剩下：

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

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

為了正確解密，本文應(yīng)該設(shè)置合適的參數(shù)，以極大的概率使

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

3.2 安全性分析

下面證明該兩方PSI協(xié)議的安全性。

定理3 如果第2章初始化階段中的加密方案在語(yǔ)義上是安全的，則該兩方PSI協(xié)議在標(biāo)準(zhǔn)模型中是針對(duì)半誠(chéng)實(shí)敵手的安全計(jì)算協(xié)議。

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

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

Game0：該游戲?qū)?yīng)于真實(shí)的游戲，其中模擬器SIM模擬P1與Ad交互。因此Pr［Game0］=Pr［REALPSI］，其中Pr［REALPSI］表示真實(shí)的游戲。

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

Game0：該游戲?qū)?yīng)于真實(shí)的游戲，其中模擬器SIM模擬P2與Ad交互。因此Pr［Game0］=Pr［REALPSI］，其中Pr［REALPSI］表示真實(shí)的游戲。

4 效率分析

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

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

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

從安全性角度來(lái)看，協(xié)議的核心算法是基于決策RLWE安全假設(shè)的函數(shù)加密算法，安全性可歸約到格上的CVP困難問(wèn)題，與傳統(tǒng)基于數(shù)論假設(shè)的協(xié)議文獻(xiàn)［9～12］不同，該協(xié)議可在未來(lái)量子計(jì)算機(jī)和現(xiàn)實(shí)敵手的雙重威脅下實(shí)現(xiàn)更完備的隱私保護(hù)需求。所以該P(yáng)SI協(xié)議在安全性方面優(yōu)于先前的文獻(xiàn)［9～12］協(xié)議。

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

從計(jì)算復(fù)雜度角度來(lái)看，本文協(xié)議與文獻(xiàn)［9～12］相比，雖然在計(jì)算復(fù)雜度方面犧牲了些許效率，但是相較于其他協(xié)議，本文協(xié)議可以在離線階段對(duì)相關(guān)操作進(jìn)行預(yù)計(jì)算，無(wú)須在線階段完成，適用于資源受限的環(huán)境。

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［1］宋祥福，蓋敏，趙圣楠，等. 面向集合計(jì)算的隱私保護(hù)統(tǒng)計(jì)協(xié)議［J］. 計(jì)算機(jī)研究與發(fā)展，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］王生玉，汪金苗，董清風(fēng)，等. 基于屬性加密技術(shù)研究綜述［J］. 信息網(wǎng)絡(luò)安全，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］賽煒. 基于理想格的公鑰密碼中模多項(xiàng)式的應(yīng)用研究［D］. 西安： 西安電子科技大學(xué)，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，F(xiàn)reeman 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］唐慧，汪學(xué)明. 基于格的多授權(quán)密文屬性加密方案［J］. 計(jì)算機(jī)應(yīng)用研究，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，F(xiàn)reeman 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.