PSI系列（1）组件 | Cuckoo Hashing

1

简介

布谷鸟哈希（Cuckoo Hashing）原本是一种解决哈希冲突的方法，因与布谷鸟的习性（布谷鸟在孵化时会将其他的蛋或幼崽挤出巢穴）而得名，目前常常与Simple Hashing联动来构造PSI协议。我初次接触它时，在网上搜寻资料看到诸多不同版本，与所读文章中的用法不尽相同，加之其通俗易懂的规则，故以此为PSI系列的首篇十分合适。本文选用stash-less Cuckoo hashing并根据文献[1]的记法和文献[2]的插入规则来对其进行介绍。
2

插入规则布谷鸟哈希的目标是使用个哈希函数 将大小为的集合插入个桶（bin, 记为）中，得到的结果为，其中是只能存放一个元素的桶。根据文献[2]可知，当时，分别取和时布谷鸟哈希的插入失败概率至多为。我们取，就可以得到记法：插入规则如下：1. 当插入元素时，先查看中是否有空桶，有多个空桶时放入序号最小的第一个空桶；若没有空桶则在这三个桶中随机选取一个桶，将该桶内的元素踢出，插入元素。 2. 以相同的规则插入，直到所有元素插入完毕。（这种插入后踢出再插入的方式，可能会产生循环，当循环次数达到某个门限值时，会将其放入储藏桶（stash）中；储藏桶对于PSI协议会产生很多额外的开销。因此很多文章选择不使用储藏桶（stash-less），根据的大小来调节桶的个数可以使得失败概率很低。）
3

例子1. 插入 ： 根据计算得到了三个位置，均为空桶，我们按照规则将插入序号最小的空桶中。 2. 插入 ：根据计算得到了三个位置，我们按照规则将插入序号最小的空桶中。3. 插入 ： 根据计算得到了三个位置，我们按照规则将插入序号最小的空桶中。 4. 插入 ： 根据计算得到了三个位置，我们按照规则将插入序号最小的空桶中。 5. 插入 ：   根据计算得到了三个位置，没有空桶，我们随机选择一个桶将其中的元素踢出，并将插入中。 

踢出B

插入G

6. 插入 ：  针对被踢出的元素，我们照旧计算得到三个位置，将插入序号最小的空桶中。 
根据上述插入规则，我们很容易得到布谷鸟哈希的一个重要性质：对于某个元素，其所在桶的位置必然是中的一个。这便是布谷鸟哈希可以用来作为PSI组件的重要原因，具体的构造会在今后的文章中给出。本文如有错误，请各位及时指出，谢谢。
4

参考文献[1] Garimella G, Mohassel P, Rosulek M, et al. Private set operations from oblivious switching[C]//Public-Key Cryptography–PKC 2021: 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10–13, 2021, Proceedings, Part II. Cham: Springer International Publishing, 2021: 591-617.[2] Chandran N, Dasgupta N, Gupta D, et al. Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI[C]//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 1182-1204.[3] Pinkas B, Schneider T, Zohner M. Scalable private set intersection based on OT extension[J]. ACM Transactions on Privacy and Security (TOPS), 2018, 21(2): 1-35.作者简介：林中允，华东师范大学软件工程密码与网络安全系研究生，主要研究方向为多方隐私集合求交。知乎：@云波

END

往期推荐

1.全同态加密知识体系整理(下)
2.联邦学习安全聚合：基于安全多方计算的经典方案3.椭圆曲线密码在多方安全计算中的应用4.全同态加密知识体系整理(上)