在通訊軟體擲硬幣 (Coin flipping by telephone)

12 Oct, 2026

阿公在超市購物而阿嬤在健行，他們正在 LINE 上爭執晚餐的湯要喝鹹的還是淡的。

最後他們決定由阿公擲硬幣讓阿嬤猜，阿嬤猜中的話就聽阿嬤的，否則就聽阿公的。問題是，要怎麼避免作弊或是耍賴呢？

如果阿嬤說：「我猜⋯⋯數字那一面」，阿公卻說：「哈哈，猜錯了，是人頭啦」，阿嬤一定不服氣，要阿公證明他沒有作弊（聽到阿嬤猜測後才改口）。

Blum 在 1981 年的 Coin flipping by telephone 提出了一個作法。

基本思路

擲硬幣者（阿公）要提供證據讓猜測者（阿嬤）驗證。
站在猜測者的角度，證據不能在猜測後才拿到，否則擲硬幣者可能會根據猜測來偽造證據。
站在擲硬幣者的角度，在猜測前不能給出全部的證據，否則猜測者就知道硬幣的結果了。

因此，一個可能的流程長得像這樣

擲硬幣者給出硬幣結果的部份證據。
猜測者進行猜測。
擲硬幣者給完整證據。
猜測者驗證。

套回原本的情境

阿公先幫硬幣拍照，並把照片加密後傳給阿嬤，但密碼不給阿嬤。
阿嬤說出他的猜測（人頭或數字）。
阿公把加密照片用的密碼給阿嬤。
阿嬤看到照片，確認阿公說的結果跟照片中的一樣。

或是換個場景（如果不要求遠端溝通）

阿公在紙條上寫人頭或數字，把紙條放進保險箱裡面，把保險箱給阿嬤。
阿嬤說出他的猜測（人頭或數字）。
阿公把保險箱的鑰匙給阿嬤。
阿嬤打開保險箱檢查紙條的內容。

如果你只對原本的問題有興趣而不想看技術細節的話，看到這裡就好了。

設定

為了方便接下來的討論，我們先把流程抽象成這樣

擲硬幣者私下生成亂數 $x$ ，用來產生部份證據 $h (x)$ 以及產生硬幣結果 $c (x)$ ，在猜測者給出猜測後揭露 $x$ 。

我們用 $c (x) = + 1$ 表示結果是人頭， $c (x) = - 1$ 表示結果是數字。

為了不讓擲硬幣者「作弊」，部份證據 $h (x)$ 的產生必須滿足：

擲硬幣者短時間（例如 100 年）內沒辦法找到另一個亂數 $x^{'}$ 產生一樣的部份證據 $h (x^{'}) = h (x)$ 但是硬幣結果相反 $c (x^{'}) = - c (x)$ 。

一般來說， $h$ 會選一個單向函數 (one-way function)。

資訊洩漏

到這邊，問題看似解決了，但有個小問題：部份證據可能洩漏了硬幣結果，也就是猜測者能從部份證據判斷人頭跟數字哪一個的可能性比較高（哪怕只是 49.99% 跟 50.01% 的差異）。

為了解決這個問題，Blum 給出了一種產生部份證據 $h$ 以及硬幣結果 $c$ 的方式，滿足額外的限制：

保證存在其他亂數 $x^{'}$ 可以產生一樣的部份證據 $h (x^{'}) = h (x)$ ，但是硬幣結果相反。
在所有對應到同一個部份證據 $H$ 的亂數 $x$ 中，產生「人頭」與「數字」的亂數數量一樣多。

這麼一來，在給定部份證據 $H$ 的情況下，人頭跟數字對猜測者來說有相同的可能性。

具體公式

先選定 $n = p q$ ，其中 $p, q$ 都是形如 $4 k + 3$ 的質數。

亂數： $x \in [1, n)$ 但要求 $x$ 跟 $n$ 互質（這樣的集合用 $ℤ_{n}^{*}$ 表示）。
部份證據： $h (x) = x^{2} mod n$
硬幣結果： c(x)=(xn)∈{−1,+1} 是 Jacobi symbol。
- Jacobi symbol 可以在 $𝒪 (\log x \log n)$ 的時間內計算出來，不需要知道 $n$ 的質因數分解。

協定流程（簡化版）

猜測者先選定 $n = p q$ ，把 $n$ 告訴擲硬幣者但 $p, q$ 保密。
擲硬幣者選擇亂數 $x \in ℤ_{n}^{*}$ ，把 $h (x) = x^{2} mod n$ 告訴猜測者。
猜測者給出猜測。
擲硬幣者揭露 $x$ 。

簡短分析

給定 $H \in ℤ_{n}^{*}$ （ $n$ 按照之前的方式選取），如果 $y^{2} \equiv H mod n$ 有解，那這個方程式總共會有四個解，並且其中兩個的 Jacobi symbol 是 $+ 1$ ，另外兩個的 Jacobi symbol 是 $- 1$ 。下面給出說明。

存在四個解

給定 $H \in ℤ_{n}^{*}$ ，如果 $y^{2} \equiv H mod n$ 有解，那他的解一定是

{\begin{matrix} y \equiv \pm s \mod p \\ y \equiv \pm r \mod q \end{matrix}

換句話說，模 $n$ 的解有四個： $\pm x$ 跟 $\pm x^{'}$ 。

{\begin{matrix} x \equiv s \mod p \\ x \equiv r \mod q \end{matrix}, {\begin{matrix} - x \equiv - s \mod p \\ - x \equiv - r \mod q \end{matrix}, {\begin{matrix} x^{'} \equiv - s \mod p \\ x^{'} \equiv r \mod q \end{matrix}, {\begin{matrix} - x^{'} \equiv s \mod p \\ - x^{'} \equiv - r \mod q \end{matrix},

兩種硬幣結果各半

由於 Jacobi symbol 的性質

(\frac{- 1}{p}) = {\begin{matrix} + 1, if p \equiv 1 \mod 4 \\ - 1, if p \equiv 3 \mod 4 \end{matrix}

而 $p, q$ 都是選 $4 k + 3$ 的形式，因此 $(\frac{- 1}{p}) = (\frac{- 1}{q}) = - 1$ 。

他們的 Jacobi symbol

(\frac{x}{n}) = (\frac{s}{p}) (\frac{r}{q}) = (\frac{- 1}{p}) (\frac{s}{p}) (\frac{- 1}{q}) (\frac{r}{q}) = (\frac{- s}{p}) (\frac{- r}{q}) = (\frac{- x}{n})

(\frac{x^{'}}{n}) = (\frac{- s}{p}) (\frac{r}{q}) = (\frac{s}{p}) (\frac{- r}{q}) = (\frac{- x^{'}}{n}) = - (\frac{x}{n})

因此這四個解按照 Jacobi symbol 分成兩組：一組是 $x$ 跟 $- x$ ，另一組是 $x^{'}$ 跟 $- x^{'}$ 。一組的 Jacobi symbol 是 $+ 1$ ，另一組是 $- 1$ 。

無法偽造硬幣結果

擲硬幣者生成亂數 $x$ 後只需要告知猜測者 $h (x)$ 的值，直到對方做出猜測後才需要揭露 $x$ 。那擲硬幣者有沒有辦法在聽到猜測後，謊稱他的亂數其實是另一個值呢？

可以，他可以宣稱他當初是選 $- x$ ，並且因為 $h (- x) = x^{2} = h (x)$ ，這個謊稱的值一樣可以通過驗證。不過問題是 $x$ 跟 $- x$ 的 Jacobi symbol 一樣，這樣並沒有辦法改變硬幣結果。

那擲硬幣者有沒有辦法知道另一個分組的解（前面提到的 $x^{'}$ ）呢？很困難，如果找到 $x$ 跟 $x^{'}$ 的話就能夠分解 $n$ ：因為 $x - x^{'} \equiv 0 mod q$ ，所以 $gcd (x - x^{'}, n) = q$ ，只要計算 $x - x^{'}$ 跟 $n$ 的最大公因數就能找到 $n$ 的一個質因數。

Reference:

Manuel Blum. 1983. Coin flipping by telephone a protocol for solving impossible problems. SIGACT News 15, 1 (Winter-Spring 1983), 23–27. https://doi.org/10.1145/1008908.1008911