本文介绍了一篇关于安全排序与选择的研究论文，题为《Secure Sorting and Selection via Function Secret Sharing》，由Amit Agarwal、Elette Boyle、Nishanth Chandran、Niv Gilboa、Divya Gupta、Yuval Ishai、Mahimna Kelkar和Yiping Ma共同撰写，发表于2024年10月的ACM SIGSAC计算机与通信安全会议（CCS ‘24）。该研究聚焦于在半诚实模型下，如何高效地对秘密共享数据进行排序和选择操作（如最大值、中位数或前k个元素），并提出了一系列基于函数秘密共享（Function Secret Sharing, FSS）的协议，显著提升了在线通信和轮次效率。

研究背景与动机

排序和选择是许多应用中的基础操作，尤其是在处理敏感数据时，如何在不泄露数据隐私的情况下高效执行这些操作成为了一个重要问题。现有的解决方案要么通信开销大，要么需要多轮交互，即使允许输入无关的预处理阶段，效率仍然不高。本文旨在通过FSS技术，设计出在线通信和轮次最优的协议，以解决这些问题。

研究方法与流程

研究提出了两种主要的协议设计思路：基于FSS的排序和基于FSS的路由。具体流程如下：

1. 排序与选择的分阶段处理：

   • 排序阶段：分为排名（Ranking）和路由（Routing）两个子阶段。排名阶段计算每个元素的排名（即比它小的元素数量），路由阶段根据排名重新排序或选择特定排名的元素。
   • 选择阶段：与排序类似，但只需选择特定排名的元素，无需完全排序。

2. 基于FSS的排名协议：

   • 分布式比较函数（DCF）：利用DCF进行非交互式的秘密共享排名计算。通过并行比较所有输入对，并聚合比较结果，生成每个输入的秘密共享排名。
   • 乘法分布式点函数（Multiplicative DPF）：在3方设置下，利用乘法DPF进行排名计算，减少了离线通信和在线计算的开销，但仅适用于小域输入。

3. 基于FSS的路由协议：

   • 基于洗牌的路由：在排名阶段之前对输入进行随机洗牌，确保排名可以安全公开，然后根据排名进行路由。
   • 基于DPF的路由：通过DPF技术改进在线轮次复杂度，结合1轮排名协议，实现2轮或3轮的排序/选择协议。

4. 协议性能对比：

   • 本文提出的协议在在线通信和轮次上达到了最优，与现有的基于混淆电路（Garbled Circuit, GC）的协议相比，在线通信开销显著降低。
   • 通过实验对比，本文协议在某些设置下，在线运行时间提升了14倍。

主要结果

1. 协议性能：

   • 本文提出的4种协议（结合不同的排名和路由技术）在在线通信和轮次上均优于现有协议。例如，协议I适用于小批量排序任务，协议II适用于小域排序，协议III和IV通过DPF路由减少了轮次。
   • 协议IV的离线开销与输入规模线性相关，适用于3方设置，但其在线通信开销略高。

2. 理论贡献：

   • 本文证明了在单轮在线协议中，实现高效的安全排序或选择存在理论障碍，表明2轮协议可能是最优的，除非使用更强的密码学假设或指数级预处理。

3. 计算优化：

   • 通过引入比较-聚合算法，本文进一步优化了基于比较的排序和选择协议的计算开销，将在线计算从二次复杂度降低到次二次复杂度，但需要更多的轮次。

结论与意义

本文通过FSS技术，提出了一系列高效的安全排序和选择协议，显著降低了在线通信和轮次的开销。这些协议不仅在理论上达到了最优，还在实际应用中表现出色，特别是在处理小批量或小域数据时。本文的研究为安全多方计算领域提供了新的工具和方法，具有重要的科学和应用价值。

研究亮点

1. 创新性：本文首次将FSS技术应用于安全排序和选择问题，提出了多种新颖的协议设计，显著提升了效率。
2. 理论贡献：通过理论分析，本文证明了在单轮协议中实现高效排序或选择的困难性，为后续研究提供了理论指导。
3. 实际应用：本文的协议在实际应用中表现出色，特别是在处理小批量数据或小域数据时，具有显著的优势。

其他有价值的内容

本文还探讨了如何通过比较-聚合算法进一步优化计算开销，并提供了详细的协议实现和性能对比。此外，本文还讨论了如何在3方设置下实现高效的排序和选择协议，为实际应用提供了更多选择。

本文通过创新的FSS技术，提出了一系列高效的安全排序和选择协议，为安全多方计算领域提供了重要的理论和实践贡献。