Strict asymptotic inclusion
DefinitionRestrictedDec_Supplement_SecSubsetneqchosen-ciphertext-securityfunctional-decryptionp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryptionsecurity-hierarchy
For families and a timing , over means:
- every efficient scheme over (polynomial-time, decrypting into , App. A.1) in is in ; and
- one efficient scheme lies in but not in .
This is the paper's asymptotic notion of strictness: a single uniformly constructible scheme satisfies the weaker notion while a single PPT attack breaks the stronger one, possibly only on infinitely many security parameters.
Definition code
import Mathlib
import Definitions.Def_RestrictedDec_Supplement_IsSchemeM
import Definitions.Def_RestrictedDec_Supplement_SecM
open QAlgorithms.Complexity
set_option autoImplicit false
namespace RestrictedDec
namespace Supplement
/-- **Strict asymptotic inclusion** `Sec^t(𝓖) ⊊ Sec^t(𝓕)` over the message space `M`: every
(efficient) scheme over `M` in `Sec^t(𝓖)` is in `Sec^t(𝓕)`, and one efficient scheme is in `Sec^t(𝓕)` but not in `Sec^t(𝓖)`.
Nguyen–Susilo, STOC 2027 submission (manuscript sha256 6aeac40c…), §2.3, p.15 ("An inclusion is
strict in the asymptotic sense only when a single uniformly constructible encryption scheme
satisfies the weaker notion and a single PPT attack has nonnegligible advantage for the stronger one
(possibly on an infinite subsequence of security parameters)").
**Formalization Note.** "Not in `Sec^t(𝓖)`" is the negation of `SecM`; for a correct scheme it says
that some uniform PPT adversary has non-negligible advantage. The inclusion ranges over the schemes
of the paper, those with message space `M` (`IsSchemeM`: polynomial-time, and `Dec` outputs in
`M_λ ∪ {⊥}`, App. A.1, p.29). Over arbitrary `PKE` values it would be false: a decryption output
outside `M_λ` is not covered by the simulation `𝓕 ⪯ 𝓖` of §3.1, which is stated on `M_⊥` only. -/
def SecSubsetneq (t : Timing) (M : ℕ → Str → Prop) (G F : Family) : Prop :=
(∀ P : PKE, IsSchemeM M P → SecM t M G P → SecM t M F P) ∧
∃ P : PKE, IsSchemeM M P ∧ SecM t M F P ∧ ¬ SecM t M G P
end Supplement
end RestrictedDec
Source
Nguyen–Susilo, Between CPA and CCA: Security Hierarchies for Restricted Decryption, STOC 2027 submission (manuscript sha256 6aeac40c…), §2.3, p.15