§7, Choosing the Prime — Sampling a prime in the dyadic interval
ProvedGenericGroupWE.Main.sec_7_primecomplexity-theorycryptographygeneric-groupsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
There is an absolute positive integer and one bounded polynomial-time probabilistic program implementing the specified independent uniform dyadic sampler. For every and , it uses trials, returns a prime in on success, and otherwise returns the common abort symbol, with
The program's actual Turing transition time is polynomial. Sampling has no message-bit input, so its failure event is bit independent.
Differences from the source:
- generalization: the application uses m>=16n and n>=2 → every m>=1 and n>=0; reason: dyadic prime density admits one absolute constant on this larger domain; m=0 would instead give the prime-free interval [1,2) and is excluded
- encoding: ceil(C m(n+2)) for an absolute real constant → C is chosen as a positive integer and the trial count is exactly C m(n+2); reason: enlarging the constant to an integer preserves the bound and makes the ceiling redundant
- encoding: polynomial-time algorithms on encoded data → a single CookLevin polynomial-step implementation for each length-faithful encoded map; reason: the time predicate bounds actual Turing steps; clocks also bound rounds and state length
Preamble
import Definitions.Def_GenericGroupWE_Main_PrimeSampling import Definitions.Def_GenericGroupWE_Main_Complexity
Formal statement
namespace GenericGroupWE.Main
theorem sec_7_prime :
∃ C : ℕ, 0 < C ∧ ∃ P : OracleProgram,
CookLevin.IsPolyTimeComputable P.next ∧ ∀ (m n : ℕ), 1 ≤ m →
P.run false (primeSamplingInput m n) none =
(dyadicPrimeSampler m (C*m*(n+2))).map primeSamplingOutput ∧
probability (dyadicPrimeSampler m (C*m*(n+2))) (· = none) ≤
(2 : ℝ)^(-(n : ℝ)-2) ∧
∀ p : PrimeOrder, some p ∈ (dyadicPrimeSampler m (C*m*(n+2))).support →
2^m ≤ p.val ∧ p.val < 2^(m+1) := by sorry
end GenericGroupWE.Main
Source
Hair and Sahai, Witness Encryption via Prime-Order Generic Groups, STOC 2027 submission #47 (PDF built 2026-11-02; SHA-256 0b7f14e2db9bb3e199883ab907f854b7b5884c7c9f3d1e4c306bb71e89b659cb), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/47.pdf, §7, Choosing the Prime, PDF p. 30 (printed p. 29).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.