The signed CHK compiler (4.3)
DefinitionRestrictedDec_Supplement_signedCHKchosen-ciphertext-securityfunctional-decryptionp2o-gran-per-chapterp2o-plan-paperp2o-v1public-key-encryptionsecurity-hierarchy
For an observation with , a residual scheme , an IBE with identity space , a PRF and a one-time signature :
- as in the unsigned compiler: , .
- : , , , , ; .
- : reject malformed encodings and any with ; otherwise , ; if or output ; else output .
The signature covers both encrypted components and is verified under the key used as the IBE identity.
Formalization Note is the tuple code of ; the identity is the verification-key string; an identity outside is malformed.
Definition code
import Mathlib
import Definitions.Def_BeyondDS_tup
import Definitions.Def_RestrictedDec_PKE
import Definitions.Def_RestrictedDec_Supplement_interact
import Definitions.Def_RestrictedDec_Supplement_Obs
import Definitions.Def_RestrictedDec_Supplement_IBE
import Definitions.Def_RestrictedDec_Supplement_PRF
import Definitions.Def_RestrictedDec_Supplement_OTS
open QAlgorithms.Complexity
set_option autoImplicit false
namespace RestrictedDec
namespace Supplement
open Classical in
/-- The **signed CHK-based compiler** (4.3) for the observation `q` with `Valid_q`, `Rep_q`, built
from a residual scheme `R`, an IBE `I`, a PRF `P` and a one-time signature `S`:
1. `KeyGen(1^λ)`: `(pk_R, sk_R) ← KeyGen_R`, `(mpk, msk) ← Setup_I`, seed `k`;
`pk = (pk_R, mpk)`, `sk = (sk_R, msk, k)`;
2. `Enc_pk(m)`: `(ssk, vk) ← SGen(1^λ)`, `y = q(m)`, `d ← Enc_R(pk_R, m)`,
`a ← IEnc(mpk, vk, y)`, `σ ← Sign_ssk(⟨d, a⟩)`, `C = (d, vk, a, σ)`;
3. `Dec_sk(C)`: reject malformed encodings (including an identity `vk ∉ Id_λ`) and any `C` with `Vrf_vk(⟨d, a⟩, σ) = 0`; otherwise
`sk_vk = Extract_I(msk, vk; PRF_k(vk))`, `y = IDec(sk_vk, a)`; if `y = ⊥` or
`Valid_q(1^λ, y) = 0` output `⊥`; else output `Norm_q(y, Dec_R(sk_R, d))`.
Nguyen–Susilo, STOC 2027 submission (manuscript sha256 6aeac40c…), §4.2, (4.3), pp.24–25.
**Formalization Note.** An identity outside the IBE's public identity space `Id_λ` is treated as a
malformed component and rejected. `⟨d, a⟩` is `tup [d, a]` and `C` is `tup [d, vk, a, σ]`; "malformed" means
"not the code of a 4-tuple". The identity is the verification key string itself (its canonical
injective encoding). Encryption coins are split as `SGen`, `Enc_R`, `IEnc`, `Sign`. -/
noncomputable def signedCHK (M Id : ℕ → Str → Prop) (o : Obs) (R : PKE) (I : IBE) (P : PRF)
(S : OTS) : PKE where
keyCoins := fun lam => R.keyCoins lam + I.setupCoins lam + P.keyCoins lam
encCoins := fun lam => S.keyCoins lam + R.encCoins lam + I.encCoins lam + S.signCoins lam
keyGen := fun lam r =>
(BeyondDS.tup [(R.keyGen lam (cL (cL r))).1, (I.setup lam (cR (cL r))).1],
BeyondDS.tup [(R.keyGen lam (cL (cL r))).2, (I.setup lam (cR (cL r))).2, P.gen lam (cR r)])
enc := fun lam pk m ρ =>
let kS := S.gen lam (cL (cL (cL ρ)))
let d := R.enc lam (fld pk 0) m (cR (cL (cL ρ)))
let a := I.enc lam (fld pk 1) kS.2 (o.q lam (some m)) (cR (cL ρ))
BeyondDS.tup [d, kS.2, a, S.sign lam kS.1 (BeyondDS.tup [d, a]) (cR ρ)]
dec := fun lam sk C =>
match parseTup 4 C with
| some [d, vk, a, σ] =>
if Id lam vk ∧ S.vrf lam vk (BeyondDS.tup [d, a]) σ = true then
match I.dec lam (I.extract lam (fld sk 1) vk
(coinsOf (I.extCoins lam) (P.eval lam (fld sk 2) vk))) a with
| some y => if o.valid lam y then norm M o lam y (R.dec lam (fld sk 0) d) else none
| none => none
else none
| _ => none
end Supplement
end RestrictedDec
Source
Nguyen–Susilo, Between CPA and CCA: Security Hierarchies for Restricted Decryption, STOC 2027 submission (manuscript sha256 6aeac40c…), §4.2, (4.3), pp.24–25