cheating-dealer-detection.ipynb

Kernel: SageMath 10.0

Break: Cheating Dealer Detection in Shamir Sharing

Module 12 | Breaking Weak Parameters

Detect when a dealer distributes inconsistent shares using verification polynomials.

Why This Matters

In Shamir secret sharing (Notebook 12a), a dealer splits a secret into shares by evaluating a random polynomial. Every subset of $t$ shares reconstructs the same secret because they all lie on the same degree-$(t-1)$ polynomial.

But what if the dealer is dishonest? A cheating dealer could give one party a share from a different polynomial. Now different subsets of $t$ parties reconstruct different "secrets" --- and nobody knows which (if any) is correct.

This is a real threat in distributed key generation, threshold signatures, and any protocol that begins with a sharing phase. The fix is Verifiable Secret Sharing (VSS): the dealer publishes commitments that let every party check their share's consistency.

The Scenario

A dealer distributes $(3, 5)$ Shamir shares over $\mathbb{F}_p$. Five parties each receive a share $(i, f(i))$. But the dealer gives Alice (Party 1) a corrupted share that does not lie on the polynomial used for the other four parties.

Goal: detect the inconsistency without reconstructing the secret.

# === Setup: Shamir sharing helpers (from Notebook 12a) ===

p = 1009
F = GF(p)
R.<x> = PolynomialRing(F)

def shamir_share(secret, t, n, field):
    """Split secret into n Shamir shares with threshold t."""
    p_val = field.order()
    coeffs = [field(secret)] + [field(randint(1, p_val - 1)) for _ in range(t - 1)]
    f = PolynomialRing(field, 'z')(coeffs)
    shares = [(field(i), f(field(i))) for i in range(1, n + 1)]
    return shares, f

def shamir_reconstruct(shares, field):
    """Reconstruct secret from t or more Shamir shares."""
    xs = [s[0] for s in shares]
    ys = [s[1] for s in shares]
    secret = field(0)
    for i in range(len(xs)):
        num = field(1)
        den = field(1)
        for j in range(len(xs)):
            if i != j:
                num *= -xs[j]
                den *= (xs[i] - xs[j])
        secret += ys[i] * num / den
    return secret

# Parameters
t, n = 3, 5
secret = F(42)
print(f"Shamir ({t},{n}) sharing over F_{p}")
print(f"Secret: s = {secret}")

Step 1: Honest Dealing

First, let's see how an honest dealer works. All shares lie on the same degree-2 polynomial, so every subset of $t = 3$ shares reconstructs the same secret.

# === Step 1: Honest dealer distributes consistent shares ===

honest_shares, honest_poly = shamir_share(secret, t, n, F)

print(f"Honest polynomial: f(x) = {honest_poly}")
print(f"\nShares distributed:")
for i, (xi, yi) in enumerate(honest_shares):
    print(f"  Party {i+1}: ({xi}, {yi})")

print(f"\nReconstruction from every subset of {t} shares:")
all_same = True
for combo in Combinations(range(n), t):
    subset = [honest_shares[i] for i in combo]
    parties = [i + 1 for i in combo]
    recovered = shamir_reconstruct(subset, F)
    match = recovered == secret
    if not match:
        all_same = False
    print(f"  Parties {parties}: s = {recovered} {'correct' if match else 'WRONG'}")

print(f"\nAll {len(list(Combinations(range(n), t)))} subsets agree on s = {secret}.")

Step 2: Cheating Dealer

Now the dealer corrupts Alice's share. Party 1 receives a value that does not lie on the honest polynomial. Different subsets of 3 parties now reconstruct different values.

# === Step 2: Cheating dealer gives Alice a bad share ===
cheating_shares = list(honest_shares)
original_alice = cheating_shares[0][1]
corrupted_alice = original_alice + F(100)  # shift by 100
cheating_shares[0] = (honest_shares[0][0], corrupted_alice)

print(f"Dealer corrupts Alice's share:")
print(f"  Honest:    (1, {original_alice})")
print(f"  Corrupted: (1, {corrupted_alice})")
print()

# Different subsets reconstruct different secrets
print(f"Reconstruction from subsets of {t} shares:")
results = {}
for combo in combinations(range(n), t):
    subset = [cheating_shares[i] for i in combo]
    parties = [i + 1 for i in combo]
    recovered = shamir_reconstruct(subset, F)
    has_alice = 1 in parties
    marker = "(includes Alice)" if has_alice else "(no Alice)"
    print(f"  Parties {parties}: s = {recovered}  {marker}")
    results[tuple(parties)] = recovered

unique_values = set(results.values())
print(f"\nDistinct 'secrets' reconstructed: {len(unique_values)}")
print(f"Without Alice, all subsets agree on s = {secret}.")
print(f"With Alice, the corrupted share pulls the interpolation to a wrong value.")

Step 3: Detection with Feldman's VSS

Feldman's Verifiable Secret Sharing (1987) adds a verification layer. The dealer publishes commitments to the polynomial coefficients using a generator $g$ of a multiplicative group of order $q$ (where $q$ divides $p - 1$).

If the polynomial is $f(x) = a_0 + a_1 x + a_2 x^2$, the dealer publishes:

$$C_k = g^{a_k} \bmod p \quad \text{for } k = 0, 1, \ldots, t-1$$

Each party $i$ checks their share $y_i = f(i)$ against the commitments:

$$g^{y_i} \stackrel{?}{=} \prod_{k=0}^{t-1} C_k^{i^k} \pmod{p}$$

This works because: $$\prod_k C_k^{i^k} = \prod_k g^{a_k \cdot i^k} = g^{\sum_k a_k i^k} = g^{f(i)}$$

# === Step 3: Feldman's VSS ===

# We need a prime p where p-1 has a large prime factor q
# Use p = 1009: p - 1 = 1008 = 2^4 * 3^2 * 7
# Use subgroup of order q = 7 for a small demonstration
# (In practice q would be a large prime, here we use a small one for clarity)

q = 7  # subgroup order
# Find a generator of the subgroup of order q in GF(p)*
g_candidate = F.multiplicative_generator()
g = g_candidate^((p - 1) // q)
assert g != F(1) and g^q == F(1), "g must generate a subgroup of order q"

print(f"Feldman VSS parameters:")
print(f"  Prime p = {p}, subgroup order q = {q}")
print(f"  Generator g = {g} (order {g.multiplicative_order()})")
print()

# For Feldman VSS, the polynomial coefficients and shares must be in Z_q
Fq = GF(q)
secret_q = Fq(5)  # secret in Z_q
t_vss, n_vss = 3, 5

# Honest polynomial over Z_q
coeffs = [secret_q] + [Fq(randint(1, q - 1)) for _ in range(t_vss - 1)]
R_q.<z> = PolynomialRing(Fq)
f_vss = R_q(coeffs)

# Shares
vss_shares = [(Fq(i), f_vss(Fq(i))) for i in range(1, n_vss + 1)]

print(f"Secret: s = {secret_q}")
print(f"Polynomial: f(x) = {f_vss}")
print(f"Coefficients: {coeffs}")
print()

# Dealer publishes commitments C_k = g^{a_k} mod p
commitments = [g^(ZZ(c)) for c in coeffs]
print(f"Published commitments (g^a_k mod p):")
for k, ck in enumerate(commitments):
    print(f"  C_{k} = g^{coeffs[k]} = {ck}")

# === Step 3b: Each party verifies their share ===

def feldman_verify(party_id, share_value, commitments, g, p, t):
    """Verify a Shamir share against Feldman commitments.
    
    Check: g^{share_value} == prod_{k=0}^{t-1} C_k^{i^k}  (mod p)
    """
    F_local = GF(p)
    lhs = F_local(g)^(ZZ(share_value))
    rhs = F_local(1)
    for k in range(t):
        rhs *= F_local(commitments[k])^(ZZ(party_id)^k)
    return lhs == rhs

print(f"=== Honest Share Verification ===")
for i, (xi, yi) in enumerate(vss_shares):
    valid = feldman_verify(xi, yi, commitments, g, p, t_vss)
    print(f"  Party {i+1} (share = {yi}): g^{yi} == prod C_k^{{{xi}^k}}? {valid}")

print(f"\nAll honest shares pass verification.")

Step 4: The Corrupted Share Fails Verification

Now the dealer gives Alice a corrupted share. The commitment check catches it immediately.

# === Step 4: Corrupted share fails Feldman verification ===

# Corrupt Alice's share (Party 1)
corrupted_vss_shares = list(vss_shares)
alice_honest = vss_shares[0][1]
alice_corrupted = alice_honest + Fq(2)  # shift by 2 in Z_q
corrupted_vss_shares[0] = (vss_shares[0][0], alice_corrupted)

print(f"Dealer corrupts Alice's share:")
print(f"  Honest:    f(1) = {alice_honest}")
print(f"  Corrupted: f(1) = {alice_corrupted}")
print()

print(f"=== Verification After Corruption ===")
for i, (xi, yi) in enumerate(corrupted_vss_shares):
    valid = feldman_verify(xi, yi, commitments, g, p, t_vss)
    marker = "CORRUPTED" if i == 0 and not valid else ""
    print(f"  Party {i+1} (share = {yi}): valid? {valid}  {marker}")

print(f"\nAlice detects the cheating! Her share does not match the commitments.")
print(f"She can broadcast a complaint and the protocol aborts or the dealer is replaced.")

The Fix: Verifiable Secret Sharing (VSS)

Feldman's VSS ensures share consistency by binding the dealer to a specific polynomial via public commitments.

Property	Plain Shamir	Feldman VSS
Share distribution	Dealer sends $(i, f(i))$	Same, plus publishes $g^{a_k}$
Verification	None	Each party checks $g^{f(i)} = \prod C_k^{i^k}$
Cheating detection	Only after reconstruction	Immediately upon receiving the share
Assumption	Honest dealer	Discrete log hardness

Limitation: Feldman's VSS reveals $g^s$ (the commitment to the secret). If hiding the secret's commitment is also required, Pedersen's VSS uses an additional generator $h$ with unknown discrete log relationship to $g$, achieving information-theoretic hiding.

# === Exercise: Corrupt different shares and observe detection ===

print("=== Corrupting each party's share in turn ===")
print()
for target_party in range(n_vss):
    test_shares = list(vss_shares)
    xi, yi = test_shares[target_party]
    # Corrupt by adding a random nonzero offset
    offset = Fq(randint(1, q - 1))
    test_shares[target_party] = (xi, yi + offset)
    
    print(f"Corrupt Party {target_party + 1} (shift by {offset}):")
    for i, (xj, yj) in enumerate(test_shares):
        valid = feldman_verify(xj, yj, commitments, g, p, t_vss)
        flag = " <-- DETECTED" if not valid else ""
        print(f"  Party {i+1}: valid? {valid}{flag}")
    print()

print("Every corrupted share is detected, regardless of which party is targeted.")
print("The verification is per-share: each party independently checks their own.")

# === Exercise: Scaling to larger parameters ===

# Use a larger subgroup for more realistic parameters
# p2 = 2 * q2 + 1 where q2 is prime (safe prime structure)
q2 = 503  # prime
p2 = 2 * q2 + 1  # = 1007, also prime (a safe prime)
assert is_prime(p2) and is_prime(q2)

F2 = GF(p2)
Fq2 = GF(q2)

# Generator of order q2 in GF(p2)*
g2 = F2.multiplicative_generator()^((p2 - 1) // q2)
assert g2 != F2(1) and g2^q2 == F2(1)

# (3, 7) sharing with larger parameters
secret2 = Fq2(123)
t2, n2 = 3, 7
coeffs2 = [secret2] + [Fq2(randint(1, q2 - 1)) for _ in range(t2 - 1)]
R_q2.<w> = PolynomialRing(Fq2)
f2 = R_q2(coeffs2)

vss_shares2 = [(Fq2(i), f2(Fq2(i))) for i in range(1, n2 + 1)]
commitments2 = [g2^(ZZ(c)) for c in coeffs2]

print(f"Larger Feldman VSS: ({t2},{n2}) over Z_{q2}, verification in GF({p2})")
print(f"Secret: {secret2}")
print()

# Verify all honest shares
all_valid = True
for i, (xi, yi) in enumerate(vss_shares2):
    valid = feldman_verify(xi, yi, commitments2, g2, p2, t2)
    if not valid:
        all_valid = False
print(f"All {n2} honest shares valid? {all_valid}")

# Corrupt one share
bad_shares2 = list(vss_shares2)
bad_shares2[3] = (vss_shares2[3][0], vss_shares2[3][1] + Fq2(50))
valid_corrupt = feldman_verify(bad_shares2[3][0], bad_shares2[3][1], commitments2, g2, p2, t2)
print(f"Corrupted Party 4 share valid? {valid_corrupt}")
print(f"\nDetection works at any scale. In practice, q would be 256+ bits.")

Summary

Aspect	Detail
Attack	Dishonest dealer gives one party a share from a different polynomial
Impact	Different subsets reconstruct different "secrets" --- the output is meaningless
Detection	Feldman's VSS: dealer publishes $g^{a_k}$; each party checks $g^{f(i)} = \prod C_k^{i^k}$
Root cause	Plain Shamir has no mechanism for parties to verify share consistency
Fix	Verifiable Secret Sharing (VSS) --- every sharing comes with public verification commitments
Real world	Distributed key generation (Ethereum 2.0, threshold ECDSA) requires VSS

Key takeaway: secret sharing without verification is dangerous. In any protocol where the dealer might be malicious, VSS is essential. The commitments add minimal overhead (one group exponentiation per party) but provide complete protection against inconsistent shares.

---

Back to Module 12: Multi-Party Computation