A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes

이 논문은 제로지식 코드와 양자 CSS 코드가 동등함을 증명하고, 이를 활용하여 명시적 점근적 우수 제로지식 국소 테스트 가능 코드를 구성하는 방법을 제시합니다.

핵심

1. 두 가지 다른 이름, 같은 본질

이 논문은 마치 **"사과"**와 **"빨간 과일"**이 사실은 같은 것을 가리킨다는 것을 증명하는 것과 같습니다.

• 제로-지식 (ZK) 코드:

  • 비유: "비밀을 지키는 마법 상자"입니다.
  • 설명: 누군가에게 비밀스러운 메시지 (예: 비밀번호) 를 보내고 싶지만, 도청자가 코드의 일부만 훔쳐봐도 그 비밀이 무엇인지 전혀 알 수 없어야 합니다. 마치 마법 상자를 열어보지 않고는 내용물을 추측할 수 없는 것처럼, 코드의 일부 조각을 봐도 원래 메시지는 완전히 숨겨져 있어야 합니다.
  • 용도: 암호학, 비밀 공유, 안전한 통신 등에 쓰입니다.

• 양자 CSS 코드:

  • 비유: "양자 컴퓨터의 방패"입니다.
  • 설명: 양자 컴퓨터는 매우 민감해서 작은 소리나 진동 (오류) 만으로도 정보가 망가집니다. CSS 코드는 이런 오류를 자동으로 찾아서 고쳐주는 '방패' 역할을 합니다.
  • 용도: 양자 컴퓨팅의 안정성을 보장하고, 양자 정보 이론 연구에 쓰입니다.

논문의 핵심 발견:
저자들은 이 두 가지가 서로 다른 이름으로 불릴 뿐, 실제로는 같은 구조라는 것을 증명했습니다.

"비밀을 지키는 마법 상자 (ZK 코드) 를 잘 설계하면, 그것은 자연스럽게 양자 오류를 막는 방패 (CSS 코드) 가 됩니다. 반대로, 훌륭한 양자 방패를 만들면, 그것은 자연스럽게 비밀을 지키는 마법 상자가 됩니다."

---

2. 이 발견이 왜 중요할까요? (상호 번역기)

이 두 개념이 같다는 것을 알게 되면, 한 분야의 최신 기술을 다른 분야로 바로 가져와 쓸 수 있습니다.

• 상황: 양자 컴퓨팅 분야에서는 최근 "오류를 아주 잘 고치고, 효율도 좋은 새로운 방패 (양자 코드)"를 만드는 데 큰 성공을 거두었습니다.
• 문제: 하지만 암호학 (ZK 코드) 분야에서는 아직 그런 훌륭한 "비밀 지키기 상자"를 만들기 어렵거나, 효율이 떨어지는 경우가 많았습니다.
• 해결책: 저자들은 "아! 양자 방패를 ZK 코드 공식으로만 바꾸면 되네!"라고 생각했습니다.
  • 양자 분야에서 새로 만든 **최고급 방패 (양자 코드)**를 가져와서
  • **비밀 지키기 공식 (ZK 코드)**으로 번역했습니다.

---

3. 실제 성과: "초고속 비밀 지키기"

이 논문을 통해 얻은 구체적인 성과는 다음과 같습니다.

• 기존의 문제: 예전에는 비밀을 지키면서 (ZK), 동시에 오류를 고치고 (Decodable), 그리고 코드가 너무 길어지지 않도록 (Efficient) 하는 코드를 만들기 힘들었습니다. 특히 "코드의 일부분만 봐도 비밀이 안 새어나가야 한다"는 조건을 만족시키면서 코드를 짧게 만드는 게 어려웠습니다.
• 새로운 해결책: 양자 분야에서 최근 개발된 **최신 기술 (Asymptotically-good codes)**을 ZK 코드로 변환했습니다.
  • 결과: 이제 우리는 비밀을 완벽하게 지키면서, 오류도 잘 고치고, 코드의 길이도 효율적인 새로운 암호 코드를 만들 수 있게 되었습니다.
  • 특이점: 이전에는 코드의 일부분을 확인하는 횟수 (쿼리) 가 많아야 비밀이 안전했지만, 이제는 매우 적은 횟수만 확인해도 비밀이 안전해졌습니다. 마치 도청자가 코드를 아주 조금만 훔쳐봐도, 그걸로는 비밀을 추측할 수조차 없는 상태가 된 것입니다.

---

4. 요약: 한 줄로 정리하면?

"양자 컴퓨터를 보호하는 최신 기술 (CSS 코드) 을 암호학에 적용하는 '번역기'를 개발했습니다. 이를 통해, 도청자가 코드의 일부만 봐도 절대 비밀을 알 수 없는, 동시에 오류에도 강한 '초강력 암호 코드'를 실제로 만들 수 있게 되었습니다."

이 연구는 양자 컴퓨팅과 암호학이라는 두 개의 거대한 우주를 연결하는 다리를 놓아주었으며, 앞으로 더 안전하고 효율적인 디지털 보안 시스템을 만드는 데 큰 기여를 할 것으로 기대됩니다.

기술 요약

논문 요약: 제로-지식 (Zero-Knowledge) 코드와 양자 CSS 코드의 동치성

1. 연구 배경 및 문제 정의

이 논문은 암호학 및 양자 오류 정정 이론에서 각각 독립적으로 연구되어 온 두 가지 코드 계열인 제로-지식 (Zero-Knowledge, ZK) 코드와 양자 CSS (Calderbank-Shor-Steane) 코드 사이의 깊은 수학적 연결고리를 규명합니다.

• 제로-지식 (ZK) 코드: Decatur, Goldreich, Ron [DGR20] 이 도입한 개념으로, 인코딩된 메시지의 일부 시드 (few codeword symbols) 만으로는 원본 메시지에 대한 정보를 전혀 얻을 수 없는 오류 정정 코드입니다. 이는 정보 이론적 보안 (Information-theoretic security) 을 가진 다자간 계산 (MPC), 비밀 공유, 그리고 ZK-PCP/Interactive Oracle Proofs (IOPs) 와 같은 증명 시스템의 핵심 구성 요소로 널리 사용됩니다.
• 양자 CSS 코드: Calderbank, Shor [CS96] 과 Steane [Ste96] 이 제안한 양자 오류 정정 코드입니다. 두 개의 직교하는 고전적 선형 코드 ($C_X, C_Z$) 를 기반으로 하여 양자 상태를 오류로부터 보호합니다. 최근 양자 PCP 추측과 관련된 연구에서 중요한 역할을 하고 있습니다.

문제: 이 두 가지 코드 클래스는 서로 다른 응용 분야 (고전 암호학 vs 양자 컴퓨팅) 에서 사용되어 왔으나, 본질적으로 동일한 수학적 구조를 공유하는지 여부는 명확히 밝혀지지 않았습니다. 본 논문은 이 두 개념이 **동치 (Equivalent)**임을 증명하고, 이를 통해 새로운 코드 구성을 가능하게 하는 것을 목표로 합니다.

2. 방법론 (Methodology)

저자들은 ZK 코드와 양자 CSS 코드 사이의 변환 (Transformation) 메커니즘을 제시하여 두 코드가 서로 변환 가능함을 증명합니다.

• 정의 및 설정:

  • ZK 코드: $k'$-무작위 인코딩 맵을 가진 선형 코드 $C \subseteq \mathbb{F}^n$로 정의됩니다. 여기서 $m, m'$이 서로 다른 메시지일 때, 임의의 $t$개 이하의 위치 $I$에서 인코딩된 값의 분포가 동일해야 합니다 ($Enc(m)|_I \equiv Enc(m')|_I$).
  • CSS 코드: 두 선형 코드 $C_X, C_Z \subseteq \mathbb{F}^n$의 쌍으로, $C_X^\perp$와 $C_Z^\perp$가 서로 직교해야 합니다. 거리 $d_X, d_Z$는 각각 $C_X \setminus C_Z^\perp$와 $C_Z \setminus C_X^\perp$ 내의 최소 가중치 (weight) 로 정의됩니다.

• 핵심 변환 논리 (Theorem 3.1):

  1. ZK $\to$ CSS: 주어진 ZK 코드 $C$와 생성 행렬 $G$를 기반으로 $C_X = C$로 설정합니다. $C_Z$는 $G$의 마지막 $k-k'$ 열들이 생성하는 부분 공간에 직교하는 공간으로 정의합니다.
     • 이 변환에서 $C_Z \setminus C_X^\perp$의 가중치 조건이 ZK 코드의 **제로-지식 속성 (t-ZK)**과 대응됩니다.
     • $C_X \setminus C_Z^\perp$의 가중치 조건은 ZK 코드의 오류 정정 (decodable) 속성과 대응됩니다.
  2. CSS $\to$ ZK: 반대로, 주어진 CSS 코드 $(C_X, C_Z)$에서 $C = C_X$로 두고, $C_Z^\perp$의 기저를 $G$의 마지막 열들로 구성하여 ZK 인코딩 맵을 재구성합니다.

• 증명 전략:

  • ZK 속성을 행렬 $G$의 행 (rows) 의 선형 결합 관점에서 재정의합니다 (Lemma 3.3).
  • 임의의 $t$개 행의 선형 결합이 $G$의 특정 부분 (메시지 영역) 에서 0 이 아니면서 나머지 영역 (랜덤성 영역) 에서 0 이 되는 벡터를 생성하지 않는 조건이 ZK 속성과 동치임을 보입니다.
  • 이 조건이 CSS 코드의 거리 $d_Z > t$ 조건과 수학적으로 동일함을 증명합니다.

3. 주요 기여 (Key Contributions)

1. 동치성 증명 (Equivalence Theorem): 선형이고 완벽한 (perfect) ZK 코드와 양자 CSS 코드가 서로 변환 가능하며, ZK 코드의 거리 및 제로-지식 속성이 CSS 코드의 거리 ($d_X, d_Z$) 와 직접적으로 매핑됨을 엄밀하게 증명했습니다 (Theorem 3.1, Corollary 3.2).
2. 새로운 코드 구성의 가능성 제시: 이 동치성을 통해 양자 코드 이론의 최신 발전 결과를 고전적인 ZK 코드 구성에 적용할 수 있는 길을 열었습니다.
3. 명시적 점근적 우수 ZK-LTC 구성: 최근의 양자 국소 테스트 가능 코드 (Locally Testable Codes, LTC) 구성 결과를 활용하여, **명시적 (explicit)**이고 점근적으로 우수한 (asymptotically-good) ZK-LTC 를 최초로 구성했습니다.

4. 결과 (Results)

• Theorem 4.2 및 Corollary 4.3: 최근의 양자 LTC 구성 ([DLV24, KP25, WLH25]) 을 CSS 코드로부터 유도된 ZK 코드로 변환함으로써, 다음과 같은 특성을 가진 새로운 코드 계열을 얻었습니다:

  • 선형 비율 (Constant Rate): 코드의 효율성이 높음.
  • 선형 거리 (Linear Distance): 오류 정정 능력이 $O(n)$ 수준.
  • 국소 테스트 가능성 (Local Testability): $poly(\log n)$개의 쿼리로 코드의 유효성을 검증 가능.
  • 강력한 ZK 속성: 쿼리 복잡도보다 훨씬 큰 $O(n)$ 크기의 ZK 임계값 (threshold) 을 가짐. 즉, $O(n)$개의 시드만으로는 메시지에 대한 정보를 전혀 얻을 수 없음.

• 기존 연구와의 차별점: 기존에 Ishai et al. [ISVW13] 은 확률적 변환을 통해 ZK-LTC 를 구성했으나, 본 논문은 명시적 (explicit) 구성을 제공하며, ZK 임계값이 테스트 쿼리 수보다 훨씬 큰 (linear vs poly-log) 첫 번째 명시적 사례를 제시합니다.

5. 의의 및 중요성 (Significance)

• 이론적 통찰: 암호학 (ZK) 과 양자 정보 이론 (CSS) 이 서로 다른 분야로 보이지만, 실제로는 동일한 선형 대수적 구조 위에 있음을 보여줌으로써 두 분야의 연구 성과를 상호 융합할 수 있는 기반을 마련했습니다.
• 실용적 응용:
  • ZK-PCP 및 ZK-IOP: 효율적인 ZK 증명 시스템 설계에 필수적인 ZK-LTC 를 명시적으로 제공함으로써, 더 빠르고 안전한 증명 시스템 구축이 가능해집니다.
  • 양자 PCP 추측: 양자 CSS 코드와 ZK 코드의 연결은 양자 PCP 추측 연구에도 새로운 관점을 제공합니다.
  • 코드 설계의 혁신: 고전적인 오류 정정 코드 설계 기법을 양자 코드에, 그리고 양자 코드의 최신 발전 (예: LDPC 양자 코드) 을 고전 암호학 코드에 적용하는 교량 역할을 합니다.

결론적으로, 이 논문은 두 가지 중요한 코드 계열의 동치성을 증명함으로써 암호학 및 양자 컴퓨팅 분야의 코드 설계 패러다임을 변화시키고, 특히 명시적이고 효율적인 제로-지식 국소 테스트 가능 코드의 구성을 가능하게 한 획기적인 연구입니다.