Dense masks against uniform sequence tests #
A pseudoentropy pair's prediction bound forces every efficient sequence test to admit a dense soft mask with small distinguishing gap. Otherwise the concrete sequence learner constructs one uniform strict PPT predictor violating that bound. The mask's nonzero probabilities have an explicit inverse-polynomial lower bound, needed for the subsequent extraction estimate.
The density and repetition schedules are efficiently computable. The indexed theorem gives one eventual threshold for every member of a polynomial-size family of tests and density numerators. The density need only be valid and below the entropy threshold where the conclusion is used. Neither the program nor its parameters are chosen separately at each input length.
Main results #
HasGap.eventually_exists_indexed_mask: one threshold for all tests in an efficient family.HasGap.eventually_exists_mask: specialize to a single uniform sequence test.
References #
- Thomas Holenstein, Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness, TCC 2006, Section 5, Games 3--5 and the following prediction reduction. [Hol06].
- Thomas Holenstein, Key Agreement from Weak Bit Agreement, STOC 2005, Section 2.2. [Hol05]. We use the clocked soft-mask implementation, with all sampling failures included.
Adapted from the cslib crypto branch at
5ff69ca93402e7c947208dc56396d6d86203ccd8.
All tests in a uniformly efficient polynomial-size family eventually admit dense soft masks with small distinguishing gap whenever their density is valid. The common eventual threshold allows arbitrary choices of index in the proof without supplying that choice to the program.
Every uniform sequence test eventually admits a dense soft mask with small distinguishing gap. The mask may depend on the test and parameter; its positive probabilities are uniformly bounded below by the configured dyadic rate. The statement exposes no boosting state.