강의 25

상호작용 증명 시스템(Interactive Proof Systems, IP)

검증자에게 동전과 대화를 동시에 쥐여 주면

1. NP의 한계, 그리고 그 너머

NP를 다시 떠올려 보자. 검증자 V는 다항 시간 결정 TM이고, 증명자가 보낸 단 하나의 인증서 w를 읽고 수락 또는 거절한다. V는 동전도 없고 P와 두 번째 메시지를 주고받지도 않는다. 이 정적 모델은 우아하지만, 매우 경직되어 있다. SAT 같은 문제는 잘 다루지만, "어떤 조건이 성립하지 않는다"는 종류의 진술 — coNP — 에 대해서는 짧은 인증서를 일반적으로 알지 못한다.

이 강의에서 우리는 검증자에게 두 가지 새로운 자원을 동시에 준다. 첫째, 무작위 동전. 둘째, 증명자와의 다항 라운드 대화. 그 결과 클래스가 IP다. 놀랍게도 IP는 NP보다 단순히 큰 정도가 아니라, PSPACE 전체와 같다(다음 강의에서 증명). 우선 정의부터.

2. IP의 형식적 정의

정의 25.1 (상호작용 증명 시스템). 언어 L이 IP에 속한다는 것은, 다항 시간에 동작하는 확률적 검증자 V와 무한 계산 능력을 가진 증명자 P가 존재해 둘이 다항 라운드의 메시지를 주고받으며, 다음 두 조건을 만족함을 뜻한다.
  • 완전성(completeness): x ∈ L이면 어떤 P가 존재해 Pr[V가 수락] ≥ 2/3.
  • 건전성(soundness): x ∉ L이면 모든 (악의적) P̃에 대해 Pr[V가 수락] ≤ 1/3.
라운드 수와 메시지 길이는 |x|에 대해 다항.

NP의 두 변경점이 모두 결정적이다. V의 동전은 P가 모르는 무작위성을 V에게 주고, 다항 라운드의 대화는 V가 P의 답에 따라 다음 도전을 적응적으로 만들 수 있게 한다. P가 무한 능력이라는 가정 — 결국 어떤 PSPACE 문제도 풀어 줄 수 있다 — 도 핵심이다. P는 진실을 알고 있고, V는 그 진실을 검증하기만 하면 된다.

완전성/건전성의 1/3과 2/3은 BPP에서처럼 증폭으로 1 − 2−n 수준까지 끌어올릴 수 있다. 같은 프로토콜을 독립적으로 여러 번 평행 또는 직렬로 돌려 다수결을 취하면 된다. 단 평행 반복이 건전성을 항상 보존하지는 않는다는 미묘함은 다항 라운드 IP의 분석에서 중요한 주제다.

3. NP ⊆ IP는 자명하다

정리 25.2. NP ⊆ IP.
증명. L ∈ NP의 검증자 VNP를 생각하자. IP 프로토콜에서 P는 첫 라운드에 인증서 w를 보내고, V는 VNP(x, w)를 결정적으로 시뮬레이션한다. 동전을 단 한 번도 던지지 않아도 완전성 1, 건전성 0이 성립한다. 따라서 L ∈ IP.

그렇다면 IP의 진짜 위력은 어디서 오는가? coNP 같은 클래스에서 온다. 다음 절의 예제는 IP가 단순히 NP를 흉내 내는 것이 아니라, 짧은 인증서가 알려져 있지 않은 문제까지 검증할 수 있음을 보여 주는 고전이다.

4. 그래프 비동형성 ∈ IP

두 그래프 G1 = (V, E1), G2 = (V, E2)가 주어졌을 때 동형이 아니라는 것을 어떻게 짧게 증명할 것인가? 동형이라는 사실에는 짧은 인증서(순열)가 있지만, 동형이 아니라는 사실에는 자연스러운 짧은 인증서가 없다. 그러나 다음 IP 프로토콜은 단 두 라운드로 GNI를 검증한다.

정리 25.3. GRAPH NON-ISOMORPHISM ∈ IP.
프로토콜.
  1. V의 도전. V는 b ∈ {1, 2}를 균등하게 무작위로 뽑고, 정점 순열 π를 균등하게 무작위로 뽑은 뒤 H = π(Gb)를 P에게 보낸다.
  2. P의 답. P는 H가 G1과 G2 중 어느 쪽에서 만들어졌는지 추측해 b' ∈ {1, 2}를 보낸다.
  3. V의 결정. b = b'이면 V가 수락, 아니면 거절.

완전성. G1 ≇ G2이면 H의 동형류는 Gb의 동형류와 같다. 무한 능력의 P는 H의 동형류를 결정해 b를 정확히 맞힌다. 따라서 Pr[수락] = 1.

건전성. G1 ≅ G2이면 H의 분포는 b의 값과 무관하게 같다 — π가 균등 순열이고 G1 ≅ G2면 π(G1)의 분포 = π(G2)의 분포. P̃는 H만 보고 b를 정보 이론적으로 알 수 없으므로 어떤 전략으로도 Pr[b = b'] ≤ 1/2.

건전성 1/2은 우리 정의의 1/3을 살짝 넘지만, 두 번 독립 시행 후 둘 다 맞을 때만 수락하면 1/4로 떨어진다. 적당한 반복으로 1/3 이하 보장.

5. 왜 무작위성이 핵심인가

위 프로토콜에서 V의 동전 b와 π를 P가 미리 알고 있다고 상상해 보자. 그러면 P는 H를 받기도 전에 b'를 정확히 답할 수 있다. 건전성은 즉시 무너진다. 즉 V의 동전이 P에게 비밀로 남아 있어야만 P가 속이지 못한다. 이런 의미에서 IP에서 무작위성은 단순한 효율 도구가 아니라 안전 메커니즘이다.

또 다른 시각으로 말하자면, V의 동전은 P를 시험하기 위한 동적 도전을 무한히 생성하는 엔진이다. 정적 NP 인증서가 한 번의 시험이라면, IP는 P를 매번 새로운 무작위 도전 앞에 세우는 면접관의 역할을 V에게 부여한다.

6. Arthur–Merlin과 공개 동전 모델

IP의 동전은 V에게 비밀이다. 동전을 모두 공개하는 변종 — 공개 동전 모델 — 도 자연스러운 정의를 낳는다. 이를 Arthur–Merlin 게임이라 한다. Arthur(V)가 매 라운드 동전을 던져 그 결과를 그대로 메시지로 보내고, Merlin(P)이 응답한다.

정의 25.4. AM[k]는 Arthur–Merlin 프로토콜에서 k 라운드를 사용하는 클래스다. 가장 중요한 두 사례:
  • MA = Merlin이 먼저, Arthur가 나중. 사실상 NP에 무작위 V를 결합한 형태.
  • AM = Arthur가 먼저(동전을 보냄), Merlin이 나중. AM[2].
정리 25.5 (Goldwasser–Sipser, 1986). IP[k] ⊆ AM[k+2]. 따라서 다항 라운드에 대한 IP와 AM은 동치이며, 비밀 동전 모델은 공개 동전 모델로 효율 손실 없이 환원될 수 있다.

이 정리의 직관: V가 비밀 동전을 사용한다면, V는 동전 시퀀스의 분포가 자기 메시지에 대해 충분히 균등함을 P에게 통계적으로 증명할 수 있다. 비밀스러움은 전체 클래스의 표현력에 영향을 주지 않는, 다소 외형적인 차이임이 드러난다. 단, 라운드 수가 상수일 때는 AM[k]의 위계가 특정 깊이에서 무너진다 — AM[2] = AM[k] for any constant k ≥ 2 — 라는 부수적 사실도 유명하다.

Goldwasser와 Sipser의 결과는 직관에 반한다. "V가 동전을 숨기는 것이 P를 속이지 못하게 하는 핵심"이라고 우리가 5절에서 강조했는데, 정리 25.5는 그 비밀스러움을 그냥 포기해도 클래스 자체는 안 변한다고 말한다. 차이는 프로토콜 설계의 우아함에 있을 뿐, 표현력에 있지 않다는 것이다.

7. 다음 강의 예고

지금까지 우리는 IP의 정의와 첫 비자명한 거주민 GNI를 보았다. 다음 강의에서 우리는 더 야심찬 목표 — coNP ⊆ IP — 을 LFKN의 산술화 기법과 SUM-CHECK 프로토콜로 직접 증명한다. 그리고 이 기법이 전부 PSPACE까지 확장될 때 IP = PSPACE라는 1992년의 대정리에 도달한다. NP의 좁은 정적 모델을 떠난 우리는, 검증의 한계가 사실은 PSPACE만큼 멀다는 것을 보게 된다.