Sequential Confidence Amplification for Noisy Binary Oracles (SPRT-style)

Updated 13 Sep 2026

• •

  What it is

  • •

    A general statistical technique for extracting a reliable answer from a binary oracle whose responses are corrupted by random noise — as long as the noise isn't a perfectly uncorrelated 50/50 coin flip, repeated querying can drive the probability of a wrong conclusion arbitrarily close to zero. Rather than committing to a fixed number of samples per question up front (wasteful for easy cases, insufficient for hard ones), a sequential test accumulates evidence one query at a time and stops as soon as the accumulated evidence crosses a confidence threshold — this is the core idea behind Wald's Sequential Probability Ratio Test (SPRT), and it generalizes cleanly to "keep querying whichever candidate answer currently looks most likely, stop once it's convincingly ahead."

• •

  When to apply

  • •

    Any noisy oracle scenario with more than a simple two-outcome guess — e.g. picking the correct one of 16 hex-digit candidates per byte position — where a fixed, evenly-split query budget per candidate would waste queries confirming already-clear answers while starving genuinely close calls.

• •

  Symbols and assumptions

  • •

    $H_1,H_0$ are two candidate explanations of an oracle reply $Y$. Let $p_1=P(Y=1\mid H_1)$ and $p_0=P(Y=1\mid H_0)$. A log-likelihood ratio measures evidence for $H_1$ over $H_0$.

• •

  Math — step by step

  • •
    1. Start with prior log-odds $L_0=\log(P(H_1)/P(H_0))$. For reply 1 add $\log(p_1/p_0)$; for reply 0 add $\log((1-p_1)/(1-p_0))$. Independent conditional observations let their likelihoods multiply and their logs add.
  • •
    2. Posterior probability is $P(H_1\mid Y)=1/(1+e^{-L})$ under this model. Stop when confidence is sufficient; a fixed sample count can waste queries on obvious candidates.
  • •
    3. Independence and calibrated reply probabilities are assumptions. Repeated correlated replies can make this formula overconfident. Use a query budget, allow an inconclusive outcome, and validate recovered plaintext separately.
• •

  Worked example

  • •

    Equal priors and symmetric accuracy 0.75 give $p_1=0.75,p_0=0.25$. A 1 adds $\log3$; a 0 subtracts $\log3$.

  • •

    Replies $1,1,0,1$ give $L=2\log3=\log9$. Posterior odds are 9 to 1, or probability $9/(9+1)=0.9$.

  • •

    Five more 1s than 0s give odds $3^5=243$ and probability $243/244\approx0.9959$. This number is conditional on the noise model, not a universal guarantee.

• •

  Python

  • •

    def recover_candidate(oracle, make_query, n_candidates, threshold):
            score = [0] * n_candidates
            while max(score) < threshold:
                i = score.index(max(score))
                score[i] += 1 if oracle(make_query(i)) else -1   # sign convention: calibrate against the actual noise model
            return score.index(max(score))
    

• •

  Related

  • •

    Noisy Padding Oracle Attack (Statistical Amplification)

• •

  Cards

  • •

    Why is a sequential test more query-efficient than a fixed, evenly-split sampling budget?

    • •

      It concentrates queries on genuinely ambiguous candidates instead of wasting them confirming answers that are already statistically clear.

  • •

    What's the one property a noisy oracle must retain for this technique to work at all?

    • •

      Some correlation (positive or negative) with the truth — a perfectly 50/50 random oracle carries zero information no matter how it's sampled.

◌ Explore connections in Graph view