Rolling-Committee Zeroth-Order Optimization Under Query Budgets

When a machine-learning model sits behind an API, an auditor or adversary can only send inputs and read outputs. Estimating which direction to move in order to improve an objective — a "zeroth-order" gradient, built by probing the model with slightly perturbed inputs and reading how the score changes — costs two queries per input dimension per step, so a single gradient step on an ImageNet-scale input can take hundreds of thousands of calls. Providers know this, and modern defenses do not just rate-limit: they remember. Stateful detectors keep a store of every query ever seen and flag new queries that are perceptually similar to earlier ones, so any optimizer that converges must issue many near-duplicate probes and thereby reveals itself. A recent result formalizes this as a proved dilemma for a single query stream: to evade the similarity detector you must spread your probes widely, but wide probes make the gradient estimate noisy and destroy convergence.

This proposal argues that the dilemma is an artifact of the single-stream assumption, and that it dissolves when a coalition of short-lived participants shares one optimization state. The idea in two sentences: many accounts each issue a small, widely-dispersed set of queries, and their individual gradient estimates — too noisy to be useful alone — are averaged into one precise estimate; the running state (current point, momentum, and the perturbation seeds that generate future probes) is held as a secret split across the participants, so that members can join and leave indefinitely without a coordinator re-issuing shares. The cryptographic machinery for enrollment comes from evolving secret sharing; the optimization machinery comes from distributed zeroth-order methods; the evaluation regime comes from the stateful-defense literature. The honest framing is dual-use: the protocol is a stress test that shows what globally-correlated query coalitions can do to current defenses, and a building block for legitimate federated auditing of hosted models by parties who do not trust each other with their raw query streams.

Core Claim

The dilemma result of Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box Attacks proves that one optimizer cannot simultaneously evade a similarity threshold $\delta$ and keep gradient variance low, because evasion forces a large perturbation scale $\beta$ that inflates the variance $v(\beta)$ of each two-point estimate. But detection thresholds are applied per query stream, while variance averages over streams. If $M$ enrolled agents each form an independent estimate $\hat g_i$ at the evasion-scale $\beta^*$, and the coalition reconstructs the average, then under independence

$$ \mathrm{Var}\big[\hat g_{\mathrm{coal}}\big] \;=\; \frac{1}{M^2}\sum_{i=1}^{M} \mathrm{Var}\big[\hat g_i\big] \;\approx\; \frac{v(\beta^*)}{M}, $$

so a large enough coalition recovers centralized-grade precision while every individual stream stays sparse and dispersed. The claim is threefold: this variance-averaging escape is real and quantifiable; the shared state can be maintained across unbounded enrollment and churn using no-update secret sharing rather than a coordinator; and approximate (not exact) reconstruction of the shared state suffices, because zeroth-order optimization already tolerates bounded gradient noise.

Research Program

The first workstream builds the protocol. What is shared is not a small key but a growing optimization state — the current iterate, momentum buffers, and a tree of perturbation seeds — so we adapt the compiler that Evolving Secret Sharing Made Short already ships for large secrets: an information-dispersal algorithm plus symmetric encryption, with short projective-pseudorandom-generator seeds that expand into evaluation points and need never be updated when new parties enroll (share size scaling as $\lambda(n+1)$ for dynamic thresholds, where $\lambda$ is the security parameter and $n$ the pool size). This paper supplies our enrollment primitive; it does not consider iterative optimization or feedback from an external oracle, which is exactly our addition. Committee handoffs at epochs — where a departing subset hands the state to a freshly enrolled one — follow the bivariate-polynomial machinery of CHURP: Dynamic-Committee Proactive Secret Sharing, whose dimension-switching handoffs tolerate corrupted members during transition; CHURP solves key persistence on blockchains and has never been applied to continuous optimization state, which is the gap we fill. Two constraints from the crypto literature shape the design honestly. First, Evolving Secret Sharing Made Short proves succinct no-update sharing is possible only for rigid access structures — ones where enrollment can never make an unauthorized subset authorized — so either the coalition accepts fixed threshold semantics as the pool grows, or it pays for share updates at handoff (the CHURP epoch path). Second, verifiable aggregation against a malicious member who submits bogus gradient shares is a stated open problem in evolving secret sharing; we will not solve it cryptographically but will use redundant querying and trimmed (median) aggregation, and report how much redundancy Byzantine tolerance costs.

The second workstream proves the variance lemma above rigorously and extends it to churn. The key prior result to build on is Privacy-Preserving Distributed Zeroth-Order Optimization, which proves an $\mathcal{O}(1/M)$ convergence rate for distributed zeroth-order ADMM and shows the perturbation noise itself yields differential privacy for free — we reuse both insights, but that work fixes a static five-agent graph with pre-registered members, while we allow unbounded arrivals and departures. Closest in the optimization literature is Distributed Zeroth-Order Stochastic Optimization in Time-varying Networks, which handles changing communication topologies; however, it varies edges among a fixed population, whereas we vary the population itself and hold the state cryptographically rather than assuming reliable point-to-point channels. We also borrow the noise-tolerance insight of approximate secret sharing from Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity: reconstruction of the form $b' = b + n_{sm}$ suffices when the downstream consumer tolerates bounded error, and a stochastic optimizer is precisely such a consumer — that paper applies this only to homomorphic decryption shares, not to iterative gradient aggregation.

The third workstream is the empirical confrontation with stateful defenses, described below.

Baselines

The naive reference point is uncoordinated Sybil rotation: a pool of fresh accounts, each independently running a standard zeroth-order attack such as NES against the same target, with no shared state. This is what a skeptic would try first, and Investigating Stateful Defenses Against Black-Box Adversarial Examples documents why it fails against defenses with global query stores: Blacklight pools quantized hashes and PIHA pools perceptual hashes across all accounts, so independently descending accounts issue near-duplicate probes that collide in the store regardless of account identity. We will run it with the same total query budget and account count as our method, and beating it means achieving non-trivial attack success where rotation alone triggers detection and stalls.

The strongest existing competitor is OARS, the oracle-guided adaptive rejection sampling attack of Investigating Stateful Defenses Against Black-Box Adversarial Examples, which mines binary rejection feedback to adapt its sampling distribution and reports 99–100% attack success against Blacklight on ImageNet within 10,000 queries, at a cost of $1 to $18 per successful attack against commercial MLaaS; the same paper reports driving a Blacklight-protected CIFAR-10 classifier from 82.2% to 6.4% accuracy. Since its success rate is already at the ceiling, we cannot beat it on raw success; the fair and meaningful comparison is under a per-account query cap with a global store active — say 500 queries per account — where OARS's single stream exhausts its budget and rotation collides in the store. Both methods get identical total query budget, identical account pool, and identical tuning effort over hyperparameters; beating OARS means higher success at equal per-account load, or equal success at a fraction of the per-account load. On pure convergence efficiency we also compare against PSO-BBA from A Distributed Biased Boundary Attack Method in Black-Box Attack, which reports an average of 4596 queries per successful ImageNet attack versus 5432 for BBA and over 10,000 for Boundary Attack, run against a memoryless oracle to isolate query efficiency from evasion.

Finally, two ablations isolate our ingredients. A plain-server coalition — same distributed averaging, same account rotation, but a trusted plaintext coordinator holding the state — isolates the cryptographic contribution; if it matches our full protocol against defenses, the crypto earns its keep only in the untrusting, coordinator-free setting, and we will say so. A static coalition — fixed membership, no churn, D-ZOA-style — isolates the dynamic-enrollment machinery by measuring how much convergence degrades when members actually leave.

Why not just…?

Why not just rotate through Sybil accounts? Because the leading defenses no longer track per account. Investigating Stateful Defenses Against Black-Box Adversarial Examples shows global stores defeat account rotation unless the queries across accounts avoid clustering in the defense's feature space — and uncoordinated accounts descending the same objective inevitably cluster. Geometric dispersion of the query stream is exactly what our protocol enforces by construction, and the Sybil-rotation baseline above will quantify the difference.

Why not just use universal one-query perturbations (YOQO/YOQT)? You Only Query Once queries each image once or twice and can fool nearly 90% of MNIST inputs after 500 images, but its targeted success on ResNet-50 is only about 20% at one query (rising above 66% at two), it still needs thousands to millions of evaluations of distinct images to find the universal perturbation, and its tiling trick leaves structural artifacts. It solves a different problem — per-image repeated-query evasion — and cannot substitute for instance-specific targeted auditing, which is our regime. We will include YOQT as a baseline where the task is universal-perturbation auditing, and expect it to win there; that boundary is part of the contribution.

Why not just use a trusted coordination server? This is the real threat, and we treat it as such rather than arguing around it: against a defense that only watches the model's query interface, a plaintext coordinator plus rotating accounts captures the entire variance-averaging benefit, and the plain-server ablation will measure exactly this. The cryptographic layer is justified only by the deployment stories where no such server exists — mutually distrusting auditors who cannot hand each other raw query streams (each stream reveals the auditor's own data, and the intrinsic differential privacy of zeroth-order perturbations noted by Privacy-Preserving Distributed Zeroth-Order Optimization is part of that story), open ad-hoc coalitions with churn, and settings where a coordinator's own traffic is a detectable chokepoint. If the ablation shows no evasion gap between plain-server and full protocol, we will report the protocol as a fault-tolerance and trust contribution, not an evasion contribution.

Why not just re-key with a central dealer when membership changes? How to Share a Secret, Infinitely and An Identity (ID)-Based Threshold Multi-Secret Sharing Scheme establish that full resets during redistribution create a single point of failure and heavy communication bursts exactly when the system is most exposed; under continuous churn, re-keying never stops. The no-update property of Evolving Secret Sharing Made Short and the $O(n)$ on-chain handoffs of CHURP exist precisely to avoid this, and our churn experiment measures the operational difference.

Proposed Experiments and Decisive Checks

The main arena is ImageNet and CIFAR-10 under re-implemented Blacklight-style (quantized hash) and PIHA-style (similarity-encoder) defenses with global stores, following the setup of Investigating Stateful Defenses Against Black-Box Adversarial Examples and Stateful Detection of Black-Box Adversarial Attacks; the latter reports that a similarity encoder is 6–8x more effective than plain $L_2$ distance at catching attacks, so we use the encoder variant as the harder defense. The decisive metric is attack success at fixed per-account budgets (we sweep caps of 100, 500, and 1000 queries), alongside total queries, detection rate, and dollar cost against the $1–$18 per-attack figure reported for OARS. The headline check is a phase diagram in $(M, \beta)$ space — coalition size versus perturbation scale — testing the $v(\beta^*)/M$ prediction directly: the boundary where the coalition converges should move toward smaller $M$ as $\beta$ falls, and the single-stream dilemma boundary at $\beta^*$ should match the theory of Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box Attacks, which evaluated perturbation variance $\beta = 0.01$ on a one-million-image subset.

Churn is tested on the committee scale of the CHURP simulation benchmark — committees up to 1001 nodes, where a full epoch takes about 3 minutes — injecting member departures and Byzantine share-submission at rates from 5% to 30% per epoch, measuring convergence degradation, handoff latency, and communication overhead against CHURP's reported $O(n)$-on-chain profile. A sanity check on the synthetic distributed-Lasso setup of Privacy-Preserving Distributed Zeroth-Order Optimization verifies we match its proved $\mathcal{O}(1/M)$ rate with static membership before adding churn; no reported result found on Lacuna for that paper's tabulated asymptotic error values, so we reproduce its setting ourselves rather than compare to printed numbers. The proposal succeeds if the coalition achieves near-ceiling success under per-account caps that defeat OARS and Sybil rotation, matches the variance-averaging prediction quantitatively, and survives 20% churn with bounded convergence loss; it fails informatively if the plain-server ablation matches it on evasion and global stores turn out to detect cross-account coordination through the aggregate query geometry — in which case the output is a stronger defense design, which is a publishable result in its own right.