💻 computer science

Non-Trivial Zero-Knowledge Implies One-Way Functions

이 논문은 $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$ 를 가정할 때, 오류 합이 1 보다 작은 '비자명한 (non-trivial)' 영지식 증명 (NIZK 및 상호작용형) 의 존재가 일방향 함수의 존재를 함의함을 증명하여, 기존에 해결되지 않았던 고오류 영역에서의 관계를 규명했습니다.

원저자: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

게시일 2026-02-20

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

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

1. 배경: 자물쇠 (OWF) 와 마술사 (ZK)

한 방향 함수 (OWF): 쉽게는 **'자물쇠'**라고 생각하세요. 누구나 자물쇠를 잠글 수는 있지만 (쉬움), 잠긴 자물쇠를 열쇠 없이 다시 여는 것은 거의 불가능합니다 (어려움). 이 '자물쇠'가 있어야만 은행 보안, 암호 메시지 등 현대 암호학이 가능합니다.
영지식 증명 (ZK): **'마술사'**가 있습니다. 마술사는 "내가 이 보물 상자의 비밀번호를 알고 있다"는 사실만 증명하고, 실제 비밀번호는 절대 말하지 않습니다. 검증자는 마술사가 진짜로 비밀번호를 알고 있는지만 확인할 뿐, 비밀번호 자체는 모릅니다.

기존의 문제:
과거 연구자들은 "영지식 증명 (마술) 을 만들려면 반드시 자물쇠 (OWF) 가 있어야 한다"고 믿어왔습니다. 하지만 그 전제 조건이 너무 까다로웠습니다. "마술사의 실수 (오류) 가 거의 0에 가까워야만 자물쇠가 존재한다고 증명할 수 있다"는 것이었습니다.

만약 마술사가 가끔 실수하거나, 거짓말을 할 확률이 조금이라도 높다면? 그때는 자물쇠가 존재하는지 알 수 없었습니다. 마치 "완벽한 마술만 자물쇠를 만든다"는 식이었죠.

2. 이 논문의 핵심 발견: "약한 마술도 자물쇠를 만든다"

이 논문은 **"완벽할 필요는 없다"**는 것을 증명했습니다.

새로운 발견: 마술사 (영지식 증명) 가 완벽하지 않아도, 전체적인 실수 확률 (완성도, 거짓말, 정보 유출의 합) 이 100% 미만이라면, 그 자체로 강력한 자물쇠 (OWF) 가 존재한다는 것을 증명했습니다.
비유: 마술사가 10 번 중 1 번은 실수를 하더라도, 그 마술쇼가 '의미 있는' 수준이라면, 그 마술쇼를 통해 자물쇠를 만들 수 있다는 뜻입니다.

3. 어떻게 증명했을까요? (창의적인 비유)

저자들은 이전 연구자들이 놓친 **'반복의 힘'**을 발견했습니다.

비유 1: 복권 추첨 (NIZK - 비상호적 증명)

상황: 마술사가 한 번의 마술로 자물쇠를 만들려다 실패했습니다. (실수 확률이 높음)
해법: 하지만 마술사를 수천 번 부른다고 상상해 보세요.
- 만약 마술사가 가짜라면, 수천 번 중 한 번도 성공할 확률은 거의 0 입니다.
- 만약 마술사가 진짜라면, 수천 번 중 적어도 한 번은 성공할 확률은 100% 에 가깝습니다.
결과: 이 논리는 "수천 번 반복해서 성공하는지 확인하는 알고리즘"을 통해, 약한 마술사조차 자물쇠를 만드는 데 쓸 수 있음을 보여줍니다.

비유 2: 체스 경기 (상호적 증명)

상황: 마술사와 검증자가 여러 번 대화하며 (상호적) 마술을 펼칩니다.
해법: 저자들은 **'악의적인 마술사 (eP)'**라는 가상의 인물을 만들었습니다. 이 악의적인 마술사는 "어떤 말을 하면 검증자를 가장 잘 속일 수 있을까?"를 계산해서 최선의 말을 선택합니다.
핵심: 이 악의적인 마술사가 검증자를 속일 확률이 높다면, 그건 진짜 마술사도 속일 수 있다는 뜻이고, 결국 자물쇠가 존재한다는 증거가 됩니다.

4. 이 연구가 왜 중요한가요?

이 연구는 암호학의 지형을 바꿉니다.

문턱이 낮아졌습니다: 이제 우리는 "완벽한 영지식 증명"을 찾기 위해 애쓸 필요가 없습니다. 실수가 좀 있는 '약한' 증명 시스템만 있어도, 그걸로 강력한 암호 체계 (자물쇠) 를 만들 수 있습니다.
약한 것을 강하게 만드는 법: 만약 우리가 약한 영지식 증명 시스템을 발견했다면, 이 논리를 통해 그것을 자물쇠로 변환하고, 그 자물쇠를 이용해 다시 완벽한 영지식 증명을 만들어낼 수 있습니다. (약한 것 → 자물쇠 → 완벽한 것)
실용성: 실제 세상에서는 완벽한 시스템은 없습니다. 이 연구는 "불완전한 시스템이라도 가치가 있다"는 것을 수학적으로 증명해 주었습니다.

5. 요약

이 논문은 **"영지식 증명 (마술) 이 완벽하지 않아도, 그 마술이 '의미 있는' 수준이라면, 그 마술을 통해 암호학의 핵심인 자물쇠 (One-Way Function) 를 만들 수 있다"**는 것을 증명했습니다.

이는 마치 **"완벽한 마술사가 아니더라도, 마술을 할 줄 안다면 그 지식으로 금고를 열 수 있는 열쇠를 만들 수 있다"**는 놀라운 발견과 같습니다. 앞으로 더 쉽고 강력한 암호 시스템을 설계하는 데 큰 발판이 될 것입니다.

1. 문제 제기 (Problem Statement)

배경: 영지식 증명 (ZK) 은 증명자가 증명자 (Verifier) 에게 어떤 NP 문제의 해 (witness) 를 알리지 않고 그 유효성을 증명하는 시스템입니다. 기존 연구 (Ostrovsky, Wigderson 등) 는 평균적인 난이도 (average-case hardness) 하에서 ZK 가 OWF 를 함의함을 보였습니다. 최근 Hirahara 와 Nanashima (HN24) 는 최악의 경우 난이도 (worst-case hardness, $NP \not\subseteq ioP/poly$ ) 하에서도 ZK 가 OWF 를 함의함을 보였습니다.
한계 (Gap): 기존 연구들은 ZK 프로토콜의 오류 (완전성 오류 $\epsilon_c$ , 건전성 오류 $\epsilon_s$ , 영지식 오류 $\epsilon_{zk}$ ) 가 무시할 수 있을 정도로 작아야 (negligible) 함을 전제로 했습니다.
핵심 질문: 만약 ZK 프로토콜의 오류가 무시할 수 없을 정도로 크더라도 (즉, $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ $ϵ_{c} + ϵ_{s} + ϵ_{z k} < 1$ 인 "비자명한" 프로토콜만 존재한다고 가정할 때), 여전히 OWF 를 유도할 수 있을까요?
- 오류가 큰 ZK 는 구성하기 쉽지만, 이를 OWF 로 변환하는 기존 기법들은 오류가 작을 때만 작동합니다.
- 만약 비자명한 ZK 가 OWF 를 함의하지 않는다면, 이러한 프로토콜은 암호학적 기초를 마련하는 데 쓸모없는 약한 객체일 수 있습니다.

2. 방법론 (Methodology)

저자들은 기존 기법들의 실패 원인을 분석하고, 이를 극복하기 위해 **반복 (Repetition)**과 **최적의 증명자 전략 (Optimal Prover Strategy)**을 결합한 새로운 접근법을 제시합니다.

2.1 기존 기법의 한계 분석

OW93 및 CHK25 기법: 기존 연구들은 '보편적 외삽법 (Universal Extrapolation, UE)'을 사용하여 시뮬레이터가 생성한 난수를 역추적하거나, 공통 참조 문자열 (CRS) 의 분포를 확인하는 방식을 사용했습니다.
실패 원인: 오류가 큰 경우 ( $\epsilon_s + \epsilon_{zk} \approx 1$ ), 시뮬레이터가 특정 CRS 에 대해 "좋은 증명 (accepting proof)"을 항상 생성하지 않고, 때로는 "나쁜 증명"을 생성하는 방식으로 ZK 속성을 만족시킬 수 있습니다. 이 경우 기존 알고리즘은 참인 입력과 거짓인 입력을 구분하는 데 실패합니다.

2.2 새로운 접근법: 반복과 최적화

저자들은 비자명한 ZK 에서 OWF 를 유도하기 위해 다음과 같은 전략을 사용합니다.

반복을 통한 '좋은 CRS' 식별 (NIZK 의 경우):
- 단일 시뮬레이션이 실패할지라도, 동일한 CRS 에 대해 시뮬레이터를 여러 번 ( $p(|x|)$ 번) 실행합니다.
- 만약 CRS 가 '나쁜 (Bad)' 것이라면 시뮬레이터는 거의 항상 거절하는 증명을 생성합니다. 반면 '좋은 (Good)' CRS 라면 시뮬레이터가 적어도 한 번은 승인되는 증명을 생성할 확률이 높습니다.
- 알고리즘은 여러 번의 시도 중 하나라도 승인되는 증명이 나오면 참으로 판단합니다. 이를 통해 $\epsilon_s + \epsilon_{zk} < 1$ 조건 하에서도 OWF 를 유도할 수 있음을 보입니다.
대화형 ZK 로의 일반화 (Interactive ZK):
- 악의적 증명자 $\tilde{P}$ 정의: 대화형 프로토콜에서는 다음 메시지가Verifier 의 승인으로 이어질지 미리 알 수 없습니다. 저자들은 '최적의 증명자' $\tilde{P}$ 를 정의합니다. 이 증명자는 현재까지의 대화 기록 (transcript) 을 바탕으로,Verifier 가 승인할 확률이 가장 높은 다음 메시지를 선택합니다.
- 효율성 확보: $\tilde{P}$ 를 효율적으로 구현하기 위해 UE 를 사용하여 가능한 다음 메시지들을 샘플링하고, 그중에서 가장 성공 확률이 높은 것을 선택합니다.
- Public-Coin 가정: Verifier 의 난수가 공개적 (Public-Coin) 일 때, $\tilde{P}$ 는 내부적으로 Verifier 와의 상호작용을 시뮬레이션하여 성공 확률을 추정할 수 있습니다.
- Private-Coin 처리: Private-Coin 프로토콜의 경우, Verifier 가 난수를 숨기는 것이 일방향 함수의 존재와 직결됨을 보이며, 이를 Public-Coin 프로토콜로 변환하거나 보조 입력이 있는 일방향 함수 (Auxiliary-Input OWF) 를 유도합니다.

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

이 논문은 다음과 같은 주요 정리를 증명합니다 (단, $NP \not\subseteq ioP/poly$ 가정 하에):

비자명한 NIZK $\implies$ OWF (Theorem 3):
- NP 에 대한 비자명한 (오류 합이 1 미만인) 비대화형 영지식 증명 (NIZK) 이 존재하면, 일방향 함수 (OWF) 가 존재합니다.
- 이는 기존 CHK25 연구가 제한했던 $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ 조건을 넘어, $\epsilon_{zk} + \epsilon_s < 1$ 인 모든 비자명한 NIZK 에 대해 성립함을 보입니다.
비자명한 Public-Coin ZK $\implies$ OWF (Theorem 1):
- NP 에 대한 비자명한, 고정된 라운드 (constant-round), 공개 동전 (public-coin) 영지식 증명이 존재하면 OWF 가 존재합니다.
- 이는 상호작용형 프로토콜에서도 오류가 크더라도 OWF 를 유도할 수 있음을 의미합니다.
Private-Coin ZK $\implies$ 보조 입력 OWF (Theorem 2):
- Private-Coin 프로토콜의 경우, 보조 입력이 있는 일방향 함수 (Auxiliary-Input OWF) 가 존재함을 보입니다. 이는 정보이론적 ZK 구성이 불가능함을 시사합니다.
증폭 (Amplification) 의 무조건적 가능성:
- NIZK 증폭: 비자명한 NIZK 가 존재하면 OWF 가 유도되고, 이 OWF 를 이용해 기존 증폭 기법 (BG24, AK25) 을 적용하여 무시할 수 있는 오류를 가진 표준 NIZK를 구성할 수 있습니다. 즉, 암호학적 가정 없이 (NP 의 최악의 경우 난이도만 가정하고) 표준 NIZK 를 얻을 수 있습니다.
- 대화형 ZK 증폭: OWF 가 존재하면 4 라운드의 표준 ZK 프로토콜 (BJY97) 을 구성할 수 있으므로, 비자명한 ZK 가 존재하면 표준 ZK 가 존재함을 보였습니다.

4. 의의 (Significance)

영지식 증명의 복잡성 분류 완성:
- 영지식 증명이 "비자명한" 경우 (오류가 1 미만) 에만 존재하더라도, 이는 암호학의 기초인 OWF 와 동등한 힘을 가진다는 것을 증명했습니다. 즉, 오류가 큰 ZK 는 암호학적 기초가 될 수 없거나, 반대로 OWF 가 존재하지 않는다면 ZK 는 존재할 수 없다는 강력한 연결고리를 확립했습니다.
암호학적 가정의 제거:
- 기존에는 표준 ZK 를 구성하기 위해 공개키 암호나 OWF 와 같은 강한 암호학적 가정이 필요했습니다. 이 연구는 **NP 의 최악의 경우 난이도 ( $NP \not\subseteq ioP/poly$ )**라는 순수한 복잡도 이론적 가정 하에, 비자명한 ZK 가 존재하면 표준 ZK 를 구성할 수 있음을 보였습니다. 이는 ZK 의 존재성을 암호학적 가정이 아닌 복잡도 이론의 난이도에 기반하여 설명하는 획기적인 결과입니다.
새로운 증폭 기법의 기반 마련:
- 고오류 (High-error) ZK 프로토콜을 표준 (Negligible-error) ZK 로 변환하는 과정에서 별도의 암호학적 가정이 필요하지 않음을 보였습니다. 이는 향후 더 약한 조건에서 ZK 를 구성하거나 증폭하는 연구에 중요한 토대가 됩니다.

요약

이 논문은 **"비자명한 영지식 증명 (오류 합 < 1) 이 존재한다면, 이는 일방향 함수의 존재를 의미하며, 결과적으로 표준적인 영지식 증명 시스템을 구성할 수 있다"**는 것을 증명했습니다. 이는 영지식 증명의 존재 조건을 복잡도 이론의 핵심 난제 (NP 의 난이도) 와 직접적으로 연결하여, 암호학의 기초에 대한 이해를 한 단계 높였습니다.