영지식 증명 — 정보를 공개하지 않고도 '진실'임을 증명하는 마법

왜 알아야 하나

로그인할 때 우리는 비밀번호를 서버로 보낸다. 서버가 그것을 저장된 값과 맞춰 보고 "맞다"고 판정하기 위해서다. 여기에는 아주 오래된 전제가 하나 깔려 있다. 확인시켜 주려면 알려줘야 한다.

이 전제는 일상 곳곳에 있다. 술을 사려면 신분증을 내밀어야 하고, 신분증에는 생년월일뿐 아니라 이름·주소·번호가 함께 적혀 있다. 대출 심사를 받으려면 소득 자료를 통째로 넘겨야 한다. 상대가 알아야 할 것은 "이 사람이 19세 이상인가", "이 사람의 소득이 기준을 넘는가" 하나뿐인데, 우리가 넘기는 것은 그 판단의 재료 전부다.

문제는 넘겨진 데이터가 그 자리에서 사라지지 않는다는 데 있다. 저장되고, 복제되고, 유출된다. 비밀번호를 서버로 보내는 방식 자체가 유출 지점을 하나 만든다는 문제의식에서, 청구자와 검증자 사이에 직접적인 정보 교환 없이 인증을 끝내려는 시도가 나왔다. 한 제안은 계산 대부분을 사용자 브라우저에서 수행하고 비밀번호를 어느 시점에도 서버에 드러내지 않는 구조를 취한다 (arXiv:1911.09329 — 동료심사 전 프리프린트).

이 발상을 일반화한 것이 영지식 증명(zero-knowledge proof, ZKP)이다. 증명자가 어떤 비밀값을 알고 있다는 사실을 검증자에게 납득시키되, 그 비밀 자체에 대해서는 아무것도 드러내지 않는 암호학적 장치다 (arXiv:2502.07063 — 동료심사 전 프리프린트).

제목에 '마법'이라 썼지만 먼저 정직하게 못 박아 두자. 마법이 아니다. 영지식 증명은 확률과 계산 가정 위에 세워진 공학이다. 검증에는 작지만 0이 아닌 실패 확률이 남고, 안전성은 "이 계산 문제는 현실적 시간 안에 풀리지 않는다"는 가정에 기대며, 그 가정이 바뀌면 결론도 바뀐다. 이 글의 목표는 그 구조를 입문자 눈높이에서 세워 두는 것이다.

큰 그림 — '증명'을 다시 정의하기

영지식 증명을 이해하려면 먼저 증명이라는 말 자체가 확장되었다는 사실부터 받아들여야 한다.

전통적으로 증명은 정적인 대상이다. 종이에 적힌 논증을 한 단계씩 따라가며 옳은지 확인한다. 1980년대에 등장한 대화형 증명(interactive proof)은 여기에 두 가지를 더했다. 증명자와 검증자 사이의 상호작용, 그리고 작지만 0이 아닌 오류 확률 — 잘못된 증명이 검증을 통과할 가능성을 완전히 배제하지는 않는다는 것이다. 나아가 논증(argument)은 거짓 명제의 '증명'이 존재하는 것까지 허용한다. 단, 그것을 찾으려면 감당할 수 없는 계산력이 필요하다는 조건 아래서다. 종이에 다 쓰는 대신 대화로 서로를 납득시키는 수학자들의 방식을 흉내 낸 셈이다. 그리고 원리적으로 어떤 논증이든 영지식으로 바꿀 수 있다 — 증명이 자신의 유효성 외에는 아무것도 드러내지 않게 만들 수 있다는 뜻이다 (DOI: 10.1561/3300000030).

이 확장의 밑바닥에는 더 근본적인 관점 전환이 있다. 무작위성이든 증명이든, 그것을 '이상적 실체'가 아니라 관찰자의 능력에 상대적인 것으로 보자는 관점이다. 두 확률분포가 효율적인 절차로는 구별되지 않는다면 그 둘은 같은 것으로 취급한다. 이 관점 위에서 비로소 영지식 증명 — "주장이 참이라는 사실 외에는 아무것도 내주지 않는 설득력 있는 논증" — 이라는 개념이 성립한다 (DOI: 10.1093/oso/9780198537748.003.0016).

등장인물은 둘이다. 증명자(prover)는 비밀을 아는 쪽, 검증자(verifier)는 그것을 확인하려는 쪽이다. 앞으로 나올 모든 이야기는 이 둘 사이에서 벌어진다.

이 지점에서 흔히 쓰이는 비유가 있다. 두 갈래로 갈라졌다가 안쪽에서 이어지는 동굴, 그 이음매에 잠긴 문이 있고 증명자만 열쇠를 안다는 '알리바바 동굴' 이야기. 또는 색맹인 친구 앞에서 색만 다른 두 공을 섞고 안 섞고를 반복해 "둘이 다르다"를 납득시키는 이야기. 이것들은 비유다. 직관을 주기는 하지만 실제 프로토콜은 아니며, 비유만 붙들고 있으면 정작 정의를 놓친다. 교과서적으로 가장 먼저 다뤄지는 실제 예시는 그래프 동형(graph isomorphism) 문제 위의 프로토콜이고, 증명자·검증자·시뮬레이터·영지식이라는 용어가 무엇을 뜻하는지는 이 구체적 예시를 통해 익히는 것이 정석이다 (DOI: 10.59350/5bt3p-h4h88 — 학술지 논문이 아니라 입문 해설 글).

세 가지 조건

영지식 증명 프로토콜이 갖춰야 할 성질은 셋으로 정리된다 (DOI: 10.30837/rt.2025.3.222.05).

• 완전성(completeness) — 명제가 참이고 증명자가 정직하다면, 검증자는 납득한다.
• 건전성(soundness) — 명제가 거짓이라면, 부정직한 증명자가 검증자를 속일 확률이 아주 작다.
• 영지식성(zero-knowledge) — 검증자는 "명제가 참이다"라는 사실 외에는 아무것도 얻지 못한다.

앞의 둘은 직관적이다. 문제는 셋째다. "아무것도 얻지 못한다"를 어떻게 수학적으로 정의할 것인가. 얻은 것이 없다는 것을 대체 어떻게 증명하는가.

시뮬레이터 — 이 글의 심장

해법은 문제를 뒤집는 것이다. 검증자가 프로토콜을 돌리며 본 것 전부 — 주고받은 메시지와 자기가 뽑은 난수, 이것을 뷰(view)라 한다 — 를, 비밀을 전혀 모르는 제3자가 혼자서도 똑같이 만들어낼 수 있다면, 검증자는 새로 안 것이 하나도 없는 셈이다. 이미 가진 재료만으로 재현되는 것에서는 아무것도 배울 수 없기 때문이다.

이 가상의 제3자를 시뮬레이터(simulator)라 부른다. 영지식성의 정의는 이렇게 된다. "어떤 검증자에 대해서든, 비밀 없이 그 뷰를 만들어내는 효율적인 시뮬레이터가 존재한다."

정의가 추상적으로 들린다면, 실제 논문에서 어떻게 쓰이는지를 보면 감이 잡힌다. 분산 환경의 영지식을 다룬 한 연구는 각 노드의 뷰가 무시할 만한 통계적 거리 안에서 시뮬레이션 가능할 것을 요구하는 방식으로 '분산 통계적 영지식'을 정의한다 (arXiv:2605.14015 — 동료심사 전 프리프린트). 확률적 검사 증명(PCP)에 영지식을 얹은 연구도 마찬가지로, 악의적일 수 있는 검증자의 뷰가 작은 통계적 거리까지 효율적으로 시뮬레이션될 수 있음을 보장 조건으로 삼는다 (DOI: 10.3390/e24070970).

"통계적 거리 안에서"라는 단서에 주목하자. 여기서 영지식성의 등급이 갈린다. 뷰가 완전히 똑같으면 완전(perfect) 영지식, 통계적으로 구별 불가능하면 통계적(statistical) 영지식, 효율적 계산으로 구별 불가능하면 계산적(computational) 영지식이다 (DOI: 10.1155/2014/560484). 논문에서 "zero-knowledge"라는 단어를 만나면 어느 등급인지 확인하는 습관이 필요하다. 등급이 다르면 보장의 강도가 다르다.

시뮬레이터라는 개념 자체가 이 분야의 난이도도 결정한다. 시뮬레이터가 검증자를 블랙박스로만 다룰 수 있는지에 따라 무엇이 가능한지가 갈리며, 이 구분이 영지식의 정의와 보안 증명의 토대를 이룬다. 완전 양자 환경에서 상수 라운드 블랙박스 시뮬레이션 영지식이 사실상 불가능하다는 결과는, 왜 비블랙박스 시뮬레이션 기법이나 완화된 보안 개념이 필요한지를 거꾸로 정당화한다 (arXiv:2409.06317 — 동료심사 전 프리프린트).

기본 용어와 원리

도전-응답, 그리고 반복

가장 널리 쓰이는 대화형 구조는 3단계다. 이산로그 문제 위에 세워진 Schnorr 프로토콜이 교과서적 예다. 증명자가 먼저 커밋먼트(commitment) — 나중에 바꿔치기할 수 없도록 값을 봉인해 보내는 장치 — 를 보낸다. 검증자는 무작위 도전(challenge)을 되돌려 보낸다. 증명자가 응답(response)을 만든다. 검증자는 이 응답만으로 증명의 유효성을 확인할 수 있고, 그 과정에서 밑에 깔린 비밀은 알지 못한다 (DOI: 10.54254/2753-8818/14/20240870). 이 3단계 구조를 시그마(Σ) 프로토콜이라 부른다.

무작위 도전이 핵심이다. 도전이 무작위이므로 증명자는 답을 미리 준비해 둘 수 없다. 비밀을 모르는 사기꾼은 특정 도전 하나만 골라 대비할 수 있고, 다른 도전이 오면 걸린다. 한 번의 시행에서 요행이 통할 확률이 남더라도 같은 절차를 여러 번 반복하면 매번 통과할 확률은 급격히 작아진다. 건전성은 절대적 차단이 아니라 확률의 문제이며, 반복은 그 확률을 낮추는 손잡이다.

다만 "반복하면 그만"이라고 넘기기에는 미묘한 지점이 있다. 오류를 줄이려고 여러 시행을 병렬로 붙이면 영지식성이 함께 유지되지 않을 수 있다. 블랙박스 시뮬레이터를 가진 프로토콜에서는 이런 병렬 합성이 어렵다는 고전적 결과가 있고, 양자 시뮬레이터 설정으로도 일반화되어 있다 (arXiv:quant-ph/0607211 — 동료심사 전 프리프린트). 건전성과 영지식성은 공짜로 함께 가지 않는다.

지식의 증명과 추출기

"명제가 참이다"를 보이는 것과 "나는 그 답을 알고 있다"를 보이는 것은 다르다. 후자를 지식의 증명(proof of knowledge)이라 한다. 정의는 시뮬레이터와 쌍둥이처럼 생겼다. 증명자를 되감아 여러 번 돌려 보면서 그 안에서 실제 비밀을 뽑아낼 수 있는(extract) 절차 — 추출기(extractor) — 가 존재한다면, 그 증명자는 정말로 비밀을 알고 있다고 봐야 한다. 이때 추출이 실패할 여지를 지식 오류(knowledge error)라 부르며, 최신 이론 연구의 상당 부분이 이 값을 얼마나 작게 유지할 수 있는지, 그리고 추출기를 어떤 표집 방식으로 구성할지를 다룬다 (DOI: 10.1007/s00145-025-09569-y).

대화형에서 비대화형으로 — Fiat–Shamir

대화형 프로토콜에는 실무적 불편이 있다. 검증자가 실시간으로 도전을 보내 줘야 한다. 서명이나 블록체인처럼 "한 번 만들어 두면 아무나 나중에 검증"해야 하는 상황에는 맞지 않는다.

여기서 등장하는 것이 Fiat–Shamir 변환이다. 발상은 대담할 만큼 단순하다. 검증자가 보내야 할 무작위 도전을, 지금까지의 대화 내용을 해시 함수에 넣어 얻은 값으로 대체하는 것이다. 증명자가 혼자 도전을 만들어 쓰지만 해시 결과를 마음대로 조종할 수 없으므로 무작위 도전과 비슷한 효과를 낸다 (DOI: 10.54254/2753-8818/14/20240870).

이 변환은 임의의 공개 동전(public-coin) 대화형 증명을 비대화형으로 바꾸며, 랜덤 오라클 모델 아래서 원래의 주요 보안 성질을 물려받는다. 원래는 3-메시지 시그마 프로토콜을 대상으로 고안되었으나 지금은 다중 라운드 프로토콜에도 적용된다 — 그리고 여기서 대가가 발생한다. 일반적으로 (2μ+1)-메시지 프로토콜의 보안 손실은 대략 Q^μ (Q는 공격자의 오라클 질의 횟수) 규모로 커진다. 다행히 special-sound라 불리는 넓은 부류에 대해서는 손실이 Q에 선형으로만 커진다는 것이 증명되어 있다 (DOI: 10.1007/s00145-023-09478-y). "Fiat–Shamir를 붙였다"는 문장 뒤에는 이런 조건들이 숨어 있다.

이렇게 얻어진 것이 비대화형 영지식 증명(NIZK)이다. 증명자가 검증자에게 보내는 메시지가 단 하나뿐인 형태로, 낮은 상호작용 복잡도 덕분에 각종 암호 프로토콜의 부품으로 널리 쓰인다 (DOI: 10.1155/2014/560484).

무엇을 증명할 수 있고, 무엇에 기대고 있나

영지식 증명은 특정 문제 전용 트릭이 아니다. NP에 속하는 명제라면 원리적으로 다룰 수 있고, 실제로 NP 문제에 대한 비대화형 영지식 증명이 오래 연구되어 왔다 (DOI: 10.1155/2014/560484). 1980년대에 나온 Goldreich–Micali–Wigderson 프로토콜은 그래프 색칠 문제 위에서 이 일반성을 보인 대표적 구성이며, 오늘날에도 서명 스킴의 출발점으로 변형·확장된다 (arXiv:2602.02689 — 동료심사 전 프리프린트).

그 대신 이 모든 것은 계산복잡도 가정 위에 서 있다. 계산은 쉽지만 역산은 어려운 함수 — 일방향 함수 — 가 존재한다는 가정이 현대 암호학의 토대이며, 영지식 대화형 증명도 그 위에 놓인 구조물이다 (arXiv:cs/0111056 — 동료심사 전 프리프린트; arXiv:cs/0212055 — 동료심사 전 프리프린트). 실제 구현에서 쓰이는 재료는 이산로그 증명, 동형 암호, 다항식 커밋먼트, 해시 함수, 타원곡선 등이다 (DOI: 10.30837/rt.2025.3.222.05).

가정 선택이 어긋나면 프로토콜도 무너진다. 좋은 예가 앞서 개념 설명에 썼던 그래프 동형이다. 가르치기에는 이상적이지만, 실제 그래프 동형 문제는 많은 유형의 그래프에서 쉽게 풀려 버려 실용적 영지식 인증의 기반으로는 적절하지 않다는 분석이 있다 (DOI: 10.12794/metadc12076 — 학위논문). 개념을 보여 주는 예시와 실전에서 안전한 기반은 다르다.

실제로 어떻게 나타나나

간결성, 그리고 트레이드오프의 축

실무를 지배하는 성질은 간결성(succinctness)이다. 증명의 크기와 검증 시간이 원래 비밀(witness)의 크기보다 훨씬 작다는 뜻이다. 이 성질 덕분에 계산 아웃소싱, 익명 자격증명, 서명 집계, 블록체인 프로토콜 같은 응용이 열렸다 (DOI: 10.20868/upm.thesis.91808 — 박사학위논문).

zk-SNARK, zk-STARK, Bulletproofs 같은 이름들이 여기서 나온다. 이들을 "무엇이 더 빠른가"로 줄 세우려는 충동은 참는 편이 좋다. 이 계열들을 비교하는 축은 성능 숫자 하나가 아니라 증명 크기, 증명자 시간, 검증자 시간, 메모리, 그리고 셋업 가정이라는 여러 개이기 때문이다 (arXiv:2408.00243 — 동료심사 전 프리프린트).

축들이 실제로 어떻게 어긋나는지 한 실측 비교가 보여 준다. 소비자용 ARM 플랫폼에서 공개 참조 구현을 돌린 결과, zk-SNARK(Groth16)는 증명을 더 빠르게 생성하고 증명 크기도 더 작았지만 검증은 더 느렸고 신뢰 셋업을 필요로 했다. 반대로 zk-STARK는 증명이 크고 생성이 느렸지만 검증이 빨랐으며, 투명(셋업 불필요)하고 양자후 보안을 지향한다 (arXiv:2512.10020 — 동료심사 전 프리프린트).

여기서 중요한 경고 하나. 이런 결과를 일반적 서열로 읽으면 안 된다. 2015년부터 2023년 4월까지 41편을 체계적으로 검토한 연구는, 같은 계열 프로토콜이라도 실세계 성능이 구현에 따라 최대 수 자릿수까지 차이 났으며 보안 분석 방법론이 제각각이라 결정적 비교 자체가 불가능했다고 보고한다. 공통 벤치마크를 세우는 일이 향후 과제로 남아 있다 (DOI: 10.1002/spy2.401). 이 분야에서 성능 수치는 프로토콜의 성질이라기보다 구현과 실험 조건의 성질에 가깝다. 논문에서 "우리 방식이 N% 빠르다"를 만나면 그 N보다 실험 조건을 먼저 보라.

신뢰 셋업이라는 갈림길

가장 효율이 좋은 zk-SNARK들은 일회성 신뢰 셋업(trusted setup)에 의존한다. 시스템을 띄우기 전에 공개 파라미터 — 흔히 'Powers of Tau' 문자열 — 를 만들어야 하는데, 이때 쓰인 비밀값 τ가 유출되면 공격자가 거짓 증명을 만들어낼 수 있다. 그 문자열 위에 세워진 모든 zk-SNARK 시스템의 건전성이 한꺼번에 무너진다는 뜻이다. 그래서 여러 참여자가 무작위성을 나눠 기여하는 탈중앙 세리머니가 고안되었고, 그 참여 비용을 낮추는 것 자체가 연구 주제다 (arXiv:2503.04549 — 동료심사 전 프리프린트).

대안은 셋업이 필요 없는 투명(transparent) 계열이다. 대가는 효율이다. 투명 argument 시스템은 역사적으로 비효율적이었고 신뢰 셋업 계열에 비해 증명 크기가 컸다 (DOI: 10.62056/anudy76bm). 이 격차를 좁히는 것이 현재 진행형 연구다. 요컨대 셋업 문제는 "해결됐다/안 됐다"가 아니라 무엇을 내주고 무엇을 얻을 것인가의 문제다.

어디에 쓰이나

• 블록체인 프라이버시. Zcash의 프라이버시 보장은 zk-SNARK 구성 위에 통째로 얹혀 있다 (arXiv:2008.00881 — 동료심사 전 프리프린트).
• 확장(zk-롤업). 거래를 메인 체인 밖에서 처리하고 증명만 올리는 방식이다. 다만 이 시스템들의 성능은 결국 밑에 깔린 ZKP 메커니즘의 효율에 발목을 잡힌다 (arXiv:2503.22709 — 동료심사 전 프리프린트).
• 신원·자격증명. 신뢰받는 발급자가 준 자격증명에 대해, 내용을 검증자에게 전혀 드러내지 않고 명제만 증명한다 (arXiv:1907.09579 — 동료심사 전 프리프린트). zk-STARK 기반으로 "나이가 18세 이상"만 증명하는 프레임워크도 제안되었다 (arXiv:2510.09715 — 동료심사 전 프리프린트). 글머리의 신분증 문제에 정확히 대응하는 방향이다.
• 전자투표. 무거운 집계 계산을 체인 밖으로 옮기고 그 정확성을 zk-SNARK로 검증해, 확장성을 얻으면서도 분쟁 없는 성질을 유지하는 설계가 제안되었다 (arXiv:2203.03363 — 동료심사 전 프리프린트).
• 검증가능 머신러닝(ZKML). 학습·추론·테스트가 주장된 대로 수행되었음을, 데이터나 모델 파라미터를 드러내지 않고 증명하려는 시도다 (DOI: 10.1007/s10462-026-11557-y).
• 블록체인 바깥. 핵군축 검증에 커밋먼트와 zkSNARK를 결합해, 침습적 물리 사찰 없이 조약 제약 준수를 확인하되 탄두의 민감 정보는 비밀로 유지하는 프로토콜이 제안되었다 (arXiv:2507.20074 — 동료심사 전 프리프린트).
• 카드 한 벌로도. 컴퓨터 없이 물리적 도구만으로 퍼즐의 해답을 안다는 사실을 증명하는 프로토콜이 여럿 설계되어 있다 (DOI: 10.1007/s00354-024-00267-0; arXiv:2603.01393 — 동료심사 전 프리프린트). 영지식이 특정 기술이 아니라 아이디어임을 보여 주는 예다.

여기서 실증과 제안을 반드시 구분해야 한다. 블록체인 프라이버시와 롤업은 실제로 배포되어 돌아가는 시스템이 있다. 반면 검증가능 머신러닝은 회로 표현력의 한계, 높은 증명 생성 비용, 배포 복잡성이 여전히 주된 병목으로 남은 발전 중인 영역이며 (arXiv:2502.18535 — 동료심사 전 프리프린트), 핵군축 검증은 설계 제안 단계다. 논문 제목의 시제와 실제 배포 상태는 다른 이야기다.

흔한 오해

오해 1 — "영지식이면 익명이다." 아니다. 영지식 증명은 증명 안에 담긴 내용을 가릴 뿐, 그 증명을 누가 언제 어디서 제출했는지까지 가려 주지 않는다. 퍼미션리스 블록체인의 프라이버시 위험을 정리한 연구는 거래 연결(transaction linking), 거래 메타데이터, 온체인 데이터 분석, RPC 노드 같은 내용과 무관한 경로들을 나열하며, 영지식 증명·링서명·스텔스 주소를 그중 일부에 대한 해법으로 배치한다 (arXiv:2305.01038 — 동료심사 전 프리프린트). 블록체인의 프라이버시는 아직 믿고 맡길 수준이 되려면 갈 길이 멀다는 것이 문헌 검토의 진단이다 (arXiv:1809.10642 — 동료심사 전 프리프린트).

거꾸로, 익명성이 지나쳐도 문제가 된다. 인증 없이 계정을 여럿 만들어 활동을 흐릴 수 있는 완전 익명 계정 시스템은 사람과 계정의 대응을 알 수 없게 만든다 (arXiv:2301.02102 — 동료심사 전 프리프린트). 프라이버시와 책임성은 별개의 축이며, 영지식 증명은 그중 한 축을 다루는 도구일 뿐이다.

오해 2 — "수학적으로 증명됐으니 안전하다." 많은 사람이 SNARK를 "그냥 수학"으로 여긴다. 증명된 것은 실무에서도 옳다는 전제다. 실제 구현의 취약점 141건을 수집해 분류한 연구는 그 전제를 정면으로 반박한다 (arXiv:2402.15293 — 동료심사 전 프리프린트). 회로 구현 쪽도 마찬가지여서, 널리 쓰이는 라이브러리에 퍼징을 붙이자 개발자가 확인한 신규 버그 10건이 나왔고 (arXiv:2504.14881 — 동료심사 전 프리프린트), 실제 배포된 zk-롤업에서는 최종화 실패를 일으키는 제로데이 버그 12건이 발견되어 수정되었다 (arXiv:2410.12210 — 동료심사 전 프리프린트).

간극은 우연이 아니라 구조적이다. 40편 이상의 zk-SNARK 스킴과 11개 범용 라이브러리를 함께 조사한 연구는, 학계의 관심이 증명 시스템에 쏠려 있는 반면 산업 현장의 병목은 제약 시스템(constraint system) 쪽에 있다고 진단한다 (arXiv:2502.02387 — 동료심사 전 프리프린트). 종이 위의 정리, 컴파일된 회로, 배포된 코드 — 이 셋 사이에는 언제나 틈이 있다.

오해 3 — "신뢰 셋업은 형식적 절차다." 앞서 본 대로 셋업 비밀이 유출되면 가짜 증명이 가능해진다 (arXiv:2503.04549 — 동료심사 전 프리프린트). "누가 셋업을 했고 그 비밀이 정말 폐기되었는가"는 프로토콜 밖의 사회적 신뢰 문제다. 투명 계열은 바로 이 문제를 없애는 대신 효율을 내준다 (DOI: 10.62056/anudy76bm). 어떤 시스템을 평가할 때 "신뢰 셋업이 있는가"는 성능 표보다 먼저 확인할 항목이다.

오해 4 — "증명이 짧으니 싸다." 검증이 싼 것과 증명이 싼 것은 완전히 다른 이야기다. 증명 생성은 여전히 비싸며, 다중 스칼라 곱셈(MSM)이나 수론적 변환(NTT) 같은 연산이 실행 시간을 지배한다 (arXiv:2604.17808 — 동료심사 전 프리프린트). 애초에 "증명자가 다항 시간 안에 돌 수 있는가"는 자명한 조건이 아니라 별도로 요구해야 하는 성질이며, 증명자가 다항 시간이고 검증자가 거의 선형 시간일 때에야 현실의 계산 주체가 대화형 증명의 이점을 실제로 누릴 수 있다 (DOI: 10.1561/0400000084). 검증가능 머신러닝에서 높은 증명 비용이 대표적 병목으로 꼽히는 것도 같은 이유다 (arXiv:2502.18535 — 동료심사 전 프리프린트).

오해 5 — "양자컴퓨터 이야기는 다 같은 이야기다." 계열마다 다르다. 타원곡선·이산로그 가정에 기댄 계열과 해시 함수에 기댄 계열은 양자 위협 앞에서 처지가 다르며, zk-STARK 계열이 투명성과 함께 양자후 보안을 내세우는 것도 이 차이 때문이다 (arXiv:2512.10020 — 동료심사 전 프리프린트). 양자 취약 가능성은 이 분야의 주요 과제 목록에 이미 올라 있다 (DOI: 10.30837/rt.2025.3.222.05).

다만 "양자컴퓨터가 오면 다 깨진다"는 단순화도 틀렸다. Fiat–Shamir 변환을 예로 들면, 2013년의 한 연구는 양자 랜덤 오라클 모델에서 이 변환의 보안 증명이 어려워 보인다며 블랙박스 추출기가 존재할 수 없음을 보였다 (arXiv:1306.0315 — 동료심사 전 프리프린트). 그러나 2019년의 후속 연구는 일반적 환원을 제시해 건전성과 지식증명 성질이 양자 공격 아래서도 보존됨을 보였고, 문헌에 있던 일부 주장이 틀렸음을 함께 지적했다 (arXiv:1902.07556 — 동료심사 전 프리프린트). 결론은 하나다. 모델과 가정이 바뀌면 결론도 바뀐다. "양자에 안전한가"는 예/아니오가 아니라 "어느 모델에서, 어떤 가정 아래"라는 질문이다.

한 가지 정직하게 덧붙이자면, 이 글이 근거로 삼은 문헌은 개념·서베이·구현 분석에 치우쳐 있다. 사이드채널이나 구현 최적화 과정에서 새로 생기는 누출처럼, 이론 문헌이 잘 다루지 않는 위험이 실무에는 더 있다. 여기서 다룬 목록이 위험의 전부는 아니라는 뜻이다.

더 깊이 가려면

여기까지가 이 분야의 논문을 펼치기 위한 최소 토대다. 세 문장으로 압축하면 이렇다. 첫째, 영지식 증명은 '증명'이라는 개념을 상호작용과 확률로 확장한 결과물이며, 마법이 아니라 계산 가정 위의 공학이다. 둘째, 그 핵심 정의는 시뮬레이터다 — 비밀 없이도 검증자의 뷰를 만들어낼 수 있다면 검증자는 아무것도 새로 알지 못한 것이다. 셋째, 실무의 선택은 성능 서열이 아니라 셋업 가정·증명 크기·증명자 비용·보안 가정이라는 여러 축의 트레이드오프다.

다음에 읽을 것을 갈래별로 남긴다.

• 전체 지형: 대화형 증명부터 영지식 논증까지 다섯 갈래 접근법을 하나의 틀로 묶은 서베이 (DOI: 10.1561/3300000030). 개념의 출발점을 보려면 1990년의 고전 서베이 (DOI: 10.1093/oso/9780198537748.003.0016).
• 응용을 훑고 싶다면: 블록체인 안팎의 활용을 분류하고 비교표를 제공하는 서베이 (arXiv:2408.00243 — 동료심사 전 프리프린트). 비대화형 계열의 이론적 지형은 (DOI: 10.1155/2014/560484).
• 직접 만들어 보고 싶다면: 25개 범용 프레임워크를 실측 비교하고 실행 환경까지 공개한 조사 (arXiv:2502.07063 — 동료심사 전 프리프린트), 사전 지식 없이 zk-SNARK의 내부를 따라가는 해설 (arXiv:1906.07221 — 동료심사 전 프리프린트).
• 안전하게 쓰고 싶다면: 실제 취약점 141건의 분류 (arXiv:2402.15293 — 동료심사 전 프리프린트), 이론과 실무의 간극 정리 (arXiv:2502.02387 — 동료심사 전 프리프린트).
• 이론으로 더 들어가려면: 검증가능 계산의 이론적 기초를 128편으로 정리한 리포트 (arXiv:2308.15191 — 동료심사 전 프리프린트).

마지막으로 습관 하나. 이 분야의 논문을 열면 성능 표보다 먼저 다섯 가지 전제를 찾아라. ① 대화형인가 비대화형인가. ② 셋업은 신뢰형인가 투명형인가. ③ 영지식성은 완전인가 통계적인가 계산적인가. ④ 어떤 계산 가정 위에 서 있는가(이산로그·격자·해시). ⑤ 적대자는 고전인가 양자인가. 이 다섯 답을 확인하고 나면 뒤에 이어지는 정리와 실험이 무엇에 관한 주장인지 또렷해진다. 숫자를 비교하기 전에 전제를 비교하는 것 — 그것이 이 분야를 읽는 사람과 결론만 옮기는 사람을 가른다.

---

근거 논문

• "Proofs, Arguments, and Zero-Knowledge," Foundations and Trends in Privacy and Security (2022) — DOI: 10.1561/3300000030 — 대화형 증명·논증의 개념적 확장(상호작용 + 0이 아닌 오류 확률), 어떤 논증이든 원리적으로 영지식으로 변환 가능. 다섯 접근법의 통합 서베이.
• "Randomness, Interactive Proofs, and Zero-Knowledge - A Survey," The Universal Turing Machine: A Half-Century Survey (1990) — DOI: 10.1093/oso/9780198537748.003.0016 — 무작위성·증명을 관찰자의 능력에 상대적인 개념으로 재정의. 영지식 = 주장의 유효성 외에는 아무것도 내주지 않는 설득력 있는 논증.
• "Zero Knowledge Proofs — A Primer" (2016) — DOI: 10.59350/5bt3p-h4h88 — 그래프 동형 문제로 증명자·검증자·시뮬레이터·영지식 용어를 익히는 입문 해설. 학술지 논문이 아닌 해설 글.
• "Zero-knowledge proof protocols: theoretical foundations and applications in modern cryptography," Radiotekhnika (2025) — DOI: 10.30837/rt.2025.3.222.05 — 완전성·건전성·영지식성, 대화형/비대화형 분류, 수학적 재료(이산로그·다항식 커밋먼트·타원곡선), 과제(확장성·신뢰 셋업·양자).
• "Distributed Statistical Zero-Knowledge Proofs via Sumcheck" (2026) — arXiv:2605.14015 — 각 노드의 뷰가 무시할 만한 통계적 거리 안에서 시뮬레이션 가능할 것을 요구하는 분산 통계적 영지식 정의. 동료심사 전 프리프린트.
• "Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience," Entropy (2022) — DOI: 10.3390/e24070970 — 악의적 검증자의 뷰가 작은 통계적 거리까지 효율적으로 시뮬레이션 가능해야 한다는 ZK-PCP의 보장 조건.
• "The Black-Box Simulation Barrier Persists in a Fully Quantum World" (2024) — arXiv:2409.06317 — 시뮬레이션이 영지식 정의·보안 증명의 토대. 완전 양자 환경의 상수 라운드 블랙박스 시뮬레이션 영지식 불가능성. 동료심사 전 프리프린트.
• "Examining Schnorr's protocol in the context of zero-knowledge proofs," Theoretical and Natural Science (2023) — DOI: 10.54254/2753-8818/14/20240870 — 커밋먼트 → 무작위 도전 → 응답의 3단계 구조, 검증자가 비밀을 모른 채 유효성 확인, 해시 함수로 비대화형화.
• "On parallel composition of zero-knowledge proofs with black-box quantum simulators" (2006) — arXiv:quant-ph/0607211 — 건전성 오류를 줄이려는 병렬 합성이 블랙박스 시뮬레이터 아래서 영지식성과 양립하기 어렵다는 결과. 동료심사 전 프리프린트.
• "The Fiat–Shamir Transformation of Special-Sound Interactive Proofs," Journal of Cryptology (2026) — DOI: 10.1007/s00145-025-09569-y — 지식 오류(knowledge error)와 추출기 기반 분석. special-sound 부류에서 손실이 질의 수에 선형·라운드 수와 무관.
• "Fiat–Shamir Transformation of Multi-Round Interactive Proofs (Extended Version)," Journal of Cryptology (2023) — DOI: 10.1007/s00145-023-09478-y — 공개 동전 대화형 증명의 비대화형화와 랜덤 오라클 모델. 다중 라운드의 Q^μ 보안 손실과 special-sound의 선형 손실.
• "A Survey of Noninteractive Zero Knowledge Proof System and Its Applications," The Scientific World Journal (2014) — DOI: 10.1155/2014/560484 — NIZK = 메시지 한 개. NP 문제의 NIZK, 통계적·완전 영지식, zap과의 연결.
• "Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability" (2026) — arXiv:2602.02689 — Goldreich–Micali–Wigderson 영지식 프로토콜의 일반화 + Fiat–Shamir 변환 + Merkle 커밋먼트. 동료심사 전 프리프린트.
• "Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial" (2001) — arXiv:cs/0111056 — 일방향 함수(계산은 쉽고 역산은 어렵다)와 영지식 프로토콜, 대화형 증명 시스템. 동료심사 전 프리프린트.
• "Mathematical foundations of modern cryptography: computational complexity perspective" (2002) — arXiv:cs/0212055 — 암호화·의사난수·영지식 대화형 증명·다자간 프로토콜의 계산복잡도 기초. 동료심사 전 프리프린트.
• "An investigation into graph isomorphism based zero-knowledge proofs" — DOI: 10.12794/metadc12076 — 그래프 동형은 많은 유형의 그래프에서 쉽게 풀려 실용적 ZKP 기반으로 적절하지 않다는 분석. 학위논문.
• "Cryptography for a Verifiable World: Foundations and Applications of Succinct Proof Systems" — DOI: 10.20868/upm.thesis.91808 — 간결성(증명 크기·검증 시간이 witness보다 훨씬 작음)의 정의와 응용 지형. 박사학위논문.
• "A Survey on the Applications of Zero-Knowledge Proofs" (2024) — arXiv:2408.00243 — 비교 기준(증명 크기·증명자/검증자 시간·메모리·셋업 가정), 블록체인 안팎 응용 분류. 동료심사 전 프리프린트.
• "A Comparative Analysis of zk-SNARKs and zk-STARKs: Theory and Practice" (2025) — arXiv:2512.10020 — ARM 플랫폼 실측. SNARK는 증명 생성이 빠르고 크기가 작지만 검증이 느리고 신뢰 셋업 필요, STARK는 반대이며 투명·양자후 지향. 동료심사 전 프리프린트.
• "Systematic review: Comparing zk-SNARK, zk-STARK, and bulletproof protocols for privacy-preserving authentication," Security and Privacy (2024) — DOI: 10.1002/spy2.401 — 41편 검토. 구현 간 실세계 성능이 최대 수 자릿수 차이, 보안 분석 방법론이 제각각이라 결정적 비교 불가.
• "Lite-PoT: Practical Powers-of-Tau Setup Ceremony" (2025) — arXiv:2503.04549 — 신뢰 셋업 비밀 τ의 유출이 거짓 증명을 가능하게 하고 그 위의 모든 zk-SNARK 건전성을 훼손. 동료심사 전 프리프린트.
• "Improved Constant-Sized Polynomial Commitment Schemes Without Trusted Setup," IACR Communications in Cryptology (2025) — DOI: 10.62056/anudy76bm — 최고 성능 argument는 신뢰 셋업 의존, 투명 계열은 역사적으로 비효율(증명 크기 열세).
• "Demystifying the Role of zk-SNARKs in Zcash" (2020) — arXiv:2008.00881 — Zcash의 프라이버시 보장이 zk-SNARK 구성에 전적으로 의존. 동료심사 전 프리프린트.
• "Analyzing Performance Bottlenecks in Zero-Knowledge Proof Based Rollups on Ethereum" (2025) — arXiv:2503.22709 — zk-롤업의 성능이 ZKP 메커니즘의 효율에 제약됨. 동료심사 전 프리프린트.
• "ZKlaims: Privacy-preserving Attribute-based Credentials using Non-interactive Zero-knowledge Techniques" (2019) — arXiv:1907.09579 — SNARK 기반 자격증명. 내용을 드러내지 않고 명제만 증명, 비대화형 제시. 동료심사 전 프리프린트.
• "A Scalable, Privacy-Preserving Decentralized Identity and Verifiable Data Sharing Framework based on Zero-Knowledge Proofs" (2025) — arXiv:2510.09715 — zk-STARK로 "나이가 18세 이상" 같은 조건만 증명. 증명 크기는 크지만 신뢰 셋업 없음·양자후 보안. 동료심사 전 프리프린트.
• "Dispute-free Scalable Open Vote Network using zk-SNARKs" (2022) — arXiv:2203.03363 — 오프체인 집계 계산의 정확성을 zk-SNARK로 검증해 확장성과 분쟁 없는 성질을 함께. 동료심사 전 프리프린트.
• "A survey of zero-knowledge proof based verifiable machine learning," Artificial Intelligence Review (2026) — DOI: 10.1007/s10462-026-11557-y — 검증가능 학습·추론·테스트 세 범주와 구현 과제, 상용화 동향.
• "A Survey of Zero-Knowledge Proof Based Verifiable Machine Learning" (2025) — arXiv:2502.18535 — 회로 표현력 한계·높은 증명 비용·배포 복잡성이 주된 병목. 동료심사 전 프리프린트.
• "Cryptographic Data Exchange for Nuclear Warheads" (2025) — arXiv:2507.20074 — 커밋먼트 + zkSNARK로 침습적 사찰 없이 조약 준수를 검증하되 탄두 정보는 기밀 유지. 동료심사 전 프리프린트.
• "NP-Completeness and Physical Zero-Knowledge Proofs for Sumplete, a Puzzle Generated by ChatGPT," New Generation Computing (2024) — DOI: 10.1007/s00354-024-00267-0 — 물리 카드만으로 퍼즐 해답의 지식을 증명하는 프로토콜.
• "NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam" (2026) — arXiv:2603.01393 — 물리적 도구로 구현 가능한 영지식 증명. 동료심사 전 프리프린트.
• "Exploring the Privacy Concerns in Permissionless Blockchain Networks and Potential Solutions" (2023) — arXiv:2305.01038 — 거래 연결·거래 메타데이터·온체인 분석 등 내용과 무관한 프라이버시 위험의 목록. 동료심사 전 프리프린트.
• "Privacy in Blockchain Systems" (2018) — arXiv:1809.10642 — 블록체인 프라이버시는 아직 신뢰할 만한 수준에 이르지 못했다는 문헌 검토. 동료심사 전 프리프린트.
• "Linking Souls to Humans: Blockchain Accounts with Credible Anonymity for Web 3.0 Decentralized Identity" (2023) — arXiv:2301.02102 — 완전 익명 계정 시스템에서 인증 없이 계정을 여럿 만들어 활동을 흐릴 수 있다는 문제. 동료심사 전 프리프린트.
• "SoK: What don't we know? Understanding Security Vulnerabilities in SNARKs" (2024) — arXiv:2402.15293 — SNARK를 "그냥 수학"으로 보는 전제에 대한 반박. 실제 취약점 141건의 분류. 동료심사 전 프리프린트.
• "Towards Fuzzing Zero-Knowledge Proof Circuits (Short Paper)" (2025) — arXiv:2504.14881 — 널리 쓰이는 ZKP 회로 라이브러리 퍼징으로 개발자 확인 신규 버그 10건. 동료심사 전 프리프린트.
• "fAmulet: Finding Finalization Failure Bugs in Polygon zkRollup" (2024) — arXiv:2410.12210 — 배포된 zk-롤업에서 최종화 실패를 일으키는 제로데이 버그 12건 발견·수정. 동료심사 전 프리프린트.
• "SoK: Understanding zk-SNARKs: The Gap Between Research and Practice" (2025) — arXiv:2502.02387 — 학계는 증명 시스템, 산업은 제약 시스템이 병목이라는 간극 진단. 동료심사 전 프리프린트.
• "Enabling AI ASICs for Zero Knowledge Proof" (2026) — arXiv:2604.17808 — 증명 생성 비용은 여전히 크며 MSM·NTT가 실행 시간을 지배. 동료심사 전 프리프린트.
• "On Doubly-Efficient Interactive Proof Systems," Foundations and Trends in Theoretical Computer Science (2018) — DOI: 10.1561/0400000084 — 증명자가 다항 시간, 검증자가 거의 선형 시간이어야 현실의 계산 주체가 대화형 증명의 이점을 누린다.
• "The Fiat-Shamir Transformation in a Quantum World" (2013) — arXiv:1306.0315 — 양자 랜덤 오라클 모델에서 Fiat–Shamir의 보안 증명이 어려워 보이며 블랙박스 추출기가 존재할 수 없음. 동료심사 전 프리프린트.
• "Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model" (2019) — arXiv:1902.07556 — 일반적 환원으로 건전성·지식증명 성질이 양자 공격 아래서도 보존됨을 보이고 기존 문헌의 일부 주장을 반박. 동료심사 전 프리프린트.
• "Zero-Knowledge Proof Frameworks: A Systematic Survey" (2025) — arXiv:2502.07063 — ZKP의 정의와 25개 범용 프레임워크의 사용성·성능 실측, 실행 환경 공개. 동료심사 전 프리프린트.
• "Why and How zk-SNARK Works" (2019) — arXiv:1906.07221 — 사전 지식 없이 예제로 따라가는 zk-SNARK 내부 해설. 동료심사 전 프리프린트.
• "State of the Art Report: Verified Computation" (2023) — arXiv:2308.15191 — 128편·4,000쪽 이상을 정리한 검증가능 계산의 이론적 기초와 실무. 동료심사 전 프리프린트.
• "Zero Knowledge Proof based authentication protocol using graph isomorphism" (2019) — arXiv:1911.09329 — 청구자와 검증자 사이 직접적 정보 교환 없는 인증. 비밀번호를 서버에 드러내지 않는 구조. 동료심사 전 프리프린트.