05 — Rejection Sampling

The Leakage Problem

Recall the signature equation:

$\displaystyle z = y + c \cdot s_1$

Where:

• y is a random mask (known distribution, wide)
• c is the challenge (derived from message and commitment)
• s₁ is the secret key (unknown to attacker, narrow distribution)
• z is published as part of the signature

If we simply output z, an attacker who sees many signatures can:

1. Collect many (c, z) pairs
2. Set up a system of linear equations: zᵢ = yᵢ + cᵢ·s₁
3. Solve for s₁ using statistical techniques

The mask y must hide s₁ completely.

The Solution: Rejection Sampling

Instead of always outputting z, we check whether z "looks like" it came from the y distribution (without s₁ contribution):

while True:
    y = sample_from_wide_distribution()
    w = A · y
    w1 = HighBits(w)
    c = Hash(message || w1)
    z = y + c * s1
    
    # REJECTION CHECK:
    # Does z look like it came from the y distribution?
    if norm(z, infinity) < BOUND:
        break  # Accept! Output z.
    # else: Reject and try again.

Why This Works

Intuition: If y is MUCH wider than c·s₁, then z = y + c·s₁ looks almost like just y. The secret contribution is buried in noise.

Mathematically: The distribution of z (conditioned on acceptance) is statistically close to the distribution of y. An attacker seeing z learns essentially nothing about s₁.

The Distributions

The mask y is sampled uniformly from [-γ₁, γ₁]. The secret s₁ has small coefficients. Even after multiplying by c (which has small coefficients), c·s₁ is tiny compared to y.

Acceptance Probability

How often does the check pass?

The acceptance probability depends on the ratio of bounds to distributions. ML-DSA tunes these so signing is fast while security is maintained.

Why Not Just Add More Noise?

Question: Why not make y even wider so rejection is always accepted?

Answer: Then z would be very large, and the verifier's check ||z|| < bound would fail. There's a trade-off:

• Wider y → Easier rejection, but larger z → may fail verification bound
• Narrower y → Smaller z, but more rejections → slower signing

ML-DSA finds the sweet spot where:

• Rejection is reasonably fast (2–4 tries)
• z is small enough to pass verification
• Security is provable via statistical arguments

Formal Security Argument

The proof uses the Rényi divergence (a measure of distribution similarity):

1. Define the "ideal" distribution: just y (the mask, no secret)
2. Define the "real" distribution: z = y + c·s₁ after rejection
3. Show that the Rényi divergence between ideal and real is small (e.g., < 1.01)
4. If an attacker can break the real scheme, they can break the ideal scheme with similar effort
5. The ideal scheme is secure because it reveals nothing about s₁

This is the Fiat-Shamir with Aborts paradigm, pioneered by Lyubashevsky (2009).

Comparison with Other Schemes

Resources

• Lyubashevsky, "Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures" (2009), ASIACRYPT.
• Bai & Galbraith, "An improved compression technique for signatures based on learning with errors" (2014), CT-RSA.
• Kiltz et al., "A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model" (2018), EUROCRYPT.