私有集合交集协议中的元素唯一性与输入大小限制

### 隐私集合交集协议中的元素唯一性与输入大小限制 #### 1. AD - PSI - puzzle协议成本分析 AD - PSI - puzzle协议的成本分析如下表所示，括号内为替代协议与原协议不同时的成本： |操作实体|客户端|服务器| | ---- | ---- | ---- | |离线操作| | | |HE.Encryption|n|0| |HE.Decryption|0|(λ + 1)n| |Modular Multiplication|0|0| |Random number generation (in \(Z^*_p\))|0|0| |Random permutations (of length n)|0|0| |Cryptographic hash (input length λn)|0|1| |Cryptographic hash (input length \(\vert M\vert\))|0|n| |Equality check|0|0 (1)| |Involvement check (i.e., if a ∈A)|0|n| |SE.Encryption|0|0 (m)| |SE.Decryption|0|m (0)| |在线操作| | | |HE.Encryption|0|λn| |HE.Decryption|0|0| |Modular Multiplication|0|(λ + R)n| |Random number generation (in \(Z^*_p\))|0|1| |Random permutations (of length n)|0|λ| |Cryptographic hash (input length λn)|0|1| |Cryptographic hash (input length \(\vert M\vert\))|0|m| |Equality check|0|0 (1)| |Involvement check (i.e., if a ∈A)|0|0| |SE.Encryption|0|m (0)| |SE.Decryption|0|0| |通信成本| | | |CHE|(λ + 2)n| | |CSE|m| | |\(\{0, 1\}^κ\)|0 (1)| | |\(\{0, 1\}^{κ'}\)|0 (m)| | |轮数|1 (2)| | 需要注意的是，在PSI文献的常规做法中，不考虑多次执行协议后可能出现的信息泄露问题。例如，客户端故意调整输入元素，若前几轮协议输出为“否”，下一轮输出为“是”，客户端就能知晓最后一轮添加的元素在服务器集合中。不过，这将作为未来的研究方向。 #### 2. 带元素唯一性的PSI变体协议 ##### 2.1 AD - PSI - CA PSI - CA仅输出交集的基数。若客户端使用单个元素作为输入，虽不属于恶意行为，但能得知该元素是否在服务器集合S中，这超出了其应获取的信息范围。若客户端重复使用不同的单个元素进行PSI - CA，甚至能得知交集或整个S（若消息空间足够小）。 为防止这种情况，服务器可限制客户端输入集的最小大小为l，并在计算阶段检查\(\vert C\vert > l\)。但客户端可通过将单个元素复制n次（n > l）绕过此检查，此时PSI - CA结果为“0”或“1”，仍会泄露该元素是否在S中。因此，服务器需要检查客户端输入元素的唯一性，即AD - PSI - Cardinality（AD - PSI - CA）。 AD - PSI - CA的定义与AD - PSI类似，客户端输出为(\(\vert S\vert\), \(\vert S\cap C\vert\))。可通过修改AD - PSI - puzzle协议实现：服务器额外选择一个随机排列π，发送置换后的密文\(\hat{e}_i := e_{R_{\pi(i)}}\)而非\(\hat{e}_i := e_{R_i}\)。由于密文被服务器用R随机化，且客户端不知π，所以客户端无法将\(d_i\)与原始的\(c_i\)匹配。同时，AD - PSI - puzzle保证客户端使用重复输入时，极大概率无法正确解开谜题，只有使用全不同的输入元素时，客户端才能得知\(\vert C\cap S\vert\)。 ##### 2.2 AD - PSI - X PSI - X仅输出两个私有输入集交集是否非空的布尔结果。即便服务器对客户端输入集大小设置下限，客户端使用小输入集仍可能获取比布尔结果更多的信息。若结果为“1”（即存在交集），每个元素在S中的概率为\(1/\vert C\vert\)，因此服务器有动机限制客户端输入集大小以降低此概率。 构建AD - PSI - Existence（AD - PSI - X）协议的一种方法是将PoED阶段添加到基于FHE的PSI - X协议中。基于FHE的PSI - X协议的基本思想是对每个元素进行FHE加密，计算C和S中每对元素的差，再将所有差相乘（乘以一个随机数），若有元素对匹配，解密结果为零，即计算\(R\cdot\Pi_{i,j}(c_i - s_j)\)的加密结果。 PoED阶段可轻松添加：服务器在PSI - X步骤前添加洗牌阶段，并使用从谜题派生的密钥对最终消息进行加密，如同PoED - puzzle协议。 ##### 2.3 AD - PSI - DT PSI - DT会传输与交集元素相关的额外数据。当服务器限制客户端输入大小时，元素不足的客户端可能有动机作弊以绕过限制获取数据。AD - PSI with data transfer（AD - PSI - DT）的定义与AD - PSI类似，客户端输出为(\(\vert S\vert\), \(I := S\cap C\), \(\{D_j\}_{s_j\in I}\))。 AD - PSI - DT协议的构建步骤如下： 1. 与AD - PSI - puzzle协议相同，直至对客户端密文进行随机化。