자연 증명 장벽 — 하한 증명이 암호를 깨뜨린다
Razborov 와 Rudich 는 1980년대의 회로 하한 증명들이 구성성과 큼이라는 두 조건을 만족함을 보이고, 강한 유사난수 생성기가 있다면 그런 「자연 증명」으로는 일반 회로에 대한 초다항 하한을 얻을 수 없음을 증명했다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
Razborov 와 Rudich 는 1980년대의 회로 하한 증명들이 구성성과 큼이라는 두 조건을 만족함을 보이고, 강한 유사난수 생성기가 있다면 그런 「자연 증명」으로는 일반 회로에 대한 초다항 하한을 얻을 수 없음을 증명했다. 이 글은 그 정의와 정리, 그리고 하한 증명과 암호 사이의 긴장을 설명한다.
회로 하한은 왜 멈췄나
1980년대에 연구자들은 AC⁰, AC⁰[p] 같은 제한된 회로에 대해 강한 하한을 증명했다. 계획은 분명했다. 제한을 조금씩 풀어 가며 같은 기법을 일반 회로(P/poly)까지 넓히면 NP ⊄ P/poly, 따라서 P ≠ NP 가 나온다. 그런데 진전은 거기서 멈췄다. Razborov 와 Rudich 는 그 이유를 설명하는 정리를 내놓았다(1994년 STOC 발표, 1997년 학술지 게재).
자연 증명의 정의
n 변수 불 함수 전체를 Fₙ 이라 하자. 함수 하나는 길이 2ⁿ 인 진리표로 볼 수 있다. 불 함수의 성질 Cₙ ⊆ Fₙ 에 대해 세 조건을 생각한다.
- 구성성(constructivity)
- 함수가 그 성질을 갖는지를 진리표 크기의 다항 시간, 곧 2O(n) 시간에 판정할 수 있다.
- 큼(largeness)
- 전체 함수 가운데 적어도 2−O(n) 의 비율이 그 성질을 가진다. 무작위로 고른 함수가 무시할 수 없는 확률로 그 성질을 갖는다는 뜻이다.
- 유용성(usefulness)
- 그 성질을 가진 함수들은 다항 크기 회로로 계산할 수 없다.
구성성과 큼을 갖춘 성질(또는 그런 부분 성질을 품은 성질)을 자연 성질이라 하고, 유용한 자연 성질을 드러내든 숨기든 담고 있는 하한 증명을 자연 증명(natural proof)이라 한다.
함수 g 가 어렵다는 증명은 대개 「g 는 성질 C 를 가진다. C 를 가진 함수는 모두 어렵다」는 꼴이다. 저자들은 그때까지 알려진 비단조 회로 하한 증명이 모두 자연 증명이거나 그렇게 고쳐 쓸 수 있다고 논증했다.
예: 패리티 ∉ AC⁰ 의 증명이 쓰는 성질
예컨대 패리티 ∉ AC⁰ 의 증명들이 쓰는 성질은 「변수를 정해진 개수만 남기고 나머지를 어떻게 고정해도 함수가 상수가 되지 않는다」이다. 이 성질은 진리표로 쉽게 검사되고, 무작위 함수도 이 성질을 가진다.
정리
길이 k 인 씨앗을 길이 2k 로 늘이는 유사난수 생성기(pseudorandom generator) Gₖ : {0,1}k → {0,1}2k 의 난도 H(Gₖ) 를, Gₖ 의 출력과 진짜 무작위 문자열을 1/S 이상의 차이로 구별하는 회로의 최소 크기 S 로 정의한다.
증명된 정리 P/poly 에 대해 유용한 자연 성질이 있다면, 다항 크기 회로로 계산되는 모든 유사난수 생성기 Gₖ 에 대해 H(Gₖ) ≤ 2ko(1) 이다. 따라서 어떤 ε > 0 에 대해 난도가 2nε 인 생성기가 있다면, P/poly 에 대한 자연 증명은 없다.
증명의 뼈대는 이렇다.
- 생성기에서 Goldreich–Goldwasser–Micali 구성으로 유사난수 함수(pseudorandom function)의 족을 만든다. 씨앗 x 마다 정해지는 함수 fₓ 는 다항 크기 회로로 계산된다.
- 그러면 유용성 때문에 fₓ 는 성질 C 를 가질 수 없다.
- 반면 큼 때문에 진짜 무작위 함수는 무시할 수 없는 확률로 C 를 가진다.
- 결국 C 를 판정하는 알고리즘이 유사난수 함수와 무작위 함수를 2O(n) 크기의 회로로 구별하는 검사가 되고, 이것으로 생성기를 깰 수 있다.
하한 증명이 암호를 깨뜨린다
이 정리가 드러내는 긴장은 이렇다. 「어떤 함수는 작은 회로로 계산할 수 없다」를 자연스러운 방법으로 증명하면, 그 증명에서 「작은 회로로 계산되는 함수를 무작위 함수와 구별하는」 알고리즘이 따라 나온다. 그런데 암호학은 바로 그런 구별이 어렵다는 믿음 위에 서 있다. 저자들의 표현으로 자연 증명은 「거의 자기 파괴적(almost self-defeating)」이다. 어려움의 증명이 어려운 문제를 푸는 알고리즘을 부산물로 낳는다.
장벽이 서는 자리도 이것으로 설명된다. AC⁰ 은 유사난수 함수를 계산하기에는 너무 약해서 하한 증명이 가능했다. 임계값 게이트를 쓰는 상수 깊이 회로 TC⁰ 에는 이미 인수분해와 이산 로그의 어려움에 기초한 유사난수 함수 후보(Naor–Reingold)가 있다. 회로 하한의 진전이 멈춘 곳과 유사난수 함수가 나타나는 곳이 거의 일치한다.
Aaronson 은 여기서 P vs NP 의 개념적 어려움 하나를 읽어 낸다. 우리는 어떤 함수가 어렵다는 것을 증명하려 한다. 그런데 「주어진 함수가 어려운가」를 판정하는 문제 자체가, 우리가 증명하려는 바로 그 추측들에 따르면 어렵다. 진리표를 받아 회로 복잡도를 묻는 이 문제가 최소 회로 크기 문제(MCSP)이고, 이 관찰은 메타복잡도 연구와 맞닿아 있다.
피해 가는 길과 주의점
피해 가는 길
- 큼을 버린다. 대각선 논법은 함수 하나의 특수한 성질만 쓰므로 자연 증명이 아니다. 다만 상대화 장벽에 걸린다.
- 특수한 구조를 쓴다. 무작위 함수에는 없는 대칭성을 이용하려는 것이 기하적 복잡도 이론의 착안이다.
주의점
출처
- A. A. Razborov, S. Rudich, "Natural Proofs", J. Comput. System Sci. 55(1), 24–35 (1997); STOC 1994. 저자 공개본에서 §2(정의), §3.1(AC⁰ 하한의 자연 성질), §4(정리 4.1·4.3 과 증명)를 확인. 서지는 DOI 등록 정보(10.1006/jcss.1997.1494)로 확인.
- O. Goldreich, S. Goldwasser, S. Micali, "How to Construct Random Functions", J. ACM 33(4), 792–807 (1986). 서지는 DOI 등록 정보로 확인. Razborov·Rudich 1997 의 정리 4.1 증명이 이 구성을 쓴다.
- M. Naor, O. Reingold, "Number-Theoretic Constructions of Efficient Pseudo-Random Functions", J. ACM 51(2), 231–262 (2004). 서지는 DOI 등록 정보로, TC⁰ 에 관한 내용은 Aaronson 2017 §6.2.5 로 확인.
- S. Aaronson, "P =? NP", 저자 공개본(2017). §6.2.5(자연 증명 장벽)를 확인.
- L. Fortnow, "The Status of the P versus NP Problem", Commun. ACM 52(9), 78–86 (2009). §4.2 를 확인.
출처·이용 조건: 직접 작성
참고문헌 5
- 장벽원문 확인Natural proofsAlexander A. Razborov, Steven Rudich · 1997Journal of Computer and System Sciences 55(1), 24–35쪽 (1997) · 학회 발표 STOC 1994 (Proceedings of the 26th Annual ACM Symposium on Theory of Computing), 204–213쪽
알려진 회로 하한 증명들의 공통된 꼴을 「자연 증명」으로 정식화하고 그 한계를 보인 논문이다. 어려움에 관한 가정(강한 유사난수 생성기의 존재)이 참이라면 자연 증명으로는 일반 회로에 대한 초다항 하한을 증명할 수 없다는 둘째 장벽의 원전이다. 회로 하한 연구가 왜 막혔는지 이해하려는 독자에게 권한다. 게시자(Elsevier) 페이지로 연결된다.
확인:저자 공개본을 열어 §2(정의), §3.1, §4(정리 4.1·4.3)를 읽음. 연결한 게시자 주소의 서지는 DOI 등록 기록으로 확인. - 부분 결과서지만 확인How to Construct Random FunctionsO. Goldreich, S. Goldwasser, S. Micali · 1986Journal of the ACM 33(4), 792–807쪽 (1986) · 학회 발표 FOCS 1984, 464–479쪽
유사난수 생성기에서 유사난수 함수의 족을 만드는 구성을 제시한 논문이다. Razborov–Rudich 의 자연 증명 정리(정리 4.1)의 증명이 이 구성을 쓴다. 2-2 의 자연 증명 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 쓰임새는 Razborov–Rudich 1997 의 정리 4.1 증명으로 확인. - 부분 결과서지만 확인Number-Theoretic Constructions of Efficient Pseudo-Random FunctionsM. Naor, O. Reingold · 2004Journal of the ACM 51(2), 231–262쪽 (2004) · 학회 발표 FOCS 1997, 458–467쪽
수론 문제의 어려움에 기초해 효율적인 유사난수 함수를 구성한 논문이다. 상수 깊이 임계값 회로 TC⁰ 로 계산되는 유사난수 함수 후보의 출처다. 자연 증명 장벽이 TC⁰ 부근에서 서는 까닭을 설명할 때 2-2 의 자연 증명 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.2.5 로 확인. - 개관원문 확인P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음. - 개관원문 확인The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)
P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 인용한 절들을 읽음.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.