Efficiently found separating witness for (§3.3)
DefinitionRestrictedDec_Supplement_SepWitnesschosen-ciphertext-securityfunctional-decryptionp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryptionsecurity-hierarchy
An efficiently found separating witness for the adjacent classes over is a polynomial-time machine mapping to such that
- at every : , , and for every admissible ;
- on infinitely many : describes an admissible with .
This is the separation condition of §3.3 used by Theorems 3 and 4.
Formalization Note Classes are -indexed families of descriptions, which covers the paper's binary-indexed classes along a uniformly computable index sequence.
Definition code
import Mathlib
import Definitions.Def_BeyondDS_tup
import Definitions.Def_RestrictedDec_Family
open QAlgorithms.Complexity
open Filter
set_option autoImplicit false
namespace RestrictedDec
namespace Supplement
/-- An **efficiently found separating witness** for the adjacent pair of classes `(𝓕, 𝓖)` over
the message space `M`: one polynomial-time machine maps `1^λ` to `tup [m₀(λ), m₁(λ), d*(λ)]` such
that
1. at every `λ`, `m₀(λ), m₁(λ) ∈ M_λ`, `|m₀(λ)| = |m₁(λ)|`, and `F(m₀(λ)) = F(m₁(λ))` for every
admissible `F ∈ 𝓕`;
2. on infinitely many `λ`, `d*(λ)` is an admissible description of some `G* ∈ 𝓖` with
`G*(m₀(λ)) ≠ G*(m₁(λ))`.
Nguyen–Susilo, STOC 2027 submission (manuscript sha256 6aeac40c…), §3.3, pp.18–19 ("The messages
and a description of F⋆_i must be produced by a single polynomial-time algorithm from 1λ and the
binary index i. For a varying index, the two valid equal-length messages must agree under every
weaker function at all security parameters. The stronger function need distinguish them on only
infinitely many parameters. On an inactive parameter the algorithm may return two identical default
messages."); Theorem 3, p.19.
**Formalization Note.** The classes are λ-indexed families (`Family` descriptions are read at each
`λ`), which covers the paper's classes `𝓕_{i(λ)}` along a uniformly computable index sequence. -/
def SepWitness (M : ℕ → Str → Prop) (F G : Family) : Prop :=
∃ (w : Str → Str) (m0 m1 d : ℕ → Str), PolyTimeComputable w ∧
(∀ lam, w (encNat lam) = BeyondDS.tup [m0 lam, m1 lam, d lam]) ∧
(∀ lam, M lam (m0 lam) ∧ M lam (m1 lam) ∧ (m0 lam).length = (m1 lam).length ∧
∀ d', F.admissible lam d' = true → F.eval lam d' (some (m0 lam)) = F.eval lam d' (some (m1 lam))) ∧
∃ᶠ lam in atTop, G.admissible lam (d lam) = true ∧
G.eval lam (d lam) (some (m0 lam)) ≠ G.eval lam (d lam) (some (m1 lam))
end Supplement
end RestrictedDec
Source
Nguyen–Susilo, Between CPA and CCA: Security Hierarchies for Restricted Decryption, STOC 2027 submission (manuscript sha256 6aeac40c…), §3.3, pp.18–19; Theorem 3, p.19