IND-CPA security over (Definition 2)
DefinitionRestrictedDec_Supplement_INDCPAMchosen-ciphertext-securityfunctional-decryptionp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryptionsecurity-hierarchy
In the experiment , keys are generated, receives , chooses valid equal-length and receives ; the output is its final bit. The advantage is
and is IND-CPA secure over if this advantage is negligible for every uniform PPT adversary. There is no correctness clause.
This is the security assumption on the residual scheme and the label scheme of the compilers.
Formalization Note For this is the published RestrictedDec.INDCPA (proved in the sanity file).
Definition code
import Mathlib
import Definitions.Def_NoisyOWMPC_Negligible
import Definitions.Def_RestrictedDec_Supplement_runGameM
open QAlgorithms.Complexity
open Polynomial
set_option autoImplicit false
namespace RestrictedDec
namespace Supplement
/-- The experiment `Exp^{cpa,b}_E(A, λ)` over the message space `M` (Definition 2): keys
`(pk, sk) ← KeyGen(1^λ)`, the adversary gets `pk`, chooses valid equal-length `(m₀, m₁)`, receives
`c* ← Enc_pk(m_b)`, and the output is its final bit `b′`. There is no oracle.
Nguyen–Susilo, STOC 2027 submission (manuscript sha256 6aeac40c…), Definition 2, App. A.1, p.29.
**Formalization Note.** The interaction is `runGameM` with an oracle that never answers, so a
"query" move is a no-op; an invalid challenge or exhausted fuel gives `b′ = 0` for both `b`. -/
noncomputable def cpaExpM (M : ℕ → Str → Prop) (E : PKE) (A : Adversary) (lam : ℕ) (b : Bool) :
PMF Bool :=
(E.keyLaw lam).bind fun k =>
runGameM A E M lam k.1 (fun _ _ _ => none) b (A.p.eval lam + 1) none [] k.1
/-- `Adv^cpa_E(A, λ) = |Pr[Exp^{cpa,1}_E(A, λ) = 1] − Pr[Exp^{cpa,0}_E(A, λ) = 1]|` (Definition 2,
p.29). -/
noncomputable def advCPAM (M : ℕ → Str → Prop) (E : PKE) (A : Adversary) (lam : ℕ) : ℝ :=
|((cpaExpM M E A lam true) true).toReal - ((cpaExpM M E A lam false) true).toReal|
/-- **IND-CPA** security over `M`: every uniform PPT adversary has negligible distinguishing
advantage (Definition 2, p.29: "The scheme is IND-CPA secure if this advantage is negligible for
every PPT adversary"). No correctness clause, as printed. For `M λ m := m.length = n λ` this is the
published `RestrictedDec.INDCPA`. -/
def INDCPAM (M : ℕ → Str → Prop) (E : PKE) : Prop :=
∀ A : Adversary, A.Valid → NoisyOWMPC.Negligible (advCPAM M E A)
end Supplement
end RestrictedDec
Source
Nguyen–Susilo, Between CPA and CCA: Security Hierarchies for Restricted Decryption, STOC 2027 submission (manuscript sha256 6aeac40c…), Definition 2, App. A.1, p.29