The enlarged parameter of Construction 6.4
DefinitionCertRandQROM_Supplement_leverLamcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
For a constant , a security parameter and a min-entropy threshold , Construction 6.4 runs Construction 6.2 at the security parameter
Then , so the min-entropy guarantee of Construction 6.2 at gives bits (complexity leveraging).
Formalization Note The power is a real power and the ceiling the natural-number ceiling. The second quantity of Construction 6.4, , is only passed to Prove and Verify of Construction 6.2, which ignore it.
Definition code
import Mathlib
set_option autoImplicit false
namespace CertRandQROM.Supplement
/-- **The enlarged security parameter of Construction 6.4** (p.30 of Coladangelo et al.,
arXiv:2608.31112, sha256 b75095a2…):
`λ(λ′, h′∞) = max{λ′, ⌈(3 h′∞)^{1/c}⌉}`, for the constant `c ∈ (0, 1/2)`.
**Formalization Note** The power is the real power `(3h′)^{1/c}` and the ceiling is the natural
ceiling; at `h′ = 0` the value is `λ′`. The companion threshold
`h∞(λ′, h′∞) = ⌈λ(λ′, h′∞)^c/3⌉` of Construction 6.4 is passed to `Prove` and `Verify` of
Construction 6.2, which ignore it, so it needs no definition. -/
noncomputable def leverLam (c : ℝ) (l' h' : ℕ) : ℕ :=
max l' ⌈((3 * h' : ℕ) : ℝ) ^ (1 / c)⌉₊
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Construction 6.4, p.30 (PDF p.32)