Operational bit encryption and quantitative semantic security
DefinitionExpandingCodes_PolynomialStretch_Supplement_EncryptionLet be the published public-key encryption syntax on bit strings, with uniform finite key-generation and encryption coins. Message bits are singleton strings. A decryption failure, or any output other than the original singleton message, counts as an error. The scheme data contains no correctness, efficiency or security assumptions.
For positive integer and nonnegative integer , put . Efficiency means that three fixed finite transition-table machines implement key generation, encryption and decryption with at most charged transitions for sufficiently large . Coin counts, honest key lengths and ciphertext lengths have the same polynomial bound. Encryption and decryption also operate on every supplied key and ciphertext within the declared bounds. Input and output serialization is explicit: a string is preceded by its unary length delimiter. Each public key and ciphertext occupies a separate slot of bits; the slot contains the self-delimiting string followed by zeros. These slots are injective for the bounded strings. A fourth fixed serialization machine realizes this encoding in at most transitions; this is an explicit polynomial encoding overhead, independent of the security exponent.
For a Boolean circuit with one output wire, define
Both probabilities use the published key law and encryption law; the circuit receives the whole public key together with the ciphertext. Semantic security requires negligible advantage against every nonuniform polynomial-size circuit family: for every integer , its advantage is eventually at most .
Quantitative security with exponent requires a single eventual threshold, before the message bit and circuit, such that each bit's decryption error and every size-at-most- circuit's advantage are at most . The existential secure-encryption predicate requires efficiency, semantic security and these quantitative guarantees as conclusions. It is a bit-encryption result, the convention used in §3; it does not introduce a separate general-message claim.
import Mathlib
import Definitions.Def_RestrictedDec_PKE
import Definitions.Def_ErrAmpOV_Circuit
import Definitions.Def_ExpandingCodes_PolynomialStretch_OperationalFamily
import Definitions.Def_ExpandingCodes_PolynomialStretch_Supplement_Hypergraphs
set_option autoImplicit false
open scoped BigOperators Classical
namespace ExpandingCodes.PolynomialStretch.Supplement
noncomputable section
abbrev BitCircuit (L : ℕ) := ErrAmpOV.Circuit (Fin L)
def accepts {L : ℕ} (C : BitCircuit L) (s : List Bool) : Prop :=
(C.eval fun i => s.getD i.val false).getD 0 false = true
def oneOutput {L : ℕ} (C : BitCircuit L) : Prop := C.outs.length = 1
/-- Self-delimiting string; the prefix is the unary length, then the data. -/
def pack (s : List Bool) : List Bool := sizeInput s.length ++ s
/-- Injective on strings of length ≤B; exactly 2B+1 bits, including the length delimiter. -/
def slot (B : ℕ) (s : List Bool) : List Bool :=
(pack s ++ List.replicate (2 * B + 1) false).take (2 * B + 1)
def polyBound (A a n : ℕ) : ℕ := A * (n + 1) ^ a
def pkeInput (A a n : ℕ) (pk c : List Bool) : List Bool :=
slot (polyBound A a n) pk ++ slot (polyBound A a n) c
def decryptionBits : Option (List Bool) → List Bool
| none => [false]
| some s => true :: pack s
/-- Syntax has no efficiency/correctness assumptions. This predicate is a CONCLUSION:
three fixed transition tables realize key generation, encryption, and decryption, with charged
output-writing and polynomial bounds fixed before n and the coins. -/
def EfficientPKE (E : RestrictedDec.PKE) (A a : ℕ) : Prop :=
0 < A ∧ ∃ (kg en de serial : NKtLB.Machine) (n₀ : ℕ), ∀ n ≥ n₀,
let B := polyBound A a n
E.keyCoins n ≤ B ∧ E.encCoins n ≤ B ∧
(∀ ω : Fin (E.keyCoins n) → Bool,
let keys := E.keyGen n ω
keys.1.length ≤ B ∧ keys.2.length ≤ B ∧
sampledRun kg n B (E.keyCoins n) ω (pack keys.1 ++ pack keys.2)) ∧
(∀ (pk : List Bool), pk.length ≤ B → ∀ b : Bool,
∀ ω : Fin (E.encCoins n) → Bool,
(E.enc n pk [b] ω).length ≤ B ∧
en.HaltsWith ∅ ⟨sizeInput n ++ pack pk ++ [b], [], [], List.ofFn ω⟩ B
(NKtLB.bitsSym (E.enc n pk [b] ω))) ∧
(∀ (sk c : List Bool), sk.length ≤ B → c.length ≤ B →
de.Computes B (sizeInput n ++ pack sk ++ pack c) (decryptionBits (E.dec n sk c))) ∧
(∀ (pk c : List Bool), pk.length ≤ B → c.length ≤ B →
serial.Computes (8 * (B + 1) ^ 3)
(sizeInput B ++ pack pk ++ pack c) (pkeInput A a n pk c))
/-- Probabilities use the published uniform finite-coin keyLaw and encLaw. -/
def encryptionAcceptance (E : RestrictedDec.PKE) (A a n : ℕ)
(C : BitCircuit (4 * polyBound A a n + 2)) (b : Bool) : ℝ :=
(((E.keyLaw n).bind fun keys =>
(E.encLaw n keys.1 [b]).map fun c => decide (accepts C (pkeInput A a n keys.1 c))) true).toReal
def encryptionAdvantage (E : RestrictedDec.PKE) (A a n : ℕ)
(C : BitCircuit (4 * polyBound A a n + 2)) : ℝ :=
|encryptionAcceptance E A a n C false - encryptionAcceptance E A a n C true|
def decryptionError (E : RestrictedDec.PKE) (n : ℕ) (b : Bool) : ℝ :=
(((E.keyLaw n).bind fun keys =>
(E.encLaw n keys.1 [b]).map fun c => decide (E.dec n keys.2 c ≠ some [b])) true).toReal
/-- Nonuniform semantic security for bits: every polynomial-size circuit family has negligible
advantage. Its input contains BOTH the public key and the ciphertext in injective padded slots. -/
def SemanticallySecure (E : RestrictedDec.PKE) (A a : ℕ) : Prop :=
∀ C : (n : ℕ) → BitCircuit (4 * polyBound A a n + 2),
(∀ n, oneOutput (C n)) →
(∃ K d : ℕ, ∀ n, (C n).size ≤ K * (n + 1) ^ d) →
∀ t : ℕ, ∃ n₀ ≥ 2, ∀ n ≥ n₀,
encryptionAdvantage E A a n (C n) ≤ (n : ℝ) ^ (-(t : ℝ))
/-- One threshold precedes the bit and adversary; failures count as decryption errors. -/
def QuantitativeSecurity (E : RestrictedDec.PKE) (A a : ℕ) (δ' : ℝ) : Prop :=
∃ n₀ ≥ 2, ∀ n ≥ n₀,
(∀ b : Bool, decryptionError E n b ≤ Real.exp (-(n : ℝ) ^ δ')) ∧
(∀ C : BitCircuit (4 * polyBound A a n + 2), oneOutput C →
(C.size : ℝ) ≤ Real.exp ((n : ℝ) ^ δ') →
encryptionAdvantage E A a n C ≤ Real.exp (-(n : ℝ) ^ δ'))
def SecurePKEExists : Prop :=
∃ (E : RestrictedDec.PKE) (A a : ℕ) (δ' : ℝ),
0 < δ' ∧ EfficientPKE E A a ∧ SemanticallySecure E A a ∧ QuantitativeSecurity E A a δ'
end
end ExpandingCodes.PolynomialStretch.Supplement