Efficient Private Matching and Set Intersection

发表于 更新于 分类于

高效的隐私匹配和集合交集

我们考虑计算两方隐私数据集的交集问题，其中数据集包含来自大领域的元素列表。这个问题在在线协作方面有很多应用。我们提出了基于使用同态加密和平衡散列的协议，适用于半诚实和恶意的环境。对于长度为 k 的列表，我们得到了 通信开销和 计算。半诚实环境的协议在标准模型中是安全的，而恶意环境的协议在随机预言机模型中是安全的。我们还考虑了近似交点大小的问题，显示了解决这个问题的通信开销的线性下限，并提供了一个合适的安全协议。最后，我们研究了匹配问题的其他变体，包括将协议扩展到多方设置，以及考虑近似匹配的问题。

1 介绍

这项工作考虑了几个双方集合相交的问题并提出了相应的安全协议。我们的协议使双方各自持有一组输入 -- 从一个大域中抽取 -- 共同计算其输入的交集，而不泄露任何额外信息。集合相交基元是非常有用的，因为它广泛用于数据库的计算，例如，用于数据挖掘，其中数据在各方之间是垂直分割的（即，每一方有不同的属性，指的是相同的主题）。

我们可以设想将高效的集合交叉协议用于在线推荐服务、在线约会服务、医疗数据库和其他许多应用。我们已经开始看到这种应用的部署，要么使用受信任的第三方，要么使用普通的不安全通信。

贡献：我们研究集合相交的隐私双方计算，我们也把它表示为隐私匹配（PM）：

  • 基于同态加密和平衡分配的计算隐私匹配的协议：(i) 一个对半诚实的对手安全的协议；(ii) 一个在随机预言机模型中对恶意对手安全的协议。这些协议比以前解决这个问题的方法更有效。
  • 隐私匹配协议的变体，(i) 计算交集大小，(ii) 决定交集大小是否大于阈值，或者 (iii) 计算交集的一些其他函数。
  • 我们考虑交集大小的隐私近似协议（类似于 [10] 的汉明距离的隐私近似）。从不相交的通信下限的一个简单还原表明，这个问题不可能有一个亚线性的最坏情况下的通信开销。我们展示了一个基于抽样的隐私近似协议，实现了实例最优的通信。
  • 我们将集合相交的协议扩展到多方设置中。
  • 我们介绍了安全近似（或 "模糊"）匹配和搜索问题，并提出了几个简单实例的协议。

2 背景及相关工作

隐私相等性测试（PET）：一个更简单的隐私匹配形式是，两个数据集中的每一个都有一个来自大小为 的域的单一元素。计算这个函数的电路有 门，因此可以用这个开销安全地评估。[9, 18, 17] 中也提出了这个函数的专门协议，它们基本上有相同的开销。[3] 中的一个解决方案除了安全之外还提供了公平性。

一个基于电路的解决方案用于计算长度为 的数据集的 PM，需要 的通信和 的不经意传输。另一个微不足道的构造是使用 PET 协议的 个实例对两个数据集的所有项目组合进行比较（该协议本身有 的开销）。这种比较的计算可以减少到 ，同时保留了 的通信开销 [18]。还有其他的构造可以解决隐私匹配问题，其代价只是 指数化 [12, 8]。然而，这些构造只在随机预言机模型中进行了分析，针对半诚实的一方。

不相邻性和集合相交：计算（或决定）两个集合的交集的协议已经在通信复杂性的一般背景下和安全协议的背景下被研究过。在协议中，双方持有 中的子集 和 的情况下，评估不相交问题的通信复杂性受到了很大关注。如果集合 ， 有一个空的交集，则不相邻函数 被定义为 。众所周知， [14,22]。一个直接的含义是，计算 需要 的通信。因此，即使不考虑隐私，隐私匹配的通信复杂度至少与输入大小成正比。

人们可以尝试通过近似计算交集大小来绕过高通信复杂度。在安全协议的背景下，这可能会导致交集大小的亚线性隐私近似协议。如果我们满足于近似到加性误差 （对于常数 ），很容易看到存在非常有效的协议，即在隐私随机性模型中的 比特 [16，例 5.5]。然而，如果我们需要乘法误差（例如，一个 近似值），我们展示了一个来自不相邻性的简单还原，证明了任何这样的近似协议都需要 的通信比特的下限。详见第 6 节。

3 预备工作

3.1 隐私匹配（PM）

3.2 敌手模型

3.3 密码学原理 -- 同态加密方案

4 诚实好奇的情况

4.1 用于计算集合交点的隐私匹配

4.2 高效地评估多项式

4.3 诚实好奇模型下隐私匹配的安全性

4.4 变体：用于计算集合的 Cardinality 的隐私匹配

4.5 变体：用于计算 Cardinality 门限和其他功能的隐私匹配

5 针对恶意方的安全性

5.1 恶意用户

5.2 恶意服务器

5.3 处理恶意的用户和服务器

6 近似交叉点

7 有多个参与方的情况

8 模糊匹配和模糊搜索

参考文献

  1. Bill Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology—EUROCRYPT 2001, Innsbruck, Austria, May 2001.

  2. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM Journal on Computing, 29(1):180–200, 1999.

  3. Fabrice Boudot, Berry Schoenmakers, and Jacques Traore. A fair and efficient solution to the socialist millionaires’ problem. Discrete Applied Mathematics, 111(12):23–036, 2001.

  4. Andrei Z. Broder and Michael Mitzenmacher. Using multiple hash functions to improve ip lookups. In IEEE INFOCOM’01, pages 1454–1463, Anchorage, Alaska, April 2001.

  5. Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology—EUROCRYPT ’99, pages 402–414, Prague, Czech Republic, May 1999.

  6. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, pages 136–145, Las Vegas, Nevada, October 2001.

  7. Ivan Damg ̊ard and Mads Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In 4th International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2001), pages 13–15, Cheju Island, Korea, February 2001.

  8. Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proc. 22nd ACM Symposium on Principles of Database Systems (PODS 2003), pages 211–222, San Diego, CA, June 2003.

  9. Ronald Fagin, Moni Naor, and Peter Winkler. Comparing information without leaking it. Communications of the ACM, 39(5):77–85, 1996.

  10. Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, and Rebecca N. Wright. Secure multiparty computation of approximations. In Automata Languages and Programming: 27th International Colloquim (ICALP 2001), pages 927–938, Crete, Greece, July 2001.

  11. Oded Goldreich. Secure multi-party computation. In Available at Theory of Cryptography Library, http://philby.ucsb.edu/cryptolib/BOOKS, 1999.

  12. Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In Proc. ACM Conference on Electronic Commerce, pages 78–86, Denver, Colorado, November 1999.

  13. Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proc. 21st Annual ACM Symposium on Theory of Computing, pages 44–61, Seattle, Washington, May 1989.

  14. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Mathematics, 5(4):545–557, 1992.

  15. Aggelos Kiayias and Moti Yung. Secure games with polynomial expressions. In Automata Languages and Programming: 27th International Colloquim (ICALP 2001), pages 939–950, Crete, Greece, July 2001.

  16. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1997.

  17. Helger Lipmaa. Verifiable homomorphic oblivious transfer and private equality test. In Advances in Cryptology—ASIACRYPT 2003, pages 416–433, Taipei, Taiwan, November 2003.

  18. Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proc. 31st Annual ACM Symposium on Theory of Computing, pages 245–254, Atlanta, Georgia, May 1999.

  19. Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In SIAM Symposium on Discrete Algorithms (SODA), pages 448–457, Washington, D.C., January 2001.

  20. Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology—EUROCRYPT ’99, pages 223–238, Prague, Czech Republic, May 1999.

  21. Pascal Paillier. Trapdooring discrete logarithms on elliptic curves over rings. In Advances in Cryptology—ASIACRYPT 2000, pages 573–584, Kyoto, Japan, 2000.

  22. Alexander A. Razborov. Application of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81–93, 1990.