Secure Multi-party Shuffling
Secure Multi-party Shuffling
复制标题
安全多方洗牌
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Zamani
中科院分区：
文献类型：
--
作者：
Mahnush Movahedi;Jared Saia;M. Zamani
在安全多方洗牌中，每个持有输入的多方希望在保持排列秘密的同时就其输入的随机排列达成一致。这个问题在许多隐私保护应用中非常重要，例如匿名通信，基于位置的服务和电子投票。用于解决该问题的已知技术遭受差的可扩展性、负载平衡问题、可信方假设和/或弱的安全保证。
在本文中，我们提出了一个无条件安全的协议，多方洗牌，规模以及与各方的数量和负载平衡。特别是，我们要求每一方只发送一个多对数数量的比特，并执行一个多对数数量的操作，同时只产生一个对数轮复杂度。我们的安全性下，普遍的可组合性对约n/3完全恶意的缔约方。我们还提供了模拟结果表明，我们的协议显着改善了以前的工作。例如，对于一百万个缔约方，与现有技术相比，我们的协议将通信和计算成本降低了至少三个数量级，并略微减少了通信回合的数量。
In secure multi-party shuffling, multiple parties, each holding an input, want to agree on a random permutation of their inputs while keeping the permutation secret. This problem is important as a primitive in many privacy-preserving applications such as anonymous communication, location-based services, and electronic voting. Known techniques for solving this problem suffer from poor scalability, load-balancing issues, trusted party assumptions, and/or weak security guarantees.
In this paper, we propose an unconditionally-secure protocol for multi-party shuffling that scales well with the number of parties and is load-balanced. In particular, we require each party to send only a polylogarithmic number of bits and perform a polylogarithmic number of operations while incurring only a logarithmic round complexity. We show security under universal composability against up to about n/3 fully-malicious parties. We also provide simulation results showing that our protocol improves significantly over previous work. For example, for one million parties, when compared to the state of the art, our protocol reduces the communication and computation costs by at least three orders of magnitude and slightly decreases the number of communication rounds.