Fast White-Box Adversarial Streaming Without a Random Oracle
Authors: Ying Feng, Aayush Jain, David Woodruff
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove the robustness of our streaming K-Sparse Recovery algorithm in Appendix D and show the efficiency of the algorithm in Appendix E. Finally, in Appendix F and G, we describe our results for distributed protocols and low-rank matrix and tensor recovery, respectively. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA. Correspondence to: Ying Feng <yingfeng@andrew.cmu.edu>, Aayush Jain <aayushja@andrew.cmu.edu>, David P. Woodruff <dwoodruf@cs.cmu.edu>. |
| Pseudocode | Yes | Construction 3.1. Let Stream Alg0 be an algorithm for the Relaxed k-Sparse Recovery problem. Let PFHE be a pseudorandom FHE. Let λ = S(n) be the security parameter of PFHE, for some function S in n that we will specify later. Choose q poly(n) with q n N to be the modulus of PFHE ciphertexts, where N poly(n) is a bound on the stream length. All computations will be modulo q. Our construction is as follows: Stream Alg.Setup(n): Run Stream Alg0.Setup(n). Define ℓ = log n . For each i [n], define a circuit Ci : {0, 1}ℓ {0, 1}, such that: Ci(µ1, µ2, , µℓ) = ( 1 if (µ1, µ2, , µℓ) is the bit representation of i 0 otherwise. Take D e pk(λ) to be the distribution of pseudo-public key in Definition 2.4. Sample f pk D e pk(λ). Similarly, take Dect(λ) to be the distribution of pseudo-ciphertext in Definition 2.4. Sample f ct1, f ct2, , f ctℓ Dect(λ). Store (f pk, f ct1, , f ctℓ) and sketch := 0. Stream Alg.Update(it, t): Run Stream Alg0.Update(it, t). Evaluate d ctit PFHE.Eval(f pk, Cit, f ct1, f ct2, , f ctℓ). Then update sketch sketch + t d ctit. Stream Alg.Report(): Let x Stream Alg0.Report(). If x 0 > k, output . Otherwise, evaluate c cti PFHE.Eval(f pk, Ci, f ct1, f ct2, , f ctℓ) for all i [n]. Then compute hash P i [n] c cti x i. Output x if hash = sketch, and output otherwise. |
| Open Source Code | No | The paper does not provide any statements or links indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical experiments with specific datasets. It defines an abstract 'input vector x' within the streaming model but does not refer to a concrete dataset or provide access information for one. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, therefore it does not discuss training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic constructions and proofs; it does not describe any empirical experiments or the hardware used to run them. |
| Software Dependencies | No | The paper mentions cryptographic schemes (GSW, BV) and mathematical operations (e.g., FFT), but it does not specify any concrete software dependencies with version numbers (e.g., specific programming languages, libraries, or tools with their versions) that would be needed for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore it does not provide details on experimental setup such as hyperparameters or training configurations. |