Secure Multi-Party Computation and Game-Theoretic Incentives

cryptography-and-gt
secure-computation
mechanism-design
Demonstrate finite-field secret sharing and compare ideal auction outcomes in R; the auction calculation is centralized and does not implement a secure MPC protocol.
Author

Raban Heller

Published

May 8, 2026

Modified

May 8, 2026

Keywords

secure multi-party computation, secret sharing, sealed-bid auction, incentive compatibility, Shamir

Introduction & motivation

A fundamental tension pervades strategic interactions: players often benefit from jointly computing some function of their private information, but each player has strong incentives to conceal that information from others. In a sealed-bid auction, bidders want the highest bidder to win and pay a fair price, but no losing bidder wants their bid revealed – it would expose their valuation and weaken their position in future negotiations. In salary negotiations within a team, employees might want to know whether they are paid fairly relative to colleagues without disclosing their actual salaries. In supply chain coordination, firms may wish to optimise joint logistics without revealing proprietary cost structures. The question, then, is whether cryptographic protocols can resolve this tension by enabling computation over private inputs without revealing those inputs themselves.

Secure multi-party computation (MPC) provides exactly this capability. Originating from Yao’s garbled circuits (1986) for the two-party case and extended by Goldreich, Micali, and Wigderson (1987) to the multi-party setting, MPC protocols allow \(n\) parties to jointly compute any function \(f(x_1, \ldots, x_n)\) of their private inputs \(x_i\) such that each party learns only the output \(f(x_1, \ldots, x_n)\) and nothing else about other parties’ inputs. The theoretical foundation guarantees that any function computable by a polynomial-time algorithm can be securely computed in this multi-party setting, provided a sufficient fraction of parties behave honestly.

The connection between MPC and game theory runs deep. Game-theoretic mechanism design – pioneered by Hurwicz (1960) and developed by Myerson, Maskin, and others – asks how to design rules (mechanisms) that incentivise players to behave in desirable ways. The revelation principle states that any mechanism can be replicated by a direct mechanism in which players truthfully report their types to a trusted mediator. But what if no trusted mediator exists? This is precisely where MPC enters: it can simulate the trusted mediator computationally, replacing trust in a person or institution with trust in mathematical guarantees. As Dodis, Halevi, and Rabin (2000) formalised, MPC can implement any mediated equilibrium as a communication equilibrium without a mediator, provided the protocol satisfies appropriate security properties.

At the heart of most practical MPC protocols lies secret sharing, the cryptographic primitive that allows a secret to be split among multiple parties such that only authorised subsets can reconstruct it. Shamir’s secret sharing scheme (1979), based on polynomial interpolation over finite fields, is the most widely used. A secret \(s\) is encoded as the constant term of a random polynomial of degree \(t\), and each party receives an evaluation of this polynomial at a distinct point. Any \(t + 1\) shares suffice to reconstruct the polynomial (and hence the secret) via Lagrange interpolation, while \(t\) or fewer shares reveal absolutely nothing about \(s\) – not even a single bit. This threshold property is information-theoretically perfect: no amount of computational power can extract information from an insufficient number of shares.

The game-theoretic implications of MPC are profound. In a standard sealed-bid auction without MPC, the auctioneer sees all bids and could exploit this information – front-running, bid manipulation, or information leakage to favoured bidders. With MPC, the auction can be conducted such that no single party (including the auctioneer) ever sees individual bids; only the identity of the winner and the price are revealed. This transforms the game: bidders who would otherwise shade their bids to protect against information leakage can now bid more truthfully. In the language of mechanism design, MPC can make truthful reporting a dominant strategy in settings where information concerns would otherwise prevent it.

This tutorial demonstrates Shamir’s finite-field arithmetic in R, then compares ideal auction outcomes using a centralized simulation. It does not implement an MPC auction protocol. We simulate a population of bidders with private valuations and compare auction outcomes (revenue, efficiency, bidder surplus) across three regimes: a standard first-price sealed-bid auction where bids are visible to the auctioneer, a second-price (Vickrey) auction, and a duplicated ideal target for a potential MPC implementation. The duplicated Vickrey outcome is an ideal-function benchmark; it provides no evidence about privacy, secure computation or real-world incentives.

Mathematical formulation

Shamir’s Secret Sharing. Let \(p\) be a large prime and \(\mathbb{F}_p = \{0, 1, \ldots, p-1\}\) be the finite field of integers modulo \(p\). To share a secret \(s \in \mathbb{F}_p\) among \(n\) parties with threshold \(t\) (meaning any \(t+1\) shares can reconstruct \(s\), but \(t\) or fewer reveal nothing):

  1. Choose random coefficients \(a_1, \ldots, a_t \in \mathbb{F}_p\) and define the polynomial: \[ f(x) = s + a_1 x + a_2 x^2 + \cdots + a_t x^t \pmod{p} \]

  2. Give party \(i\) the share \((i, f(i) \bmod p)\) for \(i = 1, \ldots, n\).

  3. To reconstruct, use Lagrange interpolation with any \(t+1\) shares \((x_k, y_k)\): \[ s = f(0) = \sum_{k=1}^{t+1} y_k \prod_{\substack{j=1 \\ j \neq k}}^{t+1} \frac{-x_j}{x_k - x_j} \pmod{p} \]

MPC Addition. A key property of Shamir’s scheme is that it is additively homomorphic: if party \(i\) holds shares \(f(i)\) and \(g(i)\) of secrets \(s_1\) and \(s_2\) respectively, then \(f(i) + g(i) \pmod{p}\) is a valid share of \(s_1 + s_2\). This allows secure computation of sums without any communication.

Sealed-Bid Auction Protocol. Consider \(n\) bidders with private valuations \(v_i\). Each bidder submits a bid \(b_i\) by secret-sharing it among all \(n\) parties. The protocol securely computes: \[ \text{winner} = \arg\max_i \; b_i, \qquad \text{price} = \max_{j \neq \text{winner}} b_j \]

Incentive Compatibility. In a Vickrey (second-price) auction, truthful bidding \(b_i = v_i\) is a weakly dominant strategy. The expected payoff for bidder \(i\) is:

\[ \mathbb{E}[\pi_i] = \Pr(v_i \geq v_{(2)}) \cdot \mathbb{E}[v_i - v_{(2)} \mid v_i \geq v_{(2)}] \]

where \(v_{(2)}\) is the second-highest valuation. MPC preserves this incentive compatibility by ensuring no information about losing bids is revealed, eliminating concerns about strategic information leakage.

R implementation

We demonstrate Shamir’s finite-field arithmetic and centralized auction outcomes. For tractability, we work with a moderate prime and simulate the strategic comparison between auction formats.

set.seed(314)

# ---- Modular arithmetic helpers ----
field_check <- function(prime) {
  if (!is.numeric(prime) || length(prime)!=1L || !is.finite(prime) ||
      prime!=floor(prime) || prime<2 || prime>46337 ||
      (prime>3 && any(prime %% seq.int(2,floor(sqrt(prime))) == 0)))
    stop("Use a prime integer from 2 through 46337.")
}
mod_inv <- function(a, p) {
  # Extended Euclidean algorithm for modular inverse
  if (a %% p == 0) stop("Zero has no multiplicative inverse")
  a <- a %% p
  g <- p; x <- 0; y <- 1
  a_curr <- a
  while (a_curr > 1) {
    q <- a_curr %/% g
    temp <- g
    g <- a_curr %% g
    a_curr <- temp
    temp <- x
    x <- y - q * x
    y <- temp
  }
  y %% p
}

# ---- Shamir's Secret Sharing ----
shamir_share <- function(secret, n, t, p) {
  # t is the polynomial degree here; the reconstruction threshold is t + 1.
  field_check(p)
  args <- c(secret,n,t)
  if (length(args)!=3L || any(!is.finite(args)) || any(args!=floor(args)) ||
      secret<0 || secret>=p || t<0 || n<=t || n>=p)
    stop("Require 0 <= secret < p and 0 <= t < n < p")
  coeffs <- c(secret, sample.int(p, t, replace = TRUE) - 1)
  shares <- numeric(n)
  for (i in 1:n) {
    val <- 0
    for (k in seq_along(coeffs)) {
      # Use modular exponentiation to avoid overflow
      power_val <- 1
      for (m in seq_len(k - 1)) power_val <- (power_val * i) %% p
      val <- (val + coeffs[k] * power_val) %% p
    }
    shares[i] <- val
  }
  list(shares = shares, coeffs = coeffs)
}

shamir_reconstruct <- function(indices, share_values, p) {
  field_check(p)
  vals <- c(indices,share_values)
  if (!length(indices) || length(indices)!=length(share_values) ||
      any(!is.finite(vals)) || any(vals!=floor(vals)) || anyDuplicated(indices) ||
      any(indices<1 | indices>=p) || any(share_values<0 | share_values>=p))
    stop("Require distinct nonzero coordinates and valid field values")
  # Lagrange interpolation at x=0
  n <- length(indices)
  secret <- 0
  for (k in 1:n) {
    num <- 1; den <- 1
    for (j in 1:n) {
      if (j != k) {
        num <- (num * (p - indices[j])) %% p
        den <- (den * ((indices[k] - indices[j]) %% p + p)) %% p
      }
    }
    lagrange_coeff <- (num * mod_inv(den, p)) %% p
    secret <- (secret + share_values[k] * lagrange_coeff) %% p
  }
  secret
}

# ---- Demonstrate secret sharing ----
p <- 997  # prime modulus
secret <- 42
n_parties <- 5
threshold <- 2  # need t+1 = 3 shares to reconstruct

result <- shamir_share(secret, n_parties, threshold, p)
cat("Secret:", secret, "\n")
Secret: 42 
cat("Shares:", paste(result$shares, collapse = ", "), "\n")
Shares: 758, 246, 500, 523, 315 
# Reconstruct with exactly t+1 = 3 shares
recon_indices <- c(1, 3, 5)
recon_values <- result$shares[recon_indices]
recovered <- shamir_reconstruct(recon_indices, recon_values, p)
cat("Reconstructed from shares {1,3,5}:", recovered, "\n")
Reconstructed from shares {1,3,5}: 42 
# Verify additive homomorphism
secret_a <- 100; secret_b <- 200
shares_a <- shamir_share(secret_a, n_parties, threshold, p)$shares
shares_b <- shamir_share(secret_b, n_parties, threshold, p)$shares
shares_sum <- (shares_a + shares_b) %% p
recovered_sum <- shamir_reconstruct(c(1,2,3), shares_sum[c(1,2,3)], p)
cat("Additive homomorphism: ", secret_a, "+", secret_b, "=", recovered_sum, "\n")
Additive homomorphism:  100 + 200 = 300 
# ---- Centralized Sealed-Bid Auction Simulation ----
n_bidders <- 6
n_sims <- 1000

# Draw valuations from U[10, 100]
set.seed(271)
sim_results <- data.frame(
  sim = integer(0), format = character(0),
  revenue = numeric(0), efficiency = numeric(0),
  winner_surplus = numeric(0)
)

for (s in 1:n_sims) {
  valuations <- runif(n_bidders, 10, 100)
  true_winner <- which.max(valuations)
  second_highest <- sort(valuations, decreasing = TRUE)[2]

  # 1. Risk-neutral equilibrium for independent U[10,100] values
  bids_fp <- 10 + (valuations - 10) * (n_bidders - 1) / n_bidders
  winner_fp <- which.max(bids_fp)
  revenue_fp <- max(bids_fp)
  efficiency_fp <- as.integer(winner_fp == true_winner)
  surplus_fp <- valuations[winner_fp] - revenue_fp

  # 2. Vickrey auction (truthful, but auctioneer sees bids)
  bids_vickrey <- valuations  # truthful

  winner_v <- which.max(bids_vickrey)
  revenue_v <- sort(bids_vickrey, decreasing = TRUE)[2]
  efficiency_v <- 1  # always efficient
  surplus_v <- valuations[winner_v] - revenue_v

  # 3. Ideal-function benchmark only: all bids are visible in this R process.
  # No secret-sharing comparison circuit or private auction is implemented.
  bids_mpc <- valuations  # truthful benchmark; no MPC protocol is executed
  winner_mpc <- which.max(bids_mpc)
  revenue_mpc <- sort(bids_mpc, decreasing = TRUE)[2]
  efficiency_mpc <- 1
  surplus_mpc <- valuations[winner_mpc] - revenue_mpc

  sim_results <- rbind(sim_results, data.frame(
    sim = rep(s, 3),
    format = c("First-Price", "Vickrey (Open)", "Vickrey (ideal MPC target)"),
    revenue = c(revenue_fp, revenue_v, revenue_mpc),
    efficiency = c(efficiency_fp, efficiency_v, efficiency_mpc),
    winner_surplus = c(surplus_fp, surplus_v, surplus_mpc)
  ))
}

summary_stats <- sim_results |>
  group_by(format) |>
  summarise(
    avg_revenue = mean(revenue),
    avg_efficiency = mean(efficiency),
    avg_surplus = mean(winner_surplus),
    .groups = "drop"
  )

cat("\n--- Auction Format Comparison (", n_sims, "simulations) ---\n")

--- Auction Format Comparison ( 1000 simulations) ---
for (i in 1:nrow(summary_stats)) {
  cat(sprintf("\n%s:\n  Revenue: %.2f  |  Efficiency: %.3f  |  Winner surplus: %.2f\n",
              summary_stats$format[i], summary_stats$avg_revenue[i],
              summary_stats$avg_efficiency[i], summary_stats$avg_surplus[i]))
}

First-Price:
  Revenue: 74.18  |  Efficiency: 1.000  |  Winner surplus: 12.84

Vickrey (Open):
  Revenue: 74.88  |  Efficiency: 1.000  |  Winner surplus: 12.14

Vickrey (ideal MPC target):
  Revenue: 74.88  |  Efficiency: 1.000  |  Winner surplus: 12.14

Static publication-ready figure

The figure compares the revenue distributions across the three auction formats. By the revenue equivalence theorem, first-price and second-price auctions yield the same expected revenue with risk-neutral bidders, but the distributions differ.

p_static <- ggplot(sim_results, aes(x = revenue, fill = format)) +
  geom_density(alpha = 0.6, color = NA) +
  scale_fill_manual(
    values = c("First-Price" = okabe_ito[1],
               "Vickrey (Open)" = okabe_ito[2],
               "Vickrey (ideal MPC target)" = okabe_ito[3]),
    name = "Auction Format"
  ) +
  geom_vline(data = summary_stats, aes(xintercept = avg_revenue, color = format),
             linetype = "dashed", linewidth = 0.6, show.legend = FALSE) +
  scale_color_manual(
    values = c("First-Price" = okabe_ito[1],
               "Vickrey (Open)" = okabe_ito[2],
               "Vickrey (ideal MPC target)" = okabe_ito[3])
  ) +
  labs(
    title = "Revenue Distribution by Auction Format",
    subtitle = "Dashed lines indicate mean revenue; ideal target duplicates the centralized outcome",
    x = "Revenue", y = "Density"
  ) +
  theme_publication()

p_static
Figure 1: Figure 1. Revenue distributions across auction formats. First-price auctions (with equilibrium bid shading) and Vickrey auctions (centralized and ideal-function target) yield similar expected revenue by the revenue equivalence theorem, with the first-price and Vickrey distributions differing in variance. The ideal MPC target is a copy of the centralized Vickrey result; privacy is not implemented or measured. 1000 simulations with 6 bidders, valuations drawn from U[10, 100].

Interactive figure

The interactive version adds per-format summary statistics on hover.

# Create binned data for better tooltips
bin_data <- sim_results |>
  mutate(revenue_bin = round(revenue / 2) * 2) |>
  group_by(format, revenue_bin) |>
  summarise(count = n(), .groups = "drop") |>
  group_by(format) |>
  mutate(
    density = count / sum(count),
    tooltip_text = paste0(
      "Format: ", format, "\n",
      "Revenue bin: ", revenue_bin, "\n",
      "Count: ", count
    )
  )

p_inter <- ggplot(bin_data, aes(x = revenue_bin, y = density, fill = format, text = tooltip_text)) +
  geom_col(alpha = 0.6, position = "identity", width = 2) +
  scale_fill_manual(
    values = c("First-Price" = okabe_ito[1],
               "Vickrey (Open)" = okabe_ito[2],
               "Vickrey (ideal MPC target)" = okabe_ito[3]),
    name = "Format"
  ) +
  labs(
    title = "Revenue Distribution by Auction Format (Interactive)",
    x = "Revenue", y = "Relative Frequency"
  ) +
  theme_publication()

ggplotly(p_inter, tooltip = "text") |>
  config(displaylogo = FALSE, modeBarButtonsToRemove = c("select2d", "lasso2d"))
Figure 2

Interpretation

The reconstruction and addition examples demonstrate finite-field identities. Shamir’s privacy theorem requires independent uniform coefficients from the entire field, including zero; see the original paper. This deterministic teaching setup uses R’s ordinary random generator and small fields, and must not be used to protect real secrets.

For independent risk-neutral valuations on U[10,100], the first-price equilibrium bid is \(10 + (n-1)(v-10)/n\). Including the lower support endpoint matters: multiplying \(v\) alone by \((n-1)/n\) understates bids. The simulated revenues illustrate the model’s expected-revenue relationship; a finite simulation does not prove it.

The two Vickrey series are identical by construction. Both use centralized which.max and sorting over plaintext bids. The second series represents the function that a secure protocol would need to compute, not an implemented MPC protocol or a privacy experiment. Secret sharing alone does not implement secure comparisons, guarantee honest execution or establish incentive compatibility in an adversarial communication setting. A real deployment needs a specified threat model, suitable randomness and field sizes, a reviewed protocol and independent security evaluation. Those tasks are outside this tutorial.

References

Back to top

Reuse

Citation

BibTeX citation:
@online{heller2026,
  author = {Heller, Raban},
  title = {Secure {Multi-Party} {Computation} and {Game-Theoretic}
    {Incentives}},
  date = {2026-05-08},
  url = {https://cttir.github.io/equilibria/tutorials/cryptography-and-gt/secure-multiparty-computation/},
  langid = {en}
}
For attribution, please cite this work as:
Heller, Raban. 2026. “Secure Multi-Party Computation and Game-Theoretic Incentives.” May 8. https://cttir.github.io/equilibria/tutorials/cryptography-and-gt/secure-multiparty-computation/.