1 介绍
首先是介绍一些概念：
最近邻搜索KNN：找到与查询点最接近的前k个点。
近似最近邻搜索：在大型高维数据库中，KNN的成本会很高，此时该问题通常会被放宽为近似最近邻搜索ANNS，允许以高概率返回最接近的前k个邻点而非精确结果。
私有最近邻搜索：客户端希望获取且仅能获取最近邻搜索的结果，同时不向服务器泄露查询内容。
以往的私有最近邻搜索存在通信成本高、依赖两个非共谋服务器的安全假设等问题，本文适用单服务器。
通常情况，ANNS需要明确知晓数据库和查询点才能进行运算，如果双方不愿意泄露数据，就需要用到MPC。如果是三方，即两个服务器，复杂度可以大幅降低，但对客户端而言，这种设定的可信度不如单服务器。
USENIX2020提出的框架SANNS是该设定，但依赖通信开销较高的技术比如分布式oblivious RAM和混淆电路。
从SANNS角度出发，分析单服务器私有ANNS两个难点：（1）ANNS一种实践是将数据库划分为若干聚类，这样只需对部分距离较近的聚类进行前k个距离计算，避免全库的扫描。在MPC中，检索近邻聚类的点需要以不经意的方式，需要依赖开销昂贵的DORAM。（2）计算前k个结果需要用秘密共享或混淆电路，前者计算会导致过多的通信轮次，后者会产生大量通信量。
本文贡献：
-
设计了一种shuffle-and-reveal协议，通过高效的PIR而非DORAM来解决点检索问题。提出了对PIR结果（特殊格式的同态加密文本）进行后处理的高效方法，使其兼容后续的MPC操作；
-
提出了一种混合基元的top-k方法，优化了top-k选择过程；
-
对PIR和距离计算中使用的同态加密文本编码进行设计，能够使用更小的HE参数，缓解与同态加密噪声相关的隐私问题；
-
引入一个完全实现端到端安全ANNS框架Panther并进行实验。
2 预备知识
2.1 密码原语
（1）additive secret sharing
一个(l)比特（(lge 2)）的值(x)分为([[x]]_c,[[x]]_s)，分别表示客户端和服务器持有的部分，重构公式为(x=[[x]]_c+[[x]]_sspace text{mod}space 2^l)。
对于实数值(tilde xin R)，处理方法是先按照特定精度(f>0)将其编码为定点值(x=[tilde x^{2^f}]in[-2^{l-1},2^{l-1}])再进行分享。对于布尔值，(z=[[z]]_c^Boplus [[z]]_s^B)。
如果不关心份额归属时，会省略下标。
（2）混淆电路Garbled circuit
用于实现布尔电路的安全两方计算，本质是混淆方以加密格式为电路的门生成真值表，这些真值表可以由评估方进行评估。
优势在于网络交互轮次固定，这对深度电路比如求最值、排序电路非常有用。
（3）Lattice-based additive homomorphic encryption
同态加密核心是明文(x)加密后无需解密密钥，就能直接对密文进行计算。本文采用BFV方案，适用于多项式环上的加密计算，能高效支持加法和乘法操作。
BFV的公开参数定义为(text{HE.pp}=lbrace N,p,qrbrace)：
-
(N)是多项式环的维度，对应多项式的最高次数（多项式形式为(sum_{i=0}^{N-1}a[i]x^i)），决定了加密并行度和安全性；
-
(q)是密文空间的模数，定义密文所属的多项式环(A_{N,q})（即系数在模(q)下的(N)次多项式集合）；
-
(p)是明文空间的模数。
BFV的四个函数：
-
(text{KeyGen})：生成加密所需的密钥对(skin A_{N,q},pkin A_{N,q}^2)；
-
(text{Encryption})：用(pk)对明文(hat m)加密生成密文，密文形式是多项式对((hat b,hat a))；
-
(text{Addition})：输入加密(hat m_0,hat m_1)的密文(ct_0,ct_1)，计算((hat b_0+hat b_1spacetext{mod}space q,hat a_0+hat a_1spacetext{mod}space q))，可以被解密为(hat m_0+hat m_1space text{mod}space p)；
-
常数乘法：密文与明文常数相乘，结果解密后为明文与该常数的乘积。
本文使用混合密码原语设计，优先使用基于格的同态加密，对HE不适用的场景切换为秘密分享技术。
使用([[vec a]]_l^H)表示由(P_l)持有的密文，该密文是用(P_{1-l})的公钥加密的，其中向量(vec a)在加密前会被转换为多项式(hat a=sum_{i=0}^{N-1}vec a[i]X^i)。
HE到算术秘密分享的转换（H2A）：([[vec a]]_l^H)转为秘密分享([[vec a]])的流程为：
-
(P_l)采样多项式(hat r)并将和(ct=[[vec a]]_l^H boxplus hat r)发给对方；
-
(P_{1-l})解密(ct)得到多项式(hat a+hat rspace text{mod}space p)，将该多项式的系数提取作为其份额([[vec a]]_{1-l})；
-
(P_l)份额为([[vec a[i]]]_l=-lceil 2^lcdot hat r[i]/qrfloor space text{mod}space 2^l)。
（4）批量PIR
私有信息检索PIR是一类协议，它使客户端能使用私有索引(i)查询服务器数据库，从而让客户端获取(db[i])，同时服务器无法得知(i)。一种变体是客户端同时查询一组索引(I=lbrace i_1,i_2,cdots,i_mrbrace)，借助概率批量编码PBC，这种方式比进行(m)次独立查询更高效。
2.2 基于聚类的ANNS
ANNS方法可以归纳为基于图或树的方法、基于局部敏感哈希的方法以及基于聚类的方法。
明文场景下，HNSW为代表的基于图的方法性能最好，但其对安全计算并不友好，因为依赖无法并行执行的层次化内存操作。安全计算中基于聚类的算法效率颇高，因此本文选择基于聚类的算法作为底层明文方法。
基于聚类的ANNS流程：
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/2.jpg&w=218&h=124&zc=1)
