Query Rate and Composition Limit¶

Policy — instantiates Side-Channel Leakage Containment

Caps how many queries an observer may make and which combinations they may compose, so a protected fact can't be reconstructed by differencing many individually-permitted answers.

Every single answer can be within policy while the sequence of answers is not. Ask for an aggregate, then ask for the same aggregate over a set that differs by one record, and the difference reveals the record — even though each query was individually allowed. Query Rate and Composition Limit governs the query stream rather than any one response: it models the adversary's querying capability and denies the volumes and combinations that let permitted answers be differenced into a protected fact. Its defining move is to treat leakage as cumulative across queries, not per-response — it is the one sibling that constrains the observer's interaction budget instead of reshaping any output's content.

Example¶

A genomic data-sharing "beacon" answers narrow membership questions — does this dataset contain a record with a given variant? — so researchers can discover useful cohorts without raw data leaving the vault. Each yes/no is harmless in isolation. But a long series of overlapping membership queries can, in principle, triangulate whether one specific individual's data is present, a well-known concern for such services.

The limit closes that path without shutting the service. It caps queries per identity and per window, refuses near-duplicate queries that differ only enough to difference against a prior answer, and requires that a principal's query set stay within a cumulative budget before results are throttled. A detection log watches for the fingerprint of a reconstruction sweep — many tightly-overlapping queries from one source — and flags it for review. A researcher exploring real cohorts stays well inside the budget; the differencing pattern runs into the wall and into the log.

How it works¶

Encode the allowed query model. Turn the assumed adversary into a concrete policy — which query shapes, at what rate, in what combinations a principal may issue.
Budget across the interaction, not the answer. Meter queries per identity and per time window, and treat a set of overlapping queries as spending against one cumulative budget.
Deny the differencing compositions. Block or delay query pairs whose whole purpose is to isolate a single record by subtraction.
Log the reconstruction fingerprint. Record query patterns that resemble a sweep and route them to review rather than silently serving them.

Tuning parameters¶

Rate ceiling — queries per principal per window. Tighter stops reconstruction sooner but throttles legitimate heavy users.
Composition strictness — how much overlap between successive queries is tolerated before they're refused. Stricter closes differencing but blocks some honest analysis.
Identity granularity — per-user, per-organization, or global budgeting. Coarser resists Sybil evasion but penalizes shared-source users.
Detection sensitivity — how sweep-like a pattern must look before it's flagged. Higher sensitivity catches subtler probing at the cost of false positives on power users.
Breach response — throttle, hard-block, or hold-for-review when the budget is hit. The softer the response, the more it leans on the log.

When it helps, and when it misleads¶

Its strength is catching the leak that per-answer controls structurally miss: reconstruction by repetition, where no single response is at fault and only the pattern betrays intent. It is also cheap relative to redesigning the outputs themselves, and its log turns silent probing into a reviewable event.

Its failure modes cluster around identity and generosity. A patient adversary splitting queries across colluding or Sybil identities defeats a per-identity budget, so the granularity dial is load-bearing. Set the limits loosely — the usual response to user complaints — and the protection quietly evaporates while the dashboard still shows a control in place. And the policy is easily run backwards, its thresholds rationalized after a breach rather than derived from the adversary model before one. The classic demonstration that individually-permitted aggregate queries can be composed to reconstruct suppressed values is the tracker attack on statistical databases; query auditing and composition limits are its standard countermeasure.^[1] The discipline that keeps this honest is to budget across identities rather than within them, pair it with suppression so each answer is also individually safe, and actually review the log.

How it implements the components¶

This policy fills the adversary-modeling and probe-detection components — the interaction-side machinery, not the output-side controls:

adversary_prior_and_query_model — operationalizes the assumed observer into concrete limits on which queries, how many, and in what combinations may be issued.
probe_detection_and_review_log — records and flags query patterns shaped like a reconstruction sweep, creating the evidence trail for review.

It does not equalize or reshape any response — output uniformity belongs to Response Padding or Coarsening — and it does not decide how much residual risk is acceptable, which is the Residual Leakage Review Board's role.

Instantiates: Side-Channel Leakage Containment — constrains the query stream so permitted answers can't be composed into a protected fact.
Consumes: Side-Channel Inventory Workshop supplies the observation surface and adversary picture the limits are set against.
Sibling mechanisms: Threshold Suppression · Side-Channel Inventory Workshop · Residual Leakage Review Board · Response Padding or Coarsening · Secret-Independent Resource Scheduling · Side-Channel Regression Test · Privacy-Preserving Telemetry View · Batching and Delayed Release · Broker Visibility Partitioning · Cache Partitioning or Flush Rule · Constant Response Envelope · Controlled Noise Injection · Differential Observation Test · Error Message Normalization · Metadata Minimization Filter

Notes¶

Rate limiting and suppression are complements, not substitutes: Threshold Suppression makes each individual answer safe, while this limit makes the sequence safe. Neither alone closes differencing — a suppressed cell can still be reconstructed by querying around it, so the two are deployed together.

References¶

[1] In statistical-database security, a tracker is a set of queries constructed so that individually-permitted aggregate answers can be combined by subtraction to isolate a value the database meant to suppress (Denning and colleagues). Query auditing and composition limits are the classic defense against this cumulative-disclosure problem. ↩