Oblivious Stash Shuffle
Petros Maniatis Ilya Mironov Kunal Talwar Google Brain
Abstract
This is a companion report to Bittau et al. [1]. We restate and prove security of the Stash Shuffle.
中文速览
打乱（shuffle）大规模数据集是隐私计算系统的核心操作，但在受信任内存极为有限的安全硬件（如可信执行环境）中，如何做到既高效又不泄露访问模式（oblivious shuffle，遗忘洗牌）是个难题。Stash Shuffle 的思路是把 N 个数据项分成 B 个桶，先将每个输入桶的数据随机分配到各输出桶（分发阶段），再逐桶打乱（压缩阶段），用一个称为"stash（暂存区）"的私有结构来吸收分配过程中不可避免的随机波动，从而把所需的私有内存压缩到约 N^{1/2} 量级。本文从数学上严格证明了该算法的安全性：通过将 Stash Shuffle 与一个理想化的"桶洗牌"作耦合，证明只要 stash 不溢出、压缩队列不上溢/下溢，两者输出分布完全一致，进而利用矩母函数和二项分布尾概率界，将输出分布与均匀分布之间的统计距离（statistical distance）控制在关于 N 的可忽略量 N^{-ω(1)} 以内。这一结果为在受限安全硬件上构建可证明安全的大规模隐私数据处理系统提供了坚实的理论基础。
原文 arXiv:1709.07553;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1709.07553v2