Toss Coin over Telephone

이 프로토콜은 Manuel Blum(1983) 이 제안한 암호학적 동전 던지기(Coin Flipping over Telephone) 프로토콜이다. 두 참여자가 물리적으로 만나지 않고도 공정한 내기를 할 수 있음을 보여준다.

---

A와 B가 전화 통화를 하며 내기를 한다. A는 동전을 던지고, B는 A가 던진 동전의 면을 맞추는 내기이다. 당연히 A는 B가 말한 내용을 듣고 결과를 바꾸어 말할 수 있다. 공정하게 게임을 하기 위해서는 어떻게 해야 하는가?

핵심 아이디어: 이차 합동식 $x^2 \equiv y \pmod{n}$은 $n$을 소인수분해할 수 있으면 4개의 해를 구할 수 있지만, $n$의 소인수를 모르면 풀기 어렵다는 수학적 성질을 이용한다.

참여자	알고 있는 정보
A	$p,\ q,\ n$ 모두
B	$n$과 자신이 선택한 $x$만

---

프로토콜 흐름

1. A는 다음을 만족하는 3 이상의 소수 $p,\ q \equiv 3 \pmod{4}$를 고르고 B에게 $n = pq$를 전달한다. 이때 $p, q$는 공개하지 않는다.

   • $p \equiv q \equiv 3 \pmod{4}$ 조건은 이후 이차잉여의 제곱근 계산을 쉽게 만들기 위함이다. 이 조건을 만족하는 $n = pq$를 Blum 정수 라고 한다.

2. B는 $\gcd(x, n) = 1$을 만족하는 $x$를 $1 \le x < n$ 범위에서 균등 무작위로 고른 뒤, $y \equiv x^2 \pmod{n}$을 A에게 전달한다. 이때 $x$는 공개하지 않는다.

   • $\gcd(x, n) = 1$이 빠지면 근이 넷이 아니게 된다. $p \mid x$이면 $y$는 $\bmod\ p$에서 $0$이 되어 그쪽 제곱근이 하나뿐이라, $y$의 근이 둘로 줄어든다. 그러면 A가 무엇을 보내든 B가 아는 쌍이라 A가 항상 이긴다. $n = 77$짜리 예시에서는 $x$의 $22.1\%$($77$개 중 $17$개)가 여기에 해당한다. 실제 크기의 $n$에서는 이런 $x$를 뽑을 확률이 $1/p + 1/q$ 수준이라 무시할 만하지만, 조건 자체는 프로토콜의 일부다.
   • 균등 무작위여야 하는 이유는 따로 있다. B의 분포가 한쪽으로 치우쳐 있고 A가 그 사실을 알면, A는 B가 어느 쌍에 있을지 더 잘 추측해 $1/2$보다 유리해진다.

3. A는 $p, q$를 알고 있으므로, CRT(중국인의 나머지 정리) 를 이용하여 $y \equiv x^2 \pmod{n}$의 네 근 $\pm x_1,\ \pm x_2$를 구하고, 이 중 하나를 B에게 전달한다.

   • $p \equiv 3 \pmod{4}$ 조건 덕분에 $r_p \equiv y^{(p+1)/4} \pmod{p}$로 $\pmod{p}$ 제곱근을 쉽게 구할 수 있다. (마찬가지로 $r_q \equiv y^{(q+1)/4} \pmod{q}$)
   • CRT로 두 값을 합성하면 네 근 $x_1,\ n-x_1,\ x_2,\ n-x_2$를 얻는다.

4. B가 선택한 $x$가 $x_1$ 또는 $n - x_1$과 같다고 가정하자.

   • A가 B에게 $x_2$ 또는 $n - x_2$를 전달하면: B는 서로 다른 두 제곱근 $x$와 $x_2$를 모두 알게 된다. 이를 이용해 $\gcd(x - x_2,\ n)$을 계산하면 $p$ 또는 $q$를 구할 수 있다. → B 승리
   • A가 B에게 $x_1$ 또는 $n - x_1$을 전달하면: B는 자신이 이미 아는 값만 얻게 되므로 $p, q$를 구할 수 없다. → A 승리

5. 따라서 B는 A로부터 받은 값으로 $p, q$를 소인수분해할 수 있으면 B의 승리, 그렇지 않으면 A의 승리다.

   • A는 4개의 근 중 어느 것을 줄지 선택할 수 있지만, B의 $x$를 모르기 때문에 자신에게 유리한 것을 고를 수 없다. 네 근은 두 쌍을 이루고 B는 그중 한 쌍 안에 있는데, A가 보는 $y$만으로는 어느 쌍인지 구별할 수 없다.
   • 결과적으로 A가 이길 확률과 B가 이길 확률은 각각 $1/2$이다.

6. B는 A가 보낸 값 $x_1$에 대해 $x_1^2 \equiv y \pmod{n}$이 성립하는지 확인한다. 다만 이 검사가 확인해 주는 것은 응답의 유효성뿐이다.
   • 성립하지 않으면 A가 제곱근이 아닌 값을 보낸 것이므로 그 자리에서 걸린다.
   • 성립하더라도 $n$이 서로 다른 두 소수의 곱인지는 알 수 없다. 이 검사는 $n$의 구조에 대해 아무것도 말해 주지 않는다.
   • 가장 단순한 반칙은 A가 $n$을 소수로 보내는 것이다. 그러면 $y$의 근은 $\pm x$ 둘뿐이라 B는 언제나 자기가 아는 값을 돌려받고, 보낸 값은 제곱 검사를 멀쩡히 통과한다. A가 $100\%$ 이긴다. $n$이 세 소수의 곱이면 근이 여덟 개가 되어 이번에는 B가 $75\%$로 유리해진다.
   • 따라서 $n$이 Blum 정수라는 사실은 별도로 증명되어야 한다. 실무에서는 A가 영지식 증명으로 $n$의 형태를 보인다. 아래 프로토콜의 한계에서 다시 다룬다.

---

수치 예시

작은 숫자로 프로토콜 전 과정을 직접 따라가보자.

준비

A의 선택 (비공개):

• $p = 7$, $q = 11$ — 조건 확인: $7 \equiv 3 \pmod{4}$, $11 \equiv 3 \pmod{4}$ ✓
• $n = pq = 77$ → B에게 공개

B의 선택:

• $x = 15$ (비공개)
• $y \equiv x^2 \pmod{n} = 15^2 \bmod 77 = 225 \bmod 77 = 71$ → A에게 전달

A가 4개의 근을 계산하는 과정

Step 1. $\pmod{p}$ 제곱근 ($r_p$)

$$r_p \equiv y^{(p+1)/4} \equiv 71^{2} \pmod{7}$$

$71 \equiv 1 \pmod{7}$이므로 $r_p = 1^2 = 1$

→ $\pmod{7}$ 제곱근: $\pm 1$ = $1$과 $6$

Step 2. $\pmod{q}$ 제곱근 ($r_q$)

$$r_q \equiv y^{(q+1)/4} \equiv 71^{3} \pmod{11}$$

$71 \equiv 5 \pmod{11}$이므로 $r_q = 5^3 = 125 \equiv 4 \pmod{11}$

→ $\pmod{11}$ 제곱근: $\pm 4$ = $4$와 $7$

Step 3. CRT로 네 근 합성

$\pmod{7}$	$\pmod{11}$	CRT 결과
1	4	15
6	4	48
1	7	29
6	7	62

검증: $15^2,\ 48^2,\ 29^2,\ 62^2$을 모두 $\bmod 77$하면 전부 $71$ ✓

네 근은 두 쌍으로 묶인다: $\{15,\ 62\}$와 $\{29,\ 48\}$

결과 판정

B가 $x = 15$를 골랐으므로, A가 받은 $y = 71$의 네 근 중 같은 쌍은 $\{15,\ 62\}$이다.

A가 29 또는 48을 전달하는 경우 → B 승리

B는 자신의 $x = 15$와 A로부터 받은 $48$을 이용해 소인수분해 가능:

$$\gcd(15 - 48,\ 77) = \gcd(33,\ 77) = 11 = q$$

A가 15 또는 62를 전달하는 경우 → A 승리

B는 자신이 이미 아는 값을 받았을 뿐이므로, 새로운 정보를 얻지 못해 소인수분해 불가.

A는 어느 쌍이 B에게 유리한지 모르므로 결국 50% 확률로 선택하게 된다.

---

왜 공정한가?

이 프로토콜의 안전성은 소인수분해 문제의 어려움 에 기반한다.

핵심 동등성:

$x^2 \equiv y \pmod{n}$의 4개의 근을 모두 구할 수 있다 $\Longleftrightarrow$ $n$을 소인수분해할 수 있다.

증명 (⇐): $n = pq$를 알면 CRT로 4개의 근을 모두 구할 수 있다. (A가 하는 일)

증명 (⇒): 두 제곱근 $x, x'$이 $x' \not\equiv \pm x \pmod n$을 만족한다고 하자. 이 조건을 비자명한 쌍이라 부른다. $x^2 \equiv x'^2$이므로

$$n \mid (x - x')(x + x')$$

이다. $x' \not\equiv x$이므로 $n \nmid (x-x')$이고, $x' \not\equiv -x$이므로 $n \nmid (x+x')$이다. 그런데 $n = pq$가 곱을 나누므로 $p$와 $q$가 두 인수에 하나씩 갈라져 들어간다. 따라서 $\gcd(x - x',\ n)$은 $1$도 $n$도 아닌 진약수, 즉 $p$ 또는 $q$다.

$x' \equiv \pm x$인 경우에는 $\gcd(x-x', n)$이 $n$ 또는 $1$이 되어 아무것도 얻지 못한다. 비자명하다는 조건이 논증의 전부이고, 이것이 이 프로토콜에서 A의 선택이 하는 일이다.

환원의 성공 확률. “제곱근을 하나 돌려주는 상자”가 있다면 인수분해기를 만들 수 있다. $\gcd(x,n)=1$인 $x$를 무작위로 골라 $y = x^2$을 상자에 넣으면, 상자는 $y$의 네 근 중 하나를 돌려준다. 상자는 $y$만 보므로 넷 중 어느 것이 우리가 쓴 $x$인지 알 수 없고, 돌아온 값이 $\pm x$가 아닐 확률이 $1/2$이다. 그때 $\gcd$ 한 번으로 인수가 나온다. 한 번에 실패해도 다시 시도하면 되므로, $k$번 반복하면 실패 확률이 $2^{-k}$로 떨어진다. 한 번에 되는 결정적 환원이 아니라 확률적 환원이라는 점이 중요하다.

공정성 보장:

• A는 B가 어떤 $x$를 골랐는지 모르므로, B에게 유리한 쌍 $(x_2,\ n-x_2)$을 골라줄지, 불리한 쌍 $(x_1,\ n-x_1)$을 줄지 알 수 없다.
• 결과적으로 A의 선택은 사실상 랜덤 이며, 각 참여자의 승률은 정확히 $1/2$이다.
• 다만 이 값은 앞서 나열한 전제 위에서만 성립한다. 파라미터가 정직하게 생성됐고, B가 균등하게 뽑았으며, A가 $y$만으로 쌍을 구별할 수 없다는 계산적 가정이 유지될 때다. 그리고 어느 쪽도 중간에 끊지 않아야 한다.

---

공격 시나리오

공격자	시도	왜 실패하는가
A	제곱근이 아닌 값 전달	B가 $x_1^2 \equiv y \pmod{n}$ 검증으로 탐지 가능
A	결과 발표 직전 유리한 근 선택	B의 $x$를 모르므로 어느 쌍이 유리한지 알 수 없음
B	$x$ 사후 변경	$y = x^2 \bmod n$으로 이미 커밋 — 변경 불가
A	Blum 정수 아닌 $n$ 사용	제곱 검증으로는 탐지되지 않는다. $n$이 소수면 근이 둘뿐이라 A가 항상 이긴다. 영지식 증명이 따로 필요하다

---

용어 정리

---

이차잉여 (Quadratic Residue)

정의: 정수 $a$가 $n$의 이차잉여 라는 것은, $x^2 \equiv a \pmod{n}$을 만족하는 정수 $x$가 존재함을 의미한다.

소수 모듈러스에서의 제곱근 개수:

• 소수 $p$에 대해, $a \not\equiv 0 \pmod{p}$인 이차잉여 $a$의 제곱근은 정확히 2개 ($\pm r$)이다.

합성수 모듈러스에서의 제곱근 개수:

• $n = pq$ ($p, q$: 서로 다른 소수)일 때, $y$가 $n$의 이차잉여이면 $x^2 \equiv y \pmod{n}$의 해는 정확히 4개 ($x_1,\ n-x_1,\ x_2,\ n-x_2$)이다.
• $y$가 이차잉여가 아니면 해가 없다.
• 이는 CRT에 의해 $\pmod{p}$의 해 2개와 $\pmod{q}$의 해 2개를 조합하기 때문이다.
• 핵심: $n$의 소인수를 알면 4개의 근을 모두 구할 수 있지만, 모르면 하나의 근에서 나머지를 유추하기 어렵다.

왜 $p \equiv 3 \pmod{4}$인가?

$\pmod{p}$ 제곱근을 구하는 공식 $r_p \equiv y^{(p+1)/4} \pmod{p}$가 성립하는 이유를 확인해보자.

전제 조건: $p$가 소수이고, $y$가 $p$의 이차잉여이면, Euler’s Criterion 에 의해 다음이 성립한다.

$$y^{(p-1)/2} \equiv 1 \pmod{p}$$

검증:

$$\left(y^{(p+1)/4}\right)^2 = y^{(p+1)/2} = y^{(p-1)/2} \cdot y \equiv 1 \cdot y = y \pmod{p}$$

• 즉, $r_p = y^{(p+1)/4}$는 실제로 $y$의 $\pmod{p}$ 제곱근이 맞다.
• 단, 이 공식이 정수 가 되려면 $(p+1)/4$가 정수여야 하므로, $p \equiv 3 \pmod{4}$ 조건이 필요하다.
  • $p \equiv 1 \pmod{4}$이면 $(p+1)/4$가 정수가 아니므로 이 방법을 쓸 수 없다.

---

프로토콜의 한계

1. A의 Blum 정수 미준수: 6단계의 제곱 검사는 응답이 $y$의 제곱근인지만 확인할 뿐, $n$의 구조는 건드리지 못한다. A가 $n$을 소수로 보내면 근이 $\pm x$ 둘뿐이라 B는 늘 자기가 아는 값을 돌려받고, 그 값은 검사를 그대로 통과한다. A가 $100\%$ 이긴다. 이를 막으려면 영지식 증명(Zero-Knowledge Proof) 으로 A가 올바른 Blum 정수를 전달했음을 따로 증명해야 한다.

2. B의 $x$ 선택 편향: B는 $\gcd(x,n)=1$인 $x$를 $\mathbb{Z}_n^*$에서 균등하게 뽑아야 한다. 분포가 치우치면 A가 쌍을 더 잘 추측하고, $\gcd(x,n) \neq 1$이면 근이 넷이 아니게 되어 A가 이긴다.

3. 중단 공격: 결과를 먼저 알게 된 쪽이 프로토콜을 끝까지 따르지 않고 끊어 버릴 수 있다. 승부 자체가 성립하지 않으므로, 중단을 손해로 만드는 규칙이 프로토콜 밖에 있어야 한다.

4. 단일 비트 보장: 이 프로토콜은 한 번의 동전 던지기만 보장한다. 여러 번 반복하려면 확장이 필요하다.

---

관련 개념

Rabin 암호화: 이 프로토콜과 동일한 수학적 구조를 사용한다. 공개 키 $n = pq$로 암호화하고($c \equiv m^2 \pmod{n}$), 비밀 키 $p, q$로 복호화한다. Rabin 암호화의 보안은 소인수분해 문제와 수학적으로 동등 함이 증명되어 있다.

Blum-Blum-Shub (BBS) 난수 생성기: Blum 정수 $n = pq$와 초기값 $x_0$으로부터 $x_{i+1} = x_i^2 \pmod{n}$을 반복해 난수를 생성하는 암호학적으로 안전한 의사난수 생성기다. 이 프로토콜과 동일한 이차잉여 구조를 기반으로 한다.

출처

• Emory University Math Center — Flipping Coins on the Phone