Cloud visual positioning services take a photo from your phone or headset and return the camera's position and orientation, its "pose," relative to a stored map of a private space. A lot of work has gone into hiding the map itself. One approach replaces 3D points with random lines. Another replaces them with rays through a shared center. A third replaces them with quantized segments. Chelani et al. (2023) showed that none of this matters if the attacker can simply ask questions. The attacker renders fake photos of a known object, such as a specific IKEA chair, submits them, and checks whether the returned poses line up consistently. If they do, the chair is in the room, and the attacker also learns where it is. Their proposed defenses were adding noise to poses and rejecting suspicious queries. Both cost legitimate users accuracy or produce false alarms, and neither says how much protection it actually buys.
This note argues that the right currency for this threat is the number of queries, and that it should be measured with the tools theorists use to count queries. There are two reasons. The first is that attacker compute is disappearing as a cost. Building probe images once required fitting a per-object 3D reconstruction, which takes minutes to hours. Feed-forward reconstruction models such as GS-LRM now produce a renderable 3D object from 2–4 photos in about 0.23 s. That leaves the query budget as the only resource a service can actually ration. The second reason is that rationing only works if we know how many queries an optimal adaptive attacker needs. We propose to model the positioning service as a black-box oracle and to derive lower bounds on the queries needed to detect and localize an object. We then design a response rule whose bound we can certify, and validate it against the strongest adaptive attack we can build.
Core Claim
Pose leakage is a search problem over candidate object placements. The attacker's cost is set by how many placements a single query can "touch." Here, a query touches a placement if the service's answer could differ depending on whether the object is at that placement. Suppose the service returns a pose only when the matched features cover a sufficiently large and spread-out part of the map, a condition we call a coverage rule. Then any single query touches at most $k$ of $M$ possible placements, and an adversary argument gives
$$R(\text{detect}) = \Omega(M/k), \qquad Q(\text{detect}) = \Omega(\sqrt{M/k}).$$
In these bounds, $R$ is the query cost for any randomized classical attacker and $Q$ is the cost for an attacker with superposition access. The $\Omega(M/k)$ form comes from the fact that each query rules out at most $k$ placements, which makes this an unstructured search. The quantum bound is the Grover-style square root of that. What is new is the reduction itself: a service-side coverage rule becomes a provable query floor. We also test empirically whether real attackers come close to that floor.
Where the Pieces Come From
The threat model and its benchmarks come from Chelani et al. (2023). It is the work that motivates this proposal, because it shows that leakage survives map obfuscation. It also limits us, because it finds that noise and query rejection hurt legitimate users. We add what that paper lacks: a count of how many queries the attack needs, and a defense evaluated by that count.
The lower-bound technique is the adversary method. It works by building pairs of inputs that are hard to tell apart and bounding how much any single query can separate them. Aaronson's local-search lower bounds are the key precedent. They used a quantum-motivated relational adversary argument to prove a classical randomized bound, $\Omega(2^{n/2}/n^2)$ on the hypercube. So quantum query theory appears here as the source of the method, not as a claim that attackers own quantum computers. The same paper's "snake" construction is also useful for a second reason. After a first hit, the attacker refines the object's location by climbing up the inlier ratio, which is a form of local search. The snake construction suggests how to build scenes where that hill-climbing gets no help from nearby answers. Aaronson's certificate-complexity result, $QC(f)=\Theta(\sqrt{RC(f)})$, sets a limit on the quantum side: no coverage rule can hope for more than a quadratic gap between the classical and quantum bounds.
The map-side attacks (line-cloud recovery, neighborhood recovery) and defenses (ray clouds, Gaussian splatting feature fields) are complementary to this work. They protect the stored map, while we protect the service's answers. We use them as the backends that legitimate-user accuracy must be preserved on.
Research Program
The work has three parts.
Theory. We formalize the service as an oracle. It holds a scene $S$, receives an image, and returns either a pose or a refusal. The detection problem asks the attacker to tell apart the scene without the object from scenes with the object at one of $M$ discretized placements. We prove the bounds above under the coverage rule, with $k$ expressed in terms of the minimum match count and the required spatial spread. We then extend the argument to localization, meaning the refinement phase after a first hit, using a snake-style construction.
Defense. We implement the coverage rule on top of a standard localization pipeline and on top of the ray-cloud and splatting-feature-field backends. We measure how often legitimate full-scene queries are refused. The rule is designed to reject queries whose inliers cluster on one small region. Legitimate photos of a room match broadly, whereas rendered single-object probes match locally.
Attack. We build the strongest adaptive attacker we can, to test whether the bound is tight. This attacker uses GS-LRM to build object models from a few photos. It then chooses each next probe viewpoint and composition to maximize the information gained, given the answers so far. It can also embed the object inside plausible background clutter to satisfy the coverage rule. That last strategy is the attack the theory must account for. If generated clutter lets a probe touch many placements at once, $k$ grows, and we report that honestly.
Baselines
The naive reference point is an undefended service attacked with the Chelani et al. (2023) method as published. That paper reports precision up to 0.6 and recall of 0.85 for object identification on IKEA-Scenes, against random guessing at 0.19. We re-run it and report queries-to-detection alongside precision and recall. The file gives no reported query count, so we establish that number ourselves.
The strongest existing defenses are the two that paper discusses: adding noise to returned poses and rejecting single-object queries, along with plain per-client rate limiting. We run each at several strengths on the same scenes and the same attacker. We tune each to the same legitimate-user accuracy budget on 7-Scenes and RIO10 and compare the attacker's queries-to-detection at that matched accuracy. For reference on what "accurate" means, the file reports median translation errors of 1.5–5 cm on 7-Scenes for Gaussian splatting feature fields and 1.282 cm on 12-Scenes for ray clouds. Our defense beats a baseline if, at equal legitimate accuracy and refusal rate, it forces at least several times more attacker queries, and if the measured count stays above the proven floor.
The key ablation removes the spatial-spread part of the coverage rule and keeps only a match-count threshold. This isolates whether spread, rather than simple strictness, is what bounds $k$. On the attack side, we compare the adaptive LRM-based attacker with Chelani's fixed-viewpoint probes. This measures how much adaptivity and cheap object models reduce query cost.
Why not just…?
Why not just rate-limit queries? Rate limiting is the deployment mechanism our work feeds into. The problem is that without a floor on queries-to-detection, any limit is a guess. A limit of 50 per day is useless if detection needs 20 queries. It is also unnecessarily strict if detection needs 10,000. Rate limiting also cannot stop attackers who spread queries across many accounts, whereas a per-query floor holds under any number of accounts. The rate-limit baseline experiment will show whether a naive limit happens to suffice on these benchmarks. If it does, the bound's value is to certify that limit.
Why not just add noise to returned poses? Chelani et al. (2023) already find that this degrades precision for legitimate users. Consistency checks over many queries can also average the noise away. Our matched-accuracy comparison tests this directly.
Why not just measure the existing attack's query count and skip the theory? This is the most serious objection. An empirical count only bounds the attackers we happened to build, and adaptive attackers built on feed-forward reconstruction are improving quickly. The theory is valuable only if it predicts the empirical trends: how cost scales with $M$ and with the spread threshold. If our strongest attacker lands far above the bound, the bound is loose and mainly useful as a certificate. If the attacker comes close to it, the theory has identified the true cost of the attack.
Why bring in quantum query complexity at all? Real attackers are classical. We use the adversary method because it produces classical randomized bounds too, as in Aaronson. The quantum bound comes for free and is reported as a worst-case bound, not as the main contribution.
Proposed Experiments
Detection experiments use IKEA-Scenes and IKEA-Objects, which contain 7 rooms and 38 objects. The metrics are precision, recall, and queries needed to reach recall 0.8. Transfer to realistic rooms is tested on ScanNet and RIO10. Legitimate-user cost is measured on 7-Scenes, 12-Scenes and RIO10 as median translation and rotation error and refusal rate.
The decisive check is a scaling plot of queries-to-detection against the number of candidate placements $M$ and the spread threshold, overlaid with the $M/k$ prediction. The central claim holds if three conditions are met. First, the adaptive attacker's cost grows roughly linearly in $M/k$. Second, clutter-embedded probes fail to shrink the effective $k$ below the spread threshold. Third, legitimate refusals stay under a few percent with no loss of localization accuracy. If generated clutter defeats the spread rule, the coverage rule fails as a defense. We would then report the $k$ the attacker achieves as the actual threat level.
References
- Privacy-Preserving Representations are not Enough - Recovering Scene Content from Camera Poses
- GS-LRM: Large Reconstruction Model for 3D Gaussian Splatting
- Lower bounds for local search by quantum arguments
- Quantum certificate complexity
- How Privacy-Preserving are Line Clouds? Recovering Scene Details from 3D Lines
- Obfuscation Based Privacy Preserving Representations Are Recoverable Using Neighborhood Information
- Efficient Privacy-Preserving Visual Localization Using 3D Ray Clouds
- Gaussian Splatting Feature Fields for (Privacy-Preserving) Visual Localization