Statistical distance, TDHF security, IND-CPA security and the Section A.1 encryption scheme
DefinitionTrapdoorHCF_CCA2_Supplement_CPAThis file fixes four notions used by the chosen-plaintext half of the source.
- Statistical distance. For probability mass functions on an arbitrary set ,
The sum is taken over every outcome; no finiteness of is assumed.
-
TDHF security (Definition 10). For a trapdoor hardcore function with hardcore length , sample and . A uniform probabilistic polynomial-time adversary receives , where in the real experiment and is a uniform string of bits in the random one. Its advantage is the absolute difference of its output-one probabilities. is secure if it is perfectly correct and every such adversary has negligible advantage.
-
IND-CPA security (Definition 2 with atk = CPA). The classical two-stage game with no decryption access: the first stage sees and names ; invalid messages make the experiment output ; the second stage receives and its state. The scheme is IND-CPA secure if every uniform PPT adversary has negligible advantage. No correctness is part of this notion.
-
The Section A.1 scheme . Keys are those of . To encrypt , sample an input and output . To decrypt , compute ; output if , and otherwise .
These are the objects of Theorems 1, 5 and 6 and the base of the lossy constructions.
Formalization Note The adversary model, the stage runner runStage and the advantage are the published base definitions; the IND-CPA game is the base IND-CCA2 game with both oracles removed. Ciphertext pairs are tuple codes. Decryption of also returns when , which happens only for strings outside the ciphertext space and makes decryption output elements of .
import Mathlib
import Definitions.Def_TrapdoorHCF_CCA2_Constructions
open QAlgorithms.Complexity
set_option autoImplicit false
namespace TrapdoorHCF.CCA2.Supplement
open TrapdoorHCF.CCA2
/-- Notation 8, p.10: statistical distance `Δ(X,Y) = ½ Σ_ω |Pr[X=ω] − Pr[Y=ω]|`, over every
outcome `ω` of an arbitrary (possibly infinite) type. On PMFs the series is summable. -/
noncomputable def sd {α : Type} (p q : PMF α) : ℝ :=
(1 / 2) * ∑' ω, |(p ω).toReal - (q ω).toReal|
/-- Definition 10, p.16. One oracle-free stage on input `(1^λ, pk, Eval(pk,x), z)`, with
`x ← D_λ` and `z` the designated value (`b = false`) or `l(λ)` uniform bits (`b = true`).
The first bit of the output is the guess; exhaustion outputs 0. -/
noncomputable def expTDHF (l : ℕ → ℕ) (T : TDHF) (A : RestrictedDec.Adversary) (b : Bool)
(lam : ℕ) : PMF Bool := do
let keys ← T.keyLaw lam
let x ← T.inputLaw lam
let u ← coinsLaw (l lam)
let y := T.eval lam keys.1 x
let z := if b then List.ofFn u else T.hEval lam keys.1 x
let r ← runStage A lam (fun _ => none) (A.p.eval lam + 1) []
(BeyondDS.tup [encNat lam, keys.1, y, z])
pure ((r.output.getD []).headD false)
noncomputable def advTDHF (l : ℕ → ℕ) (T : TDHF) (A : RestrictedDec.Adversary) : ℕ → ℝ :=
advantage (expTDHF l T A false) (expTDHF l T A true)
/-- Definition 10, p.16: "A perfectly correct TDHF is secure if" every uniform PPT adversary
has negligible advantage. Perfect correctness (Definition 9) is part of the notion. -/
def IsSecureTDHF (l : ℕ → ℕ) (T : TDHF) : Prop :=
T.PerfectlyCorrect ∧
∀ A : RestrictedDec.Adversary, A.Valid → NoisyOWMPC.Negligible (advTDHF l T A)
/-- Definition 2, p.11, with atk = CPA: the base `expCCA2` with no decryption access in either
stage. Invalid messages and exhausted stages output 0 in both experiments. -/
noncomputable def expCPA (n : ℕ → ℕ) (P : RestrictedDec.PKE)
(A : RestrictedDec.Adversary) (b : Bool) (lam : ℕ) : PMF Bool := do
let keys ← P.keyLaw lam
let pre ← runStage A lam (fun _ => none) (A.p.eval lam + 1) []
(BeyondDS.tup [encNat lam, keys.1])
match pre.output with
| none => pure false
| some out =>
let ms := BeyondDS.untup out
let m0 := ms.getD 0 []
let m1 := ms.getD 1 []
if m0.length = n lam ∧ m1.length = n lam ∧ m0.length = m1.length then
let ct ← P.encLaw lam keys.1 (if b then m1 else m0)
let post ← runStage A lam (fun _ => none) pre.fuel pre.state
(BeyondDS.tup [ct, pre.state])
pure ((post.output.getD []).headD false)
else pure false
noncomputable def advCPA (n : ℕ → ℕ) (P : RestrictedDec.PKE)
(A : RestrictedDec.Adversary) : ℕ → ℝ :=
advantage (expCPA n P A false) (expCPA n P A true)
/-- Definition 2, p.11: IND-CPA security. No correctness clause. -/
def INDCPA (n : ℕ → ℕ) (P : RestrictedDec.PKE) : Prop :=
∀ A : RestrictedDec.Adversary, A.Valid → NoisyOWMPC.Negligible (advCPA n P A)
/-- Bitwise exclusive or `⊕` of two strings (of equal length wherever it is used). -/
def xorStr (a b : Str) : Str := List.zipWith xor a b
/-- Section A.1, p.32. The encryption randomness is an input `r ∈ D_λ`, drawn by the TDHF
sampler on the encryption coins. The ciphertext `(ct1, ct2)` is the tuple code
`tup [Eval(pk,r), hEval(pk,r) ⊕ m]`. Decryption returns `⊥` when `pInv` does (p.32), and also
when `|ct2| ≠ |z|`, which happens only outside the ciphertext space `C_λ`. -/
def kemPKE (T : TDHF) : RestrictedDec.PKE where
keyCoins := T.keyCoins
encCoins := T.sampCoins
keyGen := T.keyGen
enc := fun lam pk m r =>
BeyondDS.tup [T.eval lam pk (T.samp lam r), xorStr (T.hEval lam pk (T.samp lam r)) m]
dec := fun lam sk c =>
let fields := BeyondDS.untup c
let ct1 := fields.getD 0 []
let ct2 := fields.getD 1 []
match T.pInv lam sk ct1 with
| none => none
| some z => if z.length = ct2.length then some (xorStr z ct2) else none
end TrapdoorHCF.CCA2.Supplement