💻 computer science

Weak Zero-Knowledge and One-Way Functions

이 논문은 NP 에 속하는 모든 언어가 특정 오류 조건 ( $\epsilon_c+\epsilon_s+\epsilon_z < 1$ 등) 을 만족하는 약한 영지식 증명 프로토콜을 가진다면 일방향 함수가 존재함을 증명하여, 기존 연구보다 더 넓은 오류 범위에서 약한 영지식성과 일방향 함수의 존재성을 연결했습니다.

원저자: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

게시일 2026-02-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 암호학의 두 가지 거대한 개념인 **'영지식 증명 (Zero-Knowledge, ZK)'**과 '일방향 함수 (One-Way Function, OWF)' 사이의 관계를 새로운 각도에서 탐구합니다.

간단히 말해, **"약한 조건을 가진 영지식 증명 시스템이 존재한다면, 우리는 반드시 암호학의 핵심인 '일방향 함수'를 만들 수 있다"**는 것을 증명했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 풀어보겠습니다.

1. 배경: 두 가지 핵심 개념

먼저 두 주인공을 소개합니다.

영지식 증명 (Zero-Knowledge Proof):
- 비유: "비밀번호를 말하지 않고도 내가 그 비밀번호를 알고 있다는 것을 증명하는 것"입니다.
- 예시: 어두운 동굴에 두 개의 입구가 있고, 그 사이에는 마법 문이 있습니다. A 는 B 에게 "나는 문 여는 비법을 안다"고 증명하고 싶지만, 비법을 알려주고 싶지는 않습니다. B 가 "왼쪽 입구로 들어가서 오른쪽 입구로 나오라"고 시키면, A 는 비법을 알고 있으므로 언제든지 두 입구를 오갈 수 있습니다. B 는 A 가 비법을 알았다고 확신하지만, 그 비법 자체는 절대 알 수 없습니다.
- 현재의 문제: 기존 연구들은 이 증명 시스템이 완벽하게 작동해야만 (오류가 거의 0 이어야만) 암호학적으로 의미 있다고 보았습니다. 하지만 현실의 많은 프로토콜은 약간의 실수 (오류) 를 허용합니다.
일방향 함수 (One-Way Function, OWF):
- 비유: "계란을 부수는 것은 쉽지만, 부순 계란을 다시 원래 상태로 되돌리는 것은 불가능한 것"입니다.
- 의미: 암호학의 가장 기초가 되는 개념입니다. 만약 이런 함수가 존재하지 않는다면, 모든 암호는 깨질 수 있습니다.

2. 이 논문의 핵심 발견: "약한 증명도 충분하다"

기존 연구들은 영지식 증명의 오류가 아주 작아야 (negligible) 일방향 함수가 존재한다고 주장했습니다. 하지만 이 논문은 **"오류가 좀 크더라도, 세 가지 오류의 합이 100% 미만이기만 하면 일방향 함수가 존재한다"**는 것을 증명했습니다.

세 가지 오류는 다음과 같습니다:

진실한 사람이 틀릴 확률 (Completeness Error): 진짜 비밀번호를 가진 사람이 실수해서 증명에 실패할 확률.
가짜 사람이 속일 확률 (Soundness Error): 비밀번호를 모르는 사람이 증명에 성공할 확률.
비밀이 새어 나올 확률 (Zero-Knowledge Error): 증명 과정에서 비밀이 조금이라도 유출될 확률.

논문의 결론:
이 세 가지 확률을 더했을 때 100% 미만이면 됩니다. (예: 진실한 사람이 10% 실수하고, 가짜 사람이 20% 속이고, 비밀이 10% 새어 나와도, 합계가 40% 라면 OK!)

기존 연구는 "진실한 사람의 실수 + 비밀 유출 + (가짜 사람의 속임수) 의 제곱근"이 100% 미만이어야 한다고 했는데, 이 논문은 그 조건을 훨씬 더 넓혀서 단순한 합으로만 판단할 수 있게 만들었습니다.

3. 비유로 이해하는 증명 과정

이 논문은 어떻게 이 결론을 이끌어냈을까요? 수사관과 위조지폐 비유로 설명해 보겠습니다.

상황: 가짜 증명 (위조지폐) 을 찾는 수사관

우리는 어떤 언어 (문제) 가 정말 어려운지 (Worst-case hard) 알 수 없습니다. 만약 이 문제가 정말 어렵다면, 가짜 증명 (위조지폐) 을 만드는 것은 불가능해야 합니다.

가상의 시나리오:
- 우리가 가진 영지식 증명 시스템이 약해서, 가짜 증명 (위조지폐) 을 만들어낼 확률이 조금 있고, 비밀이 조금 새어 나온다고 가정해 봅시다.
- 만약 일방향 함수가 존재하지 않는다면, 우리는 이 시스템의 "비밀"을 역으로 계산해서 (Invert) 가짜 증명을 완벽하게 만들 수 있어야 합니다.
수사관의 전략 (논문의 방법):
- 기존 연구자들은 가짜 증명을 찾을 때, "비밀이 새어 나올까 봐" 너무 두려워해서 검증 과정을 두 번 반복했습니다. (비유: 위조지폐를 검사할 때, 한 번은 눈으로 보고, 또 한 번은 자외선으로 확인하는 식). 이렇게 하면 오류가 두 배로 쌓여 조건이 까다로워졌습니다.
- 이 논문의 혁신: "검증 과정 (Verification) 을 증명 생성 과정에 이미 포함시켜라!"라고 제안합니다.
- 비유: 수사관이 위조지폐를 만들 때, "이 지폐가 진짜인지 확인하는 기계 (검증기) 가 이미 내 손에 있다"고 가정합니다. 그래서 가짜 지폐를 만들 때, 그 기계가 "OK"라고 찍어주는지 확인하면서 만듭니다.
- 이렇게 하면 검증 과정을 따로 반복할 필요가 없어지고, 오류가 한 번만 계산됩니다. 그 결과, 훨씬 더 넓은 조건 (오류의 단순 합) 에서도 일방향 함수가 존재함을 증명할 수 있게 되었습니다.

4. 대화형 증명 (Public-Coin) 의 경우

이 논문은 대화형 증명 (서로 말을 주고받는 방식) 에 대해서도 연구했습니다.

비유: 경찰 (검증자) 이 범인 (증명자) 에게 "지금부터 무작위로 질문할게. 네가 범인이라면 이 질문에 답할 수 있겠지?"라고 묻는 상황입니다.
결과: 질문을 주고받는 횟수 (라운드) 가 $k$ 번일 때, 오류의 합이 $k$ 배의 비밀 유출 확률을 포함하더라도 100% 미만이면 일방향 함수가 존재한다는 것을 증명했습니다.
한계: 아주 짧은 대화 (상수 횟수) 에서는 완벽한 일방향 함수를 보장하지만, 대화 횟수가 무한히 길어질 경우 "무한히 자주 (Infinitely Often)"만 작동하는 약한 형태의 일방향 함수를 보장합니다. (즉, 모든 경우에 완벽하게 작동하지는 않지만, 충분히 많은 경우에서는 작동한다는 뜻입니다.)

5. 요약 및 의의

이 논문의 핵심 메시지:
"완벽한 영지식 증명을 기다릴 필요 없습니다. 현실적으로 약간의 실수가 있더라도, 그 실수들의 합이 100% 를 넘지 않는다면, 우리는 여전히 강력한 암호학의 기초 (일방향 함수) 를 가질 수 있습니다."

왜 중요한가요?

현실 적용성: 이론적으로 완벽한 시스템을 구축하기 어렵기 때문에, 약간의 오류를 허용하는 현실적인 프로토콜들도 암호학적으로 안전하다는 것을 보장해 줍니다.
조건 완화: 기존에 필요했던 복잡한 조건 (제곱근 등) 을 단순화하여, 더 많은 종류의 프로토콜이 암호학의 기초가 될 수 있음을 보여줍니다.
새로운 길: 약한 영지식 증명 시스템이 어떻게 강력한 암호학 도구를 만들어내는지에 대한 새로운 통찰을 제공했습니다.

결론적으로, 이 논문은 **"완벽함은 신의 영역이지만, 약간의 불완전함 속에서도 우리는 여전히 안전한 암호를 만들 수 있다"**는 희망적인 메시지를 전하고 있습니다.

1. 연구 배경 및 문제 제기 (Problem)

제로지식 (ZK) 과 암호학적 기초: 제로지식 프로토콜은 증명자가 검증자에게 명제의 참을 증명하되, 추가적인 비밀 정보를 누출하지 않는 시스템입니다. 기존 연구 (Ostrovsky, Wigderson, Hirahara 등) 는 오류가 무시할 수 있을 정도로 작을 때 (negligible), ZK 프로토콜의 존재가 일방향 함수 (OWF) 의 존재를 보장함을 보였습니다.
약한 ZK 프로토콜의 한계: 실제 많은 교육용 또는 실용적 프로토콜 (예: 3-색칠 문제, 그래프 동형사상 문제) 은 본질적으로 상수 크기의 오류 (완전성 오류 $\epsilon_c$ , 무결성 오류 $\epsilon_s$ , 제로지식 오류 $\epsilon_z$ ) 를 가집니다.
기존 연구의 제약: 최근 연구 (Chakraborty et al., CRYPTO 2025) 는 약한 NIZK(비상호적 ZK) 에 대해 $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ 조건 하에서 OWF 존재를 증명했습니다. 그러나 이는 $\epsilon_s$ 에 제곱근이 적용되어 모든 비자명한 (non-trivial) 오류 조합을 포괄하지 못했습니다.
핵심 질문:
1. 모든 오류가 상수일 수 있는 가장 일반적인 조건 ( $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ) 에서도 OWF 가 존재하는가?
2. 상호작용형 (Interactive) 및 공개동전 (Public-coin) 프로토콜의 경우, 오류 조건은 어떻게 되는가?

2. 주요 기여 및 결과 (Key Contributions & Results)

저자들은 NP 에 속하는 모든 언어가 약한 ZK 프로토콜을 가진다는 가정 하에 (최악의 경우 NP 가 어렵다는 가정), 다음과 같은 결과를 도출했습니다.

2.1. 비상호적 ZK (NIZK) 의 일반화

결과: NP 의 모든 언어가 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ 을 만족하는 NIZK 증명 (또는 Argument) 을 가진다면, 일방향 함수 (OWF) 가 존재합니다.
의의: 이는 $\epsilon_s$ 에 대한 제곱근 제약 ( $\sqrt{\epsilon_s}$ ) 을 제거한 것입니다. 즉, $\epsilon_c + \epsilon_s + \epsilon_z < 1$ 인 모든 비자명한 오류 조합에 대해 OWF 가 존재함을 의미합니다.
확장: 만약 $\epsilon_c$ 가 무시할 수 있을 정도로 작다면, 이 결과는 모든 오류가 무시할 수 있는 표준 NIZK 로 증폭 (Amplification) 가능함을 의미합니다.

2.2. 공개동전 (Public-Coin) ZK 프로토콜

결과 (t 메시지): NP 의 모든 언어가 $t$ $t$ 개의 메시지로 이루어진 공개동전 ZK 프로토콜을 가지며, $\epsilon_c + \epsilon_s + (t-1)\cdot\epsilon_z < 1$ $ϵ_{c} + ϵ_{s} + (t - 1) \cdot ϵ_{z} < 1$ 을 만족하면 OWF 가 존재합니다.
- 기존 기술 ( $\epsilon_c + \epsilon_s + t \cdot \epsilon_z < 1$ ) 보다 $\epsilon_z$ 의 계수가 1 줄어든 개선된 조건입니다.
결과 (상수 라운드): $k$ $k$ 라운드의 상수 라운드 공개동전 ZK 프로토콜이 $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ $ϵ_{c} + ϵ_{s} + k \cdot ϵ_{z} < 1$ 을 만족하면, 무한히 자주 (Infinitely-often) 일방향 함수가 존재합니다.
- 이 경우 조건이 더 엄격해지지만, 증명 기법상 '무한히 자주'라는 약한 형태의 OWF 만 보장됩니다.

3. 방법론 및 기술적 개요 (Methodology)

저자들의 핵심 아이디어는 검증자 (Verifier) 의 역할을 일방향 함수 후보에 명시적으로 포함시키고, 재귀적 (Recursive) 접근법을 사용하는 것입니다.

3.1. 기존 접근법 (Ostrovsky-Wigderson) 의 한계

기존 연구는 시뮬레이터 (Simulator) 의 출력을 역으로 푸는 (Invert) 공격자가 있다면, 이를 이용해 언어의 소속 여부를 판별할 수 있음을 보였습니다. 그러나 이 과정에서 제로지식 오류 ( $\epsilon_z$ ) 를 두 번 적용해야 했기 때문에 ( $\epsilon_s + 2\epsilon_z < 1$ ), 조건이 엄격해졌습니다.

3.2. 저자들의 개선: 검증 포함 (Verification Inclusion)

저자는 후보 일방향 함수 $f_x$ 의 출력을 단순히 $(r, \pi)$ 가 아닌 $(r, a)$ 로 정의합니다. 여기서 $a$ 는 검증 알고리즘 $V(x; r, \pi)$ 의 결과 (1 또는 0) 입니다.

핵심 논리: 공격자가 $f_x$ 를 성공적으로 역으로 풀어 $(r, 1)$ 을 얻는다면, 이는 검증자가 1 을 출력하는 유효한 증명을 의미합니다. 따라서 공격자가 성공하면 추가적인 검증 과정 없이도 프로토콜이 성공한 것으로 간주할 수 있어, $\epsilon_z$ 의 추가 비용을 절감합니다.
결과: 이 기법을 통해 $\epsilon_s + \epsilon_z < 1$ 조건을 달성했습니다.

3.3. 다라운드 프로토콜을 위한 재귀적 구성 (Recursive Construction)

상호작용형 프로토콜 (Public-Coin ZK) 의 경우, 라운드가 증가할수록 오류가 누적됩니다.

전략: $k$ $k$ 라운드 프로토콜의 경우, $k$ $k$ 개의 일방향 함수 $f_1, \dots, f_k$ $f_{1}, \dots, f_{k}$ 를 재귀적으로 정의합니다.
- 마지막 라운드 ( $f_k$ ) 의 역산 공격자는 이전 라운드의 성공 확률을 추정합니다.
- 이전 라운드 ( $f_i$ ) 의 함수는 다음 라운드 공격자 ( $A_{i+1}$ ) 를 오라클로 사용하여, 해당 라운드에서의 성공 확률 (또는 기대값) 을 계산하는 함수로 정의됩니다.
최적화: 공격자는 각 라운드에서 다음 라운드의 성공 확률을 최대화하는 메시지를 선택하도록 유도됩니다.
한계: 이 재귀적 구조는 모든 라운드에서 공격자가 동시에 성공해야 모순을 이끌어낼 수 있으므로, 결과적으로 무한히 자주 (Infinitely-often) OWF 가 존재한다는 약한 결론으로 이어집니다.

4. 결론 및 의의 (Significance)

약한 ZK 의 힘 규명: 이 논문은 제로지식 프로토콜이 매우 약한 조건 (상수 오류) 하에서도 강력한 암호학적 기초 (OWF) 를 제공할 수 있음을 보여주었습니다. 이는 "약한 ZK 는 암호학적 기초가 될 수 있는가?"라는 질문에 대해 "예, 조건만 맞다면 가능하다"는 강력한 답을 제공합니다.
오류 조건의 최적화: NIZK 에 대해 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ 이라는 가장 일반적인 조건을 달성함으로써, 기존 연구의 제약 ( $\sqrt{\epsilon_s}$ 등) 을 제거했습니다.
개방된 문제 (Open Problems):
- 개인동전 (Private-coin) 프로토콜: 현재 결과는 공개동전 프로토콜에 국한되어 있으며, 개인동전 프로토콜로 확장 가능한지가 미해결 문제입니다.
- 무한히 자주 (Infinitely-often) 의 제거: 상수 라운드 프로토콜의 경우 '무한히 자주'라는 약한 형태의 OWF 만 증명되었습니다. 이를 표준 OWF 로 강화하는 것이 향후 과제로 남았습니다.
- 초상수 라운드: 라운드 수가 상수가 아닌 경우의 오류 조건 개선도 새로운 도구가 필요합니다.

요약

이 논문은 약한 제로지식 프로토콜 (상수 오류 허용) 이 존재하면 일방향 함수가 존재한다는 것을 증명하는 획기적인 연구입니다. 저자들은 검증 과정을 일방향 함수 정의에 통합하고 재귀적 공격 시나리오를 설계함으로써, 기존 연구보다 훨씬 일반화된 오류 조건 하에서도 OWF 의 존재를 보장함을 보였습니다. 이는 암호학의 기초 이론에서 제로지식의 위상을 한 단계 더 높이는 중요한 기여입니다.