The discrete-logarithm concept class and its secret-homogeneity

The genuine heart of Liu, Arunachalam, Temme (2021) Theorem 1. On a finite cyclic group G with generator g, the half-interval discrete-log labeling f_s is secret-homogeneous: its uniform learning accuracy is independent of the secret s. This is exactly why a learner for one secret breaks every secret (and hence the discrete-log problem). Pure finite-group theory; no Haar / complexity assumptions.

noncomputable def QuantumAlg.dlogEquiv {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) : Multiplicative (ZMod (Nat.card G)) ≃* G

The discrete-log isomorphism induced by the generator g (Multiplicative (ZMod (Nat.card G)) ≃* G, sending ofAdd 1 ↦ g).

Equations

• QuantumAlg.dlogEquiv g hg = zmodMulEquivOfGenerator hg ⋯

noncomputable def QuantumAlg.dlog {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (x : G) : ZMod (Nat.card G)

Discrete logarithm base g.

Equations

• QuantumAlg.dlog g hg x = Multiplicative.toAdd ((QuantumAlg.dlogEquiv g hg).symm x)

noncomputable def QuantumAlg.gpow {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (t : ZMod (Nat.card G)) : G

g raised to a ZMod (Nat.card G) exponent.

Equations

• QuantumAlg.gpow g hg t = (QuantumAlg.dlogEquiv g hg) (Multiplicative.ofAdd t)

theorem QuantumAlg.dlog_mul {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (x y : G) : dlog g hg (x * y) = dlog g hg x + dlog g hg y

theorem QuantumAlg.dlog_gpow {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (t : ZMod (Nat.card G)) : dlog g hg (gpow g hg t) = t

theorem QuantumAlg.dlog_mul_gpow {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (x : G) (t : ZMod (Nat.card G)) : dlog g hg (x * gpow g hg t) = dlog g hg x + t

theorem QuantumAlg.gpow_zero {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) : gpow g hg 0 = 1

noncomputable def QuantumAlg.dlogConcept {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (s : ZMod (Nat.card G)) (x : G) : Bool

The half-interval discrete-log concept f_s: label x by whether dlog x - s lies in the lower half of ZMod (Nat.card G).

Equations

• QuantumAlg.dlogConcept g hg s x = decide ((QuantumAlg.dlog g hg x - s).val < Nat.card G / 2)

theorem QuantumAlg.dlogConcept_shift {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (s t : ZMod (Nat.card G)) (x : G) : dlogConcept g hg s (x * gpow g hg t) = dlogConcept g hg (s - t) x

Shift-equivariance (workhorse): translating the data by gᵗ shifts the secret by t.

theorem QuantumAlg.dlogConcept_reduction {G : Type u_1} [Group G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (s : ZMod (Nat.card G)) (y : G) : dlogConcept g hg s (y * gpow g hg (s - 1)) = dlogConcept g hg 1 y

Reduction corollary: shifting by g^{s-1} maps the secret-s concept to the fixed secret-1 concept.

noncomputable def QuantumAlg.acc {G : Type u_1} [Group G] [Fintype G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (p : G → Bool) (s : ZMod (Nat.card G)) : ℝ

Uniform (counting) accuracy of a Boolean predictor p against the concept f_s.

Equations

• QuantumAlg.acc g hg p s = ↑{x : G | p x = QuantumAlg.dlogConcept g hg s x}.card / ↑(Nat.card G)

theorem QuantumAlg.acc_shift {G : Type u_1} [Group G] [Fintype G] (g : G) (hg : ∀ (x : G), x ∈ Subgroup.zpowers g) (p : G → Bool) (s : ZMod (Nat.card G)) : acc g hg (fun (y : G) => p (y * gpow g hg (s - 1))) 1 = acc g hg p s

Accuracy-level secret-homogeneity (load-bearing): the accuracy of any predictor on the secret-s concept equals the accuracy of the shifted predictor on the fixed secret-1 concept. So breaking any secret is equivalent to breaking the single fixed concept.