Mental Poker

Introduction

Alice and Bob want to play poker, but they are on opposite ends of a phone line. There is no dealer, no table and no deck, and neither trusts the other. Someone must shuffle, and whoever shuffles knows the order of the cards. Someone must deal, and whoever deals could cheat. Can the game be played fairly anyway?

In 1979 Adi Shamir, Ron Rivest and Leonard Adleman, the three letters of RSA, wrote a technical memo at MIT called Mental Poker (MIT/LCS/TM-125). It reappeared in 1981 in Klarner's collection The Mathematical Gardner. Their answer was yes, with a protocol that fits in a few lines.

The idea is a pair of padlocks that commute. Alice puts her padlock on every card and shuffles. Bob adds his own padlock to every card and shuffles again. Now each card wears two locks. Whoever holds a card can ask the other player to remove their lock, and then remove their own. Alice's padlock hides each card from Bob, Bob's from Alice, and since either can be removed first, the order of locking does not matter.

Mathematically a padlock is an exponent. Pick a prime $p$ and a secret $e$ with $\gcd(e, p-1) = 1$ . Locking a card $m$ means computing

E_e(m) = m^{e} \bmod p,

and unlocking uses the exponent $d$ with $ed \equiv 1 \pmod{p-1}$ , because Fermat's little theorem gives $(m^{e})^{d} \equiv m \pmod p$ . Locks commute because exponents multiply: $(m^{a})^{b} = (m^{b})^{a} = m^{ab}$ . This is the same modular exponentiation that powers Diffie–Hellman, and its secrecy rests on the hardness of the discrete logarithm problem.

Setup:  public prime p, card i is encoded as a number m_i
1. Alice: choose key a; send shuffle( m_i^a mod p ) to Bob
2. Bob:   choose key b; send shuffle( c^b mod p ) back to Alice
3. Deal:  for Alice's slot, Bob removes b, Alice removes a
          for Bob's slot,   Alice removes a, Bob removes b
4. End:   both reveal keys; anyone can unlock every slot

Deal a Hand Without a Dealer

Step through a full game between Alice and Bob. Every number is computed with exact big-integer arithmetic modulo a small prime, so you can follow the ciphertexts by eye. Next step locks the deck twice, deals two cards to each player and ends with a showdown in which both keys are revealed and everything is checked.

<p class="hint">Two players, no dealer, ten cards. Every number is real arithmetic modulo the 31-bit toy prime p = 2147483647 (real deployments use 2048 bits or more, never this).</p>
<label class="enc">Card encoding
  <select id="enc" aria-label="Card encoding">
    <option value="naive">Naive: card k is the number k + 2 (leaks)</option>
    <option value="safe">Safe: card k is (k + 2)² mod p (quadratic residue)</option>
  </select>
</label>
<div class="btns">
  <button id="next" type="button">Next step</button>
  <button id="reset" type="button" class="ghost">New game</button>
</div>
<div class="stage" id="stage"></div>
<div id="view"></div>
<div id="leak"></div>

:root { --fg: #1c2530; --bg: #ffffff; --muted: #55606c; --card: #f1f4f8; --line: #cdd6e0; --accent: #1d3557; --accent-fg: #ffffff; --good: #0a7d33; --bad: #c92f3c; --warn-bg: #fdecee; --ok-bg: #e7f6ec; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e6ebf1; --bg: #161b22; --muted: #9aa7b6; --card: #222a34; --line: #3a4553; --accent: #7fb0e8; --accent-fg: #0d1117; --good: #4cc77a; --bad: #ff7b87; --warn-bg: #3a2125; --ok-bg: #1b3326; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.enc { display: block; font-size: .85rem; font-weight: 600; margin-bottom: .5rem; }
select { display: block; width: 100%; margin-top: .25rem; font: 14px system-ui, sans-serif; padding: .4rem; color: var(--fg); background: var(--card); border: 1px solid var(--line); border-radius: 8px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--accent); background: var(--accent); color: var(--accent-fg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button:disabled { opacity: .45; cursor: default; }
.stage { font-weight: 700; font-size: .95rem; margin: .2rem 0; }
.msg { font-size: .88rem; line-height: 1.45; margin: .2rem 0 .6rem; }
.grid { display: grid; grid-template-columns: repeat(auto-fill, minmax(104px, 1fr)); gap: 6px; margin-bottom: .6rem; }
.chip { display: flex; flex-direction: column; gap: 2px; padding: 5px 7px; background: var(--card); border: 1px solid var(--line); border-radius: 8px; position: relative; min-width: 0; }
.chip b { font-size: .85rem; }
.chip code { font: 11px ui-monospace, monospace; color: var(--muted); overflow-wrap: anywhere; }
.chip i { position: absolute; top: 4px; right: 7px; font-style: normal; font-weight: 800; }
.qr { color: var(--good); }
.nr { color: var(--bad); }
table { border-collapse: collapse; width: 100%; font-size: .8rem; margin-bottom: .6rem; }
th, td { border-bottom: 1px solid var(--line); padding: 3px 4px; text-align: left; }
td code { font: 11px ui-monospace, monospace; overflow-wrap: anywhere; }
.keys { font: 11px ui-monospace, monospace; color: var(--muted); overflow-wrap: anywhere; margin: .2rem 0 .6rem; }
.verdict { padding: .5rem .7rem; border-radius: 8px; background: var(--ok-bg); color: var(--good); font-weight: 600; font-size: .88rem; margin-bottom: .6rem; }
.verdict.bad { background: var(--warn-bg); color: var(--bad); }
.leakbox { border: 1px dashed var(--line); border-radius: 10px; padding: .5rem .6rem; margin-top: .4rem; }
.leakbox h4 { margin: 0 0 .4rem; font-size: .88rem; }
.leakbox p { margin: 0; font-size: .85rem; line-height: 1.45; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const P = 2147483647n;
const PM1 = P - 1n;
const NAMES = ['A♠', 'K♠', 'Q♠', 'J♠', '10♠', 'A♥', 'K♥', 'Q♥', 'J♥', '10♥'];
const modpow = (b, e, m) => { let r = 1n; b %= m; while (e > 0n) { if (e & 1n) r = r * b % m; b = b * b % m; e >>= 1n; } return r; };
const gcd = (a, b) => { while (b) { [a, b] = [b, a % b]; } return a; };
const modinv = (a, m) => {
  let r0 = a, r1 = m, s0 = 1n, s1 = 0n;
  while (r1) { const q = r0 / r1; [r0, r1] = [r1, r0 - q * r1]; [s0, s1] = [s1, s0 - q * s1]; }
  return ((s0 % m) + m) % m;
};
const rnd = (n) => BigInt(Math.floor(Math.random() * Number(n)));
const makeKey = () => { for (;;) { const e = 3n + rnd(PM1 - 3n); if (gcd(e, PM1) === 1n) return { e, d: modinv(e, PM1) }; } };
const legendre = (x) => (modpow(x, (P - 1n) / 2n, P) === 1n ? 1 : -1);
const encode = (i, safe) => { const b = BigInt(i + 2); return safe ? b * b % P : b; };
const lock = (m, k) => modpow(m, k, P);
const shuffled = (n) => { const idx = Array.from({ length: n }, (_, i) => i); for (let i = n - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [idx[i], idx[j]] = [idx[j], idx[i]]; } return idx; };

let G = null;
const newGame = (safe) => {
  G = { safe, step: 0, a: makeKey(), b: makeKey(), plain: NAMES.map((_, i) => encode(i, safe)) };
  G.lookup = new Map(G.plain.map((v, i) => [v.toString(), i]));
};
const advance = () => {
  if (G.step >= 4) return;
  G.step++;
  if (G.step === 1) {
    G.permA = shuffled(10);
    G.deckA = G.permA.map((i) => lock(G.plain[i], G.a.e));
  } else if (G.step === 2) {
    G.permB = shuffled(10);
    G.deckAB = G.permB.map((i) => G.deckA[i]).map((c) => lock(c, G.b.e));
    G.cardAt = G.permB.map((i) => G.permA[i]);
  } else if (G.step === 3) {
    G.deal = [];
    for (let s = 0; s < 4; s++) {
      const alice = s < 2;
      const half = alice ? lock(G.deckAB[s], G.b.d) : lock(G.deckAB[s], G.a.d);
      const fin = alice ? lock(half, G.a.d) : lock(half, G.b.d);
      G.deal.push({ s, alice, half, fin, card: G.lookup.get(fin.toString()) });
    }
  } else if (G.step === 4) {
    const seen = new Set();
    G.reveal = G.deckAB.map((c) => {
      const m = lock(lock(c, G.a.d), G.b.d);
      const idx = G.lookup.has(m.toString()) ? G.lookup.get(m.toString()) : -1;
      if (idx >= 0) seen.add(idx);
      return idx;
    });
    const handsOk = G.deal.every((d) => G.reveal[d.s] === d.card);
    G.verified = seen.size === 10 && handsOk && G.reveal.every((x, s) => x === G.cardAt[s]);
  }
};

const chip = (nm, v, bit) => '<div class="chip"><b>' + nm + '</b><code>' + v + '</code>' + (bit === undefined ? '' : '<i class="' + (bit > 0 ? 'qr' : 'nr') + '">' + (bit > 0 ? '+' : '−') + '</i>') + '</div>';
const STAGES = ["Step 0 · Public deck", "Step 1 · Alice locks and shuffles", "Step 2 · Bob locks and shuffles", "Step 3 · Dealing the hands", "Step 4 · Showdown"];
const MSGS = ["The ten cards are public numbers below p. The sign shows each number's quadratic-residue bit (+ residue, − non-residue).", "Alice picks a secret exponent a, replaces every card m by m^a mod p and shuffles. Bob receives ten numbers he cannot map back to cards.", "Bob picks a secret exponent b, locks every number again with b and shuffles. Both locks are now on every card and nobody knows the order.", "Slots 1 and 2 go to Alice: Bob removes his lock, then Alice removes hers and reads the card. Slots 3 and 4 go to Bob: Alice removes her lock first. Each player ends up seeing only their own two cards.", "Both players reveal their keys. Anyone can now unlock all ten slots and check the deck and the hands."];
const who = (alice) => (alice ? "Alice" : "Bob");

function render() {
  const g = G;
  document.getElementById('stage').textContent = STAGES[g.step];
  document.getElementById('next').disabled = g.step >= 4;
  let h = '<p class="msg">' + MSGS[g.step] + '</p>';
  const hidden = "secret";
  const ka = g.step >= 4 ? g.a.e + ' / ' + g.a.d : (g.step >= 1 ? hidden : '–');
  const kb = g.step >= 4 ? g.b.e + ' / ' + g.b.d : (g.step >= 2 ? hidden : '–');
  h += '<p class="keys">' + i18nFmt("Alice a / a⁻¹ = %a% · Bob b / b⁻¹ = %b%", { a: ka, b: kb }) + '</p>';
  if (g.step === 0) {
    h += '<div class="grid">' + g.plain.map((v, i) => chip(NAMES[i], v, legendre(v))).join('') + '</div>';
  } else if (g.step === 1) {
    h += '<div class="grid">' + g.deckA.map((v, s) => chip('#' + (s + 1), v)).join('') + '</div>';
  } else if (g.step === 2) {
    h += '<div class="grid">' + g.deckAB.map((v, s) => chip('#' + (s + 1), v)).join('') + '</div>';
  } else if (g.step === 3) {
    h += '<table><tr><th>#</th><th>' + "Hand" + '</th><th>' + "After one unlock" + '</th><th>' + "Card" + '</th></tr>';
    h += g.deal.map((d) => '<tr><td>' + (d.s + 1) + '</td><td>' + who(d.alice) + '</td><td><code>' + d.half + '</code></td><td><b>' + NAMES[d.card] + '</b></td></tr>').join('');
    h += '</table>';
  } else {
    h += '<table><tr><th>#</th><th>' + "Doubly locked" + '</th><th>' + "Card" + '</th></tr>';
    h += g.reveal.map((x, s) => '<tr><td>' + (s + 1) + '</td><td><code>' + g.deckAB[s] + '</code></td><td><b>' + (x >= 0 ? NAMES[x] : '?') + '</b></td></tr>').join('');
    h += '</table>';
    h += '<div class="verdict' + (g.verified ? '' : ' bad') + '">' + (g.verified ? "Verified: the ten slots decode to ten distinct valid cards and both hands match the deal." : "Verification failed: the deck or a hand does not match.") + '</div>';
  }
  document.getElementById('view').innerHTML = h;
  renderLeak();
}

function renderLeak() {
  const g = G;
  const box = document.getElementById('leak');
  if (g.step < 1) { box.innerHTML = ''; return; }
  const bits = g.deckA.map((c) => legendre(c));
  const q = bits.filter((b) => b > 0).length;
  const n = 10 - q;
  let h = '<div class="leakbox"><h4>' + "What Bob computes from Alice's locked deck" + '</h4>';
  h += '<div class="grid">' + g.deckA.map((v, s) => chip('#' + (s + 1), v, bits[s])).join('') + '</div>';
  if (q === 10 || n === 10) {
    h += '<p>' + "Every slot is a residue (+). The bit is identical for all cards, so Bob learns nothing from it." + '</p>';
  } else {
    const match = bits.filter((b, s) => b === legendre(g.plain[g.permA[s]])).length;
    const avg = ((q * q + n * n) / 10).toFixed(1);
    h += '<p>' + i18nFmt("Bob raises each number to (p−1)/2 and reads the residue bit: %q% residues, %n% non-residues. The bit equals the bit of the hidden card in %m% of 10 slots, so a slot is narrowed to a class of cards (on average %c% of the 10).", { q, n, m: match, c: avg }) + '</p>';
  }
  box.innerHTML = h + '</div>';
}

const start = () => { newGame(document.getElementById('enc').value === 'safe'); render(); };
document.getElementById('next').addEventListener('click', () => { advance(); render(); });
document.getElementById('reset').addEventListener('click', start);
document.getElementById('enc').addEventListener('change', start);
start();

<p class="hint">Two players, no dealer, ten cards. Every number is real arithmetic modulo the 31-bit toy prime p = 2147483647 (real deployments use 2048 bits or more, never this).</p>
<label class="enc">Card encoding
  <select id="enc" aria-label="Card encoding">
    <option value="naive">Naive: card k is the number k + 2 (leaks)</option>
    <option value="safe">Safe: card k is (k + 2)² mod p (quadratic residue)</option>
  </select>
</label>
<div class="btns">
  <button id="next" type="button">Next step</button>
  <button id="reset" type="button" class="ghost">New game</button>
</div>
<div class="stage" id="stage"></div>
<div id="view"></div>
<div id="leak"></div>

:root { --fg: #1c2530; --bg: #ffffff; --muted: #55606c; --card: #f1f4f8; --line: #cdd6e0; --accent: #1d3557; --accent-fg: #ffffff; --good: #0a7d33; --bad: #c92f3c; --warn-bg: #fdecee; --ok-bg: #e7f6ec; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e6ebf1; --bg: #161b22; --muted: #9aa7b6; --card: #222a34; --line: #3a4553; --accent: #7fb0e8; --accent-fg: #0d1117; --good: #4cc77a; --bad: #ff7b87; --warn-bg: #3a2125; --ok-bg: #1b3326; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.enc { display: block; font-size: .85rem; font-weight: 600; margin-bottom: .5rem; }
select { display: block; width: 100%; margin-top: .25rem; font: 14px system-ui, sans-serif; padding: .4rem; color: var(--fg); background: var(--card); border: 1px solid var(--line); border-radius: 8px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--accent); background: var(--accent); color: var(--accent-fg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
button:disabled { opacity: .45; cursor: default; }
.stage { font-weight: 700; font-size: .95rem; margin: .2rem 0; }
.msg { font-size: .88rem; line-height: 1.45; margin: .2rem 0 .6rem; }
.grid { display: grid; grid-template-columns: repeat(auto-fill, minmax(104px, 1fr)); gap: 6px; margin-bottom: .6rem; }
.chip { display: flex; flex-direction: column; gap: 2px; padding: 5px 7px; background: var(--card); border: 1px solid var(--line); border-radius: 8px; position: relative; min-width: 0; }
.chip b { font-size: .85rem; }
.chip code { font: 11px ui-monospace, monospace; color: var(--muted); overflow-wrap: anywhere; }
.chip i { position: absolute; top: 4px; right: 7px; font-style: normal; font-weight: 800; }
.qr { color: var(--good); }
.nr { color: var(--bad); }
table { border-collapse: collapse; width: 100%; font-size: .8rem; margin-bottom: .6rem; }
th, td { border-bottom: 1px solid var(--line); padding: 3px 4px; text-align: left; }
td code { font: 11px ui-monospace, monospace; overflow-wrap: anywhere; }
.keys { font: 11px ui-monospace, monospace; color: var(--muted); overflow-wrap: anywhere; margin: .2rem 0 .6rem; }
.verdict { padding: .5rem .7rem; border-radius: 8px; background: var(--ok-bg); color: var(--good); font-weight: 600; font-size: .88rem; margin-bottom: .6rem; }
.verdict.bad { background: var(--warn-bg); color: var(--bad); }
.leakbox { border: 1px dashed var(--line); border-radius: 10px; padding: .5rem .6rem; margin-top: .4rem; }
.leakbox h4 { margin: 0 0 .4rem; font-size: .88rem; }
.leakbox p { margin: 0; font-size: .85rem; line-height: 1.45; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const P = 2147483647n;
const PM1 = P - 1n;
const NAMES = ['A♠', 'K♠', 'Q♠', 'J♠', '10♠', 'A♥', 'K♥', 'Q♥', 'J♥', '10♥'];
const modpow = (b, e, m) => { let r = 1n; b %= m; while (e > 0n) { if (e & 1n) r = r * b % m; b = b * b % m; e >>= 1n; } return r; };
const gcd = (a, b) => { while (b) { [a, b] = [b, a % b]; } return a; };
const modinv = (a, m) => {
  let r0 = a, r1 = m, s0 = 1n, s1 = 0n;
  while (r1) { const q = r0 / r1; [r0, r1] = [r1, r0 - q * r1]; [s0, s1] = [s1, s0 - q * s1]; }
  return ((s0 % m) + m) % m;
};
const rnd = (n) => BigInt(Math.floor(Math.random() * Number(n)));
const makeKey = () => { for (;;) { const e = 3n + rnd(PM1 - 3n); if (gcd(e, PM1) === 1n) return { e, d: modinv(e, PM1) }; } };
const legendre = (x) => (modpow(x, (P - 1n) / 2n, P) === 1n ? 1 : -1);
const encode = (i, safe) => { const b = BigInt(i + 2); return safe ? b * b % P : b; };
const lock = (m, k) => modpow(m, k, P);
const shuffled = (n) => { const idx = Array.from({ length: n }, (_, i) => i); for (let i = n - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [idx[i], idx[j]] = [idx[j], idx[i]]; } return idx; };

let G = null;
const newGame = (safe) => {
  G = { safe, step: 0, a: makeKey(), b: makeKey(), plain: NAMES.map((_, i) => encode(i, safe)) };
  G.lookup = new Map(G.plain.map((v, i) => [v.toString(), i]));
};
const advance = () => {
  if (G.step >= 4) return;
  G.step++;
  if (G.step === 1) {
    G.permA = shuffled(10);
    G.deckA = G.permA.map((i) => lock(G.plain[i], G.a.e));
  } else if (G.step === 2) {
    G.permB = shuffled(10);
    G.deckAB = G.permB.map((i) => G.deckA[i]).map((c) => lock(c, G.b.e));
    G.cardAt = G.permB.map((i) => G.permA[i]);
  } else if (G.step === 3) {
    G.deal = [];
    for (let s = 0; s < 4; s++) {
      const alice = s < 2;
      const half = alice ? lock(G.deckAB[s], G.b.d) : lock(G.deckAB[s], G.a.d);
      const fin = alice ? lock(half, G.a.d) : lock(half, G.b.d);
      G.deal.push({ s, alice, half, fin, card: G.lookup.get(fin.toString()) });
    }
  } else if (G.step === 4) {
    const seen = new Set();
    G.reveal = G.deckAB.map((c) => {
      const m = lock(lock(c, G.a.d), G.b.d);
      const idx = G.lookup.has(m.toString()) ? G.lookup.get(m.toString()) : -1;
      if (idx >= 0) seen.add(idx);
      return idx;
    });
    const handsOk = G.deal.every((d) => G.reveal[d.s] === d.card);
    G.verified = seen.size === 10 && handsOk && G.reveal.every((x, s) => x === G.cardAt[s]);
  }
};

const chip = (nm, v, bit) => '<div class="chip"><b>' + nm + '</b><code>' + v + '</code>' + (bit === undefined ? '' : '<i class="' + (bit > 0 ? 'qr' : 'nr') + '">' + (bit > 0 ? '+' : '−') + '</i>') + '</div>';
const STAGES = ["Step 0 · Public deck", "Step 1 · Alice locks and shuffles", "Step 2 · Bob locks and shuffles", "Step 3 · Dealing the hands", "Step 4 · Showdown"];
const MSGS = ["The ten cards are public numbers below p. The sign shows each number's quadratic-residue bit (+ residue, − non-residue).", "Alice picks a secret exponent a, replaces every card m by m^a mod p and shuffles. Bob receives ten numbers he cannot map back to cards.", "Bob picks a secret exponent b, locks every number again with b and shuffles. Both locks are now on every card and nobody knows the order.", "Slots 1 and 2 go to Alice: Bob removes his lock, then Alice removes hers and reads the card. Slots 3 and 4 go to Bob: Alice removes her lock first. Each player ends up seeing only their own two cards.", "Both players reveal their keys. Anyone can now unlock all ten slots and check the deck and the hands."];
const who = (alice) => (alice ? "Alice" : "Bob");

function render() {
  const g = G;
  document.getElementById('stage').textContent = STAGES[g.step];
  document.getElementById('next').disabled = g.step >= 4;
  let h = '<p class="msg">' + MSGS[g.step] + '</p>';
  const hidden = "secret";
  const ka = g.step >= 4 ? g.a.e + ' / ' + g.a.d : (g.step >= 1 ? hidden : '–');
  const kb = g.step >= 4 ? g.b.e + ' / ' + g.b.d : (g.step >= 2 ? hidden : '–');
  h += '<p class="keys">' + i18nFmt("Alice a / a⁻¹ = %a% · Bob b / b⁻¹ = %b%", { a: ka, b: kb }) + '</p>';
  if (g.step === 0) {
    h += '<div class="grid">' + g.plain.map((v, i) => chip(NAMES[i], v, legendre(v))).join('') + '</div>';
  } else if (g.step === 1) {
    h += '<div class="grid">' + g.deckA.map((v, s) => chip('#' + (s + 1), v)).join('') + '</div>';
  } else if (g.step === 2) {
    h += '<div class="grid">' + g.deckAB.map((v, s) => chip('#' + (s + 1), v)).join('') + '</div>';
  } else if (g.step === 3) {
    h += '<table><tr><th>#</th><th>' + "Hand" + '</th><th>' + "After one unlock" + '</th><th>' + "Card" + '</th></tr>';
    h += g.deal.map((d) => '<tr><td>' + (d.s + 1) + '</td><td>' + who(d.alice) + '</td><td><code>' + d.half + '</code></td><td><b>' + NAMES[d.card] + '</b></td></tr>').join('');
    h += '</table>';
  } else {
    h += '<table><tr><th>#</th><th>' + "Doubly locked" + '</th><th>' + "Card" + '</th></tr>';
    h += g.reveal.map((x, s) => '<tr><td>' + (s + 1) + '</td><td><code>' + g.deckAB[s] + '</code></td><td><b>' + (x >= 0 ? NAMES[x] : '?') + '</b></td></tr>').join('');
    h += '</table>';
    h += '<div class="verdict' + (g.verified ? '' : ' bad') + '">' + (g.verified ? "Verified: the ten slots decode to ten distinct valid cards and both hands match the deal." : "Verification failed: the deck or a hand does not match.") + '</div>';
  }
  document.getElementById('view').innerHTML = h;
  renderLeak();
}

function renderLeak() {
  const g = G;
  const box = document.getElementById('leak');
  if (g.step < 1) { box.innerHTML = ''; return; }
  const bits = g.deckA.map((c) => legendre(c));
  const q = bits.filter((b) => b > 0).length;
  const n = 10 - q;
  let h = '<div class="leakbox"><h4>' + "What Bob computes from Alice's locked deck" + '</h4>';
  h += '<div class="grid">' + g.deckA.map((v, s) => chip('#' + (s + 1), v, bits[s])).join('') + '</div>';
  if (q === 10 || n === 10) {
    h += '<p>' + "Every slot is a residue (+). The bit is identical for all cards, so Bob learns nothing from it." + '</p>';
  } else {
    const match = bits.filter((b, s) => b === legendre(g.plain[g.permA[s]])).length;
    const avg = ((q * q + n * n) / 10).toFixed(1);
    h += '<p>' + i18nFmt("Bob raises each number to (p−1)/2 and reads the residue bit: %q% residues, %n% non-residues. The bit equals the bit of the hidden card in %m% of 10 slots, so a slot is narrowed to a class of cards (on average %c% of the 10).", { q, n, m: match, c: avg }) + '</p>';
  }
  box.innerHTML = h + '</div>';
}

const start = () => { newGame(document.getElementById('enc').value === 'safe'); render(); };
document.getElementById('next').addEventListener('click', () => { advance(); render(); });
document.getElementById('reset').addEventListener('click', start);
document.getElementById('enc').addEventListener('change', start);
start();

Result

Console

Now the interesting part. Leave the encoding on Naive, where card $k$ is simply the number $k+2$ , and press Next step once. Below the deck, the dashed box shows what Bob can compute from Alice's locked deck alone: the sign of each ciphertext is the same sign as the hidden card. Bob has learned one bit about every card without breaking any lock. Switch to Safe, where cards are encoded as squares modulo $p$ , and the signs all collapse to the same value.

Why? By Euler's criterion, $x$ is a quadratic residue modulo $p$ exactly when $x^{(p-1)/2} \equiv 1$ . Raising to an odd power $e$ keeps the sign, since $(m^{e})^{(p-1)/2} = (m^{(p-1)/2})^{e} = (\pm 1)^{e} = \pm 1$ . The lock cannot hide whether a card is a residue.

The Real Cost and the Real Leak

Cost. For a deck of $n$ cards and a $k$ -bit prime, one lock is a modular exponentiation: about $1.5k$ modular multiplications of $k$ -bit numbers, which is $O(k^{3})$ bit operations with schoolbook arithmetic. In the protocol above each player locks the deck once, unlocks the cards they deal and checks the deck at the end, so each does $O(n)$ exponentiations in total, $O(n\,k^{3})$ bit operations. Each message carries $n$ numbers of $k$ bits, $O(nk)$ bits, and the number of rounds is constant. A shuffle itself is a random permutation among $n!$ possibilities; for $n=52$ that is about $8\times 10^{67}$ , and Fisher–Yates produces one in $O(n)$ steps.

Parameters. The prime should be a safe prime $p = 2q+1$ with $q$ prime, and large (2048 bits or more for modern use). If $p-1$ is a product of small primes, the discrete logarithm falls to the Pohlig–Hellman algorithm and keys can be recovered; the prime used in the demo, $2^{31}-1$ , is exactly like that, and is only a toy.

The leak. Richard Lipton observed, in a 1981 AMS short-course paper titled How to cheat at mental poker, that the scheme reveals partial information. Since $e$ is odd, $\left(\tfrac{m^{e}}{p}\right) = \left(\tfrac{m}{p}\right)^{e} = \left(\tfrac{m}{p}\right)$ : whether a card is a quadratic residue survives encryption and can be read by anyone. If the card encodings include both residues and non-residues, Bob learns a bit about every card of Alice's locked deck.

The fix, and what it does not fix. Encode every card as a quadratic residue, for instance $m_i = (i+2)^2 \bmod p$ . Then the residuosity bit is $+1$ for every card and carries no information. This removes that particular leak, but the scheme remains deterministic and malleable, so there may be other partial information to find. Goldwasser and Micali took this lesson seriously: in Probabilistic encryption & how to play mental poker keeping secret all partial information (STOC 1982; journal version 1984) they defined what it means to hide all partial information, now called semantic security, and gave a probabilistic encryption scheme built on quadratic residuosity.

Cheating by a player. Honest-but-curious is not enough at a poker table. A cheater could use different keys on different cards or swap cards instead of shuffling. Real protocols add proofs. Commitments such as Pedersen commitments can bind a player to their keys, and zero-knowledge proofs show that a shuffle is a genuine permutation of the input. Neff's verifiable secret shuffle (ACM CCS 2001) is a well-known construction of this kind.

Where It Matters

Mental poker looks like a recreation, but it was the first clean example of two parties computing together without trusting each other, rather than only sending secrets. It reads today as an early case of secure multiparty computation, which grew into the general theory.

Verifiable shuffles and mix-nets: re-encrypting and permuting a list of items in a way that can be proven correct is the core of mix networks. Electronic voting systems use them so ballots can be tallied without linking a ballot to its voter.
Decentralized card games: online poker where no server can see the deck and blockchains or peers replace the dealer, with zero-knowledge proofs keeping each shuffle honest.
Fair coin flips and contract signing: Manuel Blum's Coin Flipping by Telephone (1981) belongs to the same family, using a similar mix of commitment and number theory. See commitment schemes.
Selective disclosure: oblivious transfer, where a receiver gets exactly one of several items without the sender learning which, is a close cousin of dealing a hidden card.
Foundations: the leak of the SRA scheme is one of the motivating examples for provable security. Next time a protocol says "encrypted", ask which partial information it still gives away.

Conclusion

Mental poker shows how much structure a few modular exponentiations can carry: locks that commute, a deck that two parties shuffle without either knowing the order, hands that are dealt in private and a showdown that anyone can verify.

It also shows how subtle secrecy is. The same arithmetic that makes the locks commute makes quadratic residuosity pass straight through them, and one bit per card is enough to ruin a game. The repair was not only a better encoding but a better definition of what it means to hide information, and that definition now underlies modern encryption, from RSA padding to zero-knowledge proofs.

Comments

Loading comments...

https://www.kipuhub.com/en/article/mental-poker/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Dealing cards without a dealer