Statistical Means as Cryptographic Seeds: A Domination-Polynomial ElGamal Public-Key Cryptosystem (MBD-EG)

Public-key cryptosystems need two ingredients that are, in practice, difficult to reconcile: a hard algebraic problem to build the trapdoor on, and a convenient, auditable procedure for generating the numbers the trapdoor depends on. A growing line of work in this research programme has explored graph-theoretic invariants , domination polynomials, reliability polynomials, structure functions  as sources for the second ingredient, while keeping the first ingredient anchored to a well-studied hard problem. This paper continues that programme in a new direction: rather than drawing the deterministic seed from a single number, it draws four related seeds from the four classical means of statistics, and shows that the resulting four “shares” combine exactly, by the algebra of modular exponentiation, into the single private exponent an ElGamal cryptosystem needs.

The appeal of statistical means as key material is not decorative. The arithmetic, geometric, harmonic, and quadratic means of a data vector are related by the classical inequality chain HM ≤ GM ≤ AM ≤ QM, and by the exact identity QM² = AM² + Var, which ties the spread between the extreme means directly to the variance of the underlying data. A private vector with more internal spread produces more widely separated mean-shares; this gives a designer a concrete, checkable knob for parameter selection, in a way that a single arbitrary private exponent does not.

The paper's contribution is threefold. First, it verifies, by brute-force enumeration and by an explicit linear recurrence, the domination polynomial of cycle graphs used as the seed-generating function. Second, it defines the MBD-EG construction and proves its correctness formally. Third, and most importantly for the honesty this research programme has committed to throughout, it identifies exactly what the domination polynomial does and does not contribute to security: it contributes deterministic, auditable, reproducible key derivation; it does not, and is not claimed to, contribute any cryptographic hardness of its own, a point demonstrated directly by exhibiting an efficient root-finding attack against the domination polynomial evaluation in isolation.

2. MATHEMATICAL PRELIMINARIES

2.1 DOMINATION POLYNOMIAL OF A GRAPH

For a simple graph G on n vertices, a subset S of the vertex set is a dominating set if every vertex not in S is adjacent to at least one vertex of S. Writing d(G,i) for the number of dominating sets of size i, and γ(G) for the domination number (the smallest size of any dominating set), the domination polynomial of G is defined as D(G,x) = Σᵢ d(G,i) xⁱ, summed over i from γ(G) to n (Alikhani & Peng, 2014). Domination polynomials satisfy a disjoint-union multiplicativity law, D(G₁∪G₂,x) = D(G₁,x)·D(G₂,x), a property exploited in earlier constructions in this research programme (the DPHE and DIP schemes) and revisited briefly in Section 7 below.

2.2 DOMINATION POLYNOMIAL OF CYCLES: VERIFICATION

For the cycle graph Cₙ, the domination polynomial was computed here by brute-force enumeration of all 2ⁿ vertex subsets for n = 3 through 9, confirming the coefficients independently of any textbook formula. The results match the known recurrence for cycles (Alikhani & Peng, 2008),

D(C_n, x) = x [ D(C_{n-1}, x) + D(C_{n-2}, x) + D(C_{n-3}, x)], n ≥ 7,

with base polynomials D(C₃,x)=x³+3x²+3x, D(C₄,x)=x⁴+4x³+6x², D(C₅,x)=x⁵+5x⁴+10x³+5x², and D(C₆,x)=x⁶+6x⁵+15x⁴+14x³+3x², all separately confirmed against brute force. Applying the recurrence through n = 12 gives the polynomial used throughout this paper:

D(C₁₂, x) = x¹²+12x¹¹+66x¹⁰+208x⁹+399x⁸+456x⁷+282x⁶+72x⁵+3x⁴.

This polynomial is entirely public: n = 12 is a published system parameter, and D(C₁₂,x) can be recomputed by anyone from the recurrence above. No secrecy is asked of the polynomial itself; its role, made precise in Section 4, is purely as a fixed, public function applied to a private input.

2.3 CLASSICAL STATISTICAL MEANS AND THE POWER-MEAN INEQUALITY

For a vector a = (a₁,…,aₘ) of positive reals, the four classical means used in this paper are the arithmetic mean AM(a) = (1/m)Σaᵢ, the geometric mean GM(a) = (Πaᵢ)^(1/m), the harmonic mean HM(a) = m / Σ(1/aᵢ), and the quadratic mean (root-mean-square) QM(a) = √((1/m)Σaᵢ²). These are the four best-known members of the wider family of power means (Bullen, 2003), and they satisfy the classical ordering

HM(a) ≤ GM(a) ≤ AM(a) ≤ QM(a),

with equality throughout only when all aᵢ are equal (Hardy, Littlewood, & Pólya, 1934). This ordering is what guarantees that the four rounded seeds t_HM, t_GM, t_AM, t_QM defined in Section 4 are, except in the degenerate equal-entries case, distinct integers in increasing order.

2.4 A VARIANCE IDENTITY

Proposition 1 (QMAM–variance identity). For any positive real vector a of length m, QM(a)² = AM(a)² + Var(a), where Var(a) = (1/m)Σ(aᵢ − AM(a))² is the population variance of a.

Proof. Expanding the population variance, Var(a) = (1/m)Σaᵢ² − 2·AM(a)·(1/m)Σaᵢ + AM(a)² = (1/m)Σaᵢ² − 2AM(a)² + AM(a)² = (1/m)Σaᵢ² − AM(a)² = QM(a)² − AM(a)², since (1/m)Σaᵢ² is exactly QM(a)² by definition. Rearranging gives the stated identity. ■

This identity is used in Section 6 to give a checkable design rule: the separation between the AM-share and the QM-share of the private key grows with the variance of the underlying private vector, so a designer who wants well-separated mean-shares can simply choose a private vector with sufficient spread and confirm it numerically before use.

3. RELATED WORK

The ElGamal cryptosystem (ElGamal, 1985), building on the Diffie–Hellman key exchange (Diffie & Hellman, 1976), remains the standard reference construction whose hardness rests on the discrete logarithm problem in a finite cyclic group; its security assumptions and variants are catalogued in Menezes, van Oorschot, and Vanstone (1996). Domination polynomials were introduced by Alikhani and Peng (2009, 2014) and specialised to cycles in Alikhani and Peng (2008); this paper is, to the authors' knowledge, the first to use domination-polynomial evaluation purely as a deterministic key-derivation function feeding a discrete-logarithm-hard trapdoor, rather than as the trapdoor itself  a distinction developed carefully in Section 6. Classical mean inequalities and the wider power-mean family are treated exhaustively in Hardy, Littlewood, and Pólya (1934) and in Bullen (2003); their use here as a multi-channel key-derivation source, rather than as a purely analytic tool, is the paper's second point of departure from existing literature.

4. PROPOSED CONSTRUCTION: MBD-EG

4.1 DESIGN RATIONALE

The construction separates two roles that are often conflated in graph-theoretic cryptographic proposals: the role of generating key material deterministically and reproducibly from something memorable, and the role of providing the actual computational hardness the scheme relies on for confidentiality. Section 6.3 shows explicitly why these roles must be kept separate for this particular graph invariant. The design below assigns the domination polynomial to the first role only, and assigns all cryptographic hardness to a standard ElGamal layer over a safe-prime group.

4.2 KEY GENERATION

Step 1.  Fix public system parameters: a safe prime p = 2q+1 with q prime, a generator g of the order-q subgroup of ℤₚ*, and a cycle length n (so that D(Cₙ,x) is fixed and public, as in Section 2.2).

Step 2.  The key owner privately chooses a positive-integer vector a = (a₁,…,aₘ), m ≥ 2 — for reproducibility, this may be derived deterministically from a memorable string via the A = 1, …, Z = 26 encoding, exactly as in Section 5.

Step 3.  Compute the four classical means of a AM, GM, HM, QM  and round each to the nearest positive integer, giving four seeds t_HM ≤ t_GM ≤ t_AM ≤ t_QM (Section 2.3).

Step 4.  Compute the four mean-share exponents k_i = D(Cₙ, t_i) mod q for i ∈ {HM, GM, AM, QM}.

Step 5.  Publish the four mean-share public keys h_i = g^{ki} mod p, together with (p, q, g, n).

Step 6.  The combined private exponent is K = (k_HM + k_GM + k_AM + k_QM) mod q, and the combined public key is H = h_HM·h_GM·h_AM·h_QM mod p. By the elementary law of exponents, H = g^K mod p, so publishing the four shares is equivalent to publishing their product.

4.3 ENCRYPTION

To encrypt a plaintext block M (0 ≤ M < p) under the public key H, the sender chooses a random ephemeral integer r with 1 ≤ r < q and computes C₁ = g^r mod p and C₂ = M·H^r mod p. The ciphertext is the pair (C₁, C₂).

4.4 DECRYPTION

The key owner, holding K (or, equivalently, the private vector a from which K can be recomputed via Steps 2–6), recovers the plaintext as M = C₂ · (C₁^K)⁻¹ mod p, where the inverse is the modular multiplicative inverse mod p.

4.5 CORRECTNESS

Theorem 1 (Correctness). For any plaintext M with 0 ≤ M < p and any ephemeral r, the decryption procedure of Section 4.4 recovers M exactly from the ciphertext of Section 4.3.

Proof. By Step 6, H = g^K mod p. Then C₁^K = (g^r)^K = g^{rK} = (g^K)^r = H^r (mod p). Hence C₂·(C₁^K)⁻¹ = M·H^r·(H^r)⁻¹ = M (mod p).

5. WORKED NUMERICAL EXAMPLE

All values below were computed exactly (not estimated) using the verified polynomial of Section 2.2. The private vector is derived from the word MATHEMATICS via A = 1, …, Z = 26 encoding:

a = (13, 1, 20, 8, 5, 13, 1, 20, 9, 3, 19),   m = 11.

The four classical means, computed exactly, are:

AM = 10.181818,  GM = 6.778010,  HM = 3.576163,  QM = 12.358288,

confirming the ordering HM < GM < AM < QM predicted by Section 2.3. As a check on Proposition 1, QM² = 152.727273 and AM² + Var(a) = 152.727273 agrees and rounding gives the four integer seeds

t_HM = 4,  t_GM = 7,  t_AM = 10,  t_QM = 12.

The system parameters used for this demonstration are the safe prime q = 3299, p = 2q+1 = 6599, and generator g = 4 of the order-q subgroup of ℤ₆₅₉₉* (verified by direct computation that g^q ≡ 1 (mod p) and g ≠ 1). Evaluating the public polynomial D(C₁₂,x) of Section 2.2 at each seed, reduced mod q, gives the mean-share exponents:

k_HM = 2479,  k_GM = 3173,  k_AM = 2064,  k_QM = 3194,

and the corresponding public shares h_i = g^{k_i} mod p are:

h_HM = 1124,  h_GM = 4858,  h_AM = 1374,  h_QM = 6014.

The combined private exponent is K = (2479+3173+2064+3194) mod 3299 = 1013, and the combined public key is H = g^K mod p = 1661. As required by Step 6 of Section 4.2, the direct product of the four published shares, h_HM·h_GM·h_AM·h_QM mod p, was computed independently and also equals 1661, confirming the mean-share composition law numerically.

For the plaintext, the two-letter word HI was encoded as the integer M = 809 (via the two-digit packing 08-09). With ephemeral randomness r = 777, encryption gives ciphertext (C₁, C₂) = (5868, 4727). Decryption using K = 1013 recovers M = 809 exactly, which decodes back to HI, By  Theorem 1 .

Table 1. Complete worked MBD-EG key generation, encryption, and decryption trace.

6. SECURITY ANALYSIS

6.1 REDUCTION TO THE DISCRETE LOGARITHM PROBLEM

An adversary who observes the public key components (p, q, g, h_HM, h_GM, h_AM, h_QM) and a ciphertext (C₁, C₂) must recover M without knowing K. Since H = gK mod p is published only in exponentiated form, recovering K from H is exactly the discrete logarithm problem in the order-q subgroup of ℤₚ*, and recovering M from (C₁, C₂) without K is exactly the computational Diffie–Hellman problem in the same group, the identical hardness assumptions that protect standard ElGamal (ElGamal, 1985; Menezes, van Oorschot, & Vanstone, 1996). The domination-polynomial step of Section 4.2 plays no role in this reduction: it only decides which exponent K gets used, not how hard K is to recover once fixed.

6.2 THE COUPLING PROPERTY OF MEAN-SHARES

Proposition 2 (Coupling). Let a be a positive-real vector of length m ≥ 2, and let a' be obtained from a by changing a single coordinate aⱼ to a value aⱼ' ≠ aⱼ, holding all other coordinates fixed. Then AM(a) ≠ AM(a'), GM(a) ≠ GM(a'), HM(a) ≠ HM(a'), and QM(a) ≠ QM(a').

Proof. Each of the four means, viewed as a function of the single coordinate aⱼ with the remaining m−1 coordinates held fixed, is strictly monotonic: AM is affine increasing in aⱼ; GM is a strictly increasing function of aⱼ because the m-th root and the product with fixed positive factors are both strictly increasing; HM = m/Σ(1/aᵢ) is strictly increasing in aⱼ because 1/aⱼ is strictly decreasing in aⱼ and the reciprocal of a strictly decreasing positive sum is strictly increasing; and QM is strictly increasing in aⱼ because aⱼ² is strictly increasing for aⱼ > 0. A strictly monotonic function takes different values at different inputs, so aⱼ ≠ aⱼ' forces each of the four mean values to change. ■

Practically, Proposition 2 means no single mean-share k_HM, k_GM, k_AM, or k_QM can be regenerated correctly by an attacker who has guessed or partially recovered only part of the private vector a; every coordinate of a leaves a trace in every one of the four shares simultaneously. This is a structural property of the key-derivation step, not an additional hardness assumption, and it is verified numerically

7. COMPARISON WITH RELATED CONSTRUCTIONS

Table 2. Positioning MBD-EG against ElGamal and earlier domination-polynomial constructions in this research programme.