The White-Box Adversarial Data Stream Model
The White-Box Adversarial Data Stream Model
复制标题
DOI：
10.1145/3517804.3526228
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
M. Ajtai;V. Braverman;T. S. Jayram;Sandeep Silwal;Alec Sun;David P. Woodruff;Samson Zhou
中科院分区：
文献类型：
--
作者：
M. Ajtai;V. Braverman;T. S. Jayram;Sandeep Silwal;Alec Sun;David P. Woodruff;Samson Zhou
最近有大量文献研究流算法，其中输入流是由一个黑盒敌手自适应选择的，该敌手在每个时间步观察流算法的输出。然而，当敌手能够访问算法的内部状态，而不仅仅是算法的输出时，这些算法就会失败。我们在白盒对抗模型中研究流算法，其中流是由一个在每个时间步观察算法整个内部状态的敌手自适应选择的。我们表明非平凡的算法仍然是可能的。我们首先给出一个用于L1 - 重击者问题的随机算法，它在长流上优于最优确定性的米斯拉 - 格里斯算法。如果白盒敌手在计算上是有界的，我们使用密码技术进一步减少我们的L1 - 重击者算法的内存，并为图、字符串和线性代数问题设计一些其他算法。这类算法的存在是令人惊讶的，因为在这个模型中流算法甚至没有密钥，即它的状态完全为敌手所知。我们设计的一个算法是用于估计具有插入和删除操作的流中不同元素的数量，实现乘法近似和次线性空间；对于确定性算法来说，这样的算法是不可能的。我们还给出一种通用技术，它将任何两个参与者的确定性通信下界转换为对随机算法（对白盒敌手具有鲁棒性）的下界。特别是，我们的结果表明，对于所有p≥0，存在一个常数Cp > 1，使得在具有白盒敌手的仅插入流中，任何用于Fp矩估计的Cp - 近似算法对于大小为n的全集需要Ω(n)空间。类似地，存在一个常数C > 1，使得在具有白盒敌手的仅插入流中，任何用于矩阵秩的C - 近似算法需要Ω(n)空间。这些结果与我们的上界并不矛盾，因为它们假设敌手具有无界的计算能力。因此，我们基于密码学的算法结果表明了计算有界和无界敌手之间的分离。最后，我们证明了对于0和1组成的流中确定性近似计数这一基本问题的Ω(log(n))位的下界，即使我们知道到目前为止在流的每个点我们已经看到了多少流更新，该下界仍然成立。对于具有附加信息的近似计数的这样一个下界以前是未知的，并且在我们的背景下，它表明了多参与者确定性最大通信和流算法的白盒空间复杂度之间的分离。
There has been a flurry of recent literature studying streaming algorithms for which the input stream is chosen adaptively by a black-box adversary who observes the output of the streaming algorithm at each time step. However, these algorithms fail when the adversary has access to the internal state of the algorithm, rather than just the output of the algorithm. We study streaming algorithms in the white-box adversarial model, where the stream is chosen adaptively by an adversary who observes the entire internal state of the algorithm at each time step. We show that nontrivial algorithms are still possible. We first give a randomized algorithm for the L1-heavy hitters problem that outperforms the optimal deterministic Misra-Gries algorithm on long streams. If the white-box adversary is computationally bounded, we use cryptographic techniques to reduce the memory of our L1-heavy hitters algorithm even further and to design a number of additional algorithms for graph, string, and linear algebra problems. The existence of such algorithms is surprising, as the streaming algorithm does not even have a secret key in this model, i.e., its state is entirely known to the adversary. One algorithm we design is for estimating the number of distinct elements in a stream with insertions and deletions achieving a multiplicative approximation and sublinear space; such an algorithm is impossible for deterministic algorithms. We also give a general technique that translates any two-player deterministic communication lower bound to a lower bound for randomized algorithms robust to a white-box adversary. In particular, our results show that for all p≥0, there exists a constant Cp>1 such that any Cp-approximation algorithm for Fp moment estimation in insertion-only streams with a white-box adversary requires Ω(n) space for a universe of size n. Similarly, there is a constant C>1 such that any C-approximation algorithm in an insertion-only stream for matrix rank requires Ω(n) space with a white-box adversary. These results do not contradict our upper bounds since they assume the adversary has unbounded computational power. Our algorithmic results based on cryptography thus show a separation between computationally bounded and unbounded adversaries. Finally, we prove a lower bound of Ω(log(n)) bits for the fundamental problem of deterministic approximate counting in a stream of 0s and 1s, which holds even if we know how many total stream updates we have seen so far at each point in the stream. Such a lower bound for approximate counting with additional information was previously unknown, and in our context, it shows a separation between multiplayer deterministic maximum communication and the white-box space complexity of a streaming algorithm.