Public-Key Quantum Money and Fast Real Transforms

이 논문은 공개키 양자 화폐 (Public-Key Quantum Money) 및 실수 양자 변환 (Real Quantum Transforms) 분야에 대한 새로운 알고리즘과 구성을 제안합니다. 저자들은 Zhandry(2024) 가 제안한 기존 양자 화폐 방식을 기반으로 하되, 복소수 진폭을 사용하는 푸리에 변환 (Fourier Transform) 을 **실수 진폭을 갖는 하틀리 변환 (Hartley Transform)**으로 대체하는 혁신적인 접근을 취했습니다.

다음은 논문의 문제 제기, 방법론, 주요 기여, 결과 및 의의를 상세히 요약한 내용입니다.

---

1. 문제 제기 (Problem)

• 양자 화폐의 실용성 한계: Wiesner 의 사설 키 양자 화폐는 복제 불가 정리에 기반하지만, 모든 거래에 은행의 검증이 필요하여 비실용적입니다. Aaronson 이 제안한 공개키 양자 화폐는 누구나 검증할 수 있게 했으나, 기존 제안들은 대부분 해킹되었거나 비표준적인 암호학적 가정에 의존했습니다.
• Zhandry 방식의 한계: Zhandry 는 아벨 군 작용 (Group Action) 과 양자 푸리에 변환 (QFT) 을 기반으로 한 안전한 공개키 양자 화폐를 제안했습니다. 그러나 이 방식은 **복소수 진폭 (Complex Amplitudes)**을 사용합니다.
• 실수 진폭의 필요성: 저자들은 실수 진폭을 사용하면 계산적 및 이론적 이점이 있을 수 있다고 주장합니다. 특히, 두 개의 실수 정규직교기저에 대한 특정 항등식 ($\sum |\phi_j\rangle|\phi_j\rangle = \sum |\psi_j\rangle|\psi_j\rangle$) 이 성립한다는 점은 복소수 기저에서는 일반적으로 성립하지 않으며, 이는 기존 Zhandry 방식의 보안 증명 (Quantum Lightning Scheme) 에서 발생하는 문제점을 해결할 수 있는 잠재력을 가집니다.
• 검증 알고리즘의 실패: 단순히 QFT 를 하틀리 변환 (QHT) 으로 교체하면, 기존 검증 알고리즘이 특정 위조 지폐를 구별하지 못해 위조 지폐를 100% 확률로 승인하는 치명적인 결함이 발생합니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 세 가지 핵심 기술적 요소를 결합하여 새로운 방식을 제안했습니다.

A. 하틀리 변환 (Hartley Transform) 기반 양자 화폐

• 기존 Zhandry 의 QFT 를 **양자 하틀리 변환 (Quantum Hartley Transform, QHT)**으로 대체합니다.
• 하틀리 변환은 $cas(x) = \cos(x) + \sin(x)$ 함수를 사용하여 정의되며, 모든 진폭이 실수가 됩니다.
• 이는 $H^2 = I$ (단위 변환) 성질을 가지며, 푸리에 변환과 유사한 산술적 성질을 갖습니다.

B. 그룹 액션 트위스트 (Group Action Twists) 를 활용한 새로운 검증 알고리즘

• QHT 를 도입하면 검증 과정에서 $|h\rangle$와 $|-h\rangle$가 중첩된 상태가 되어 기존 방식대로 시리얼 넘버를 추출할 수 없게 됩니다.
• 이를 해결하기 위해 그룹 액션 트위스트 (Twist) 개념을 도입합니다. 이는 $g * x \to (-g) * x$로 매핑하는 효율적인 연산입니다 (예: Isogeny 기반 암호에서 구현 가능).
• 새로운 검증 알고리즘 (Vernew):
  1. 지폐 상태가 유효한 공간에 있는지 확인.
  2. cmpIndex 알고리즘을 적용하여 시리얼 넘버 추출 시도.
  3. 측정 결과에 따라 $h$와 $-h$를 구별하는 프로젝션 수행.
  4. 트위스트 연산을 이용하여 $|Z(h)\rangle$와 $|Z(-h)\rangle$를 구별하는 추가 단계 (Lemma 7.2) 를 적용하여 위조 지폐를 차단합니다.

C. 연속 시간 양자 보행 (Continuous-Time Quantum Walks) 을 통한 시리얼 넘버 계산

• 기존 방식에서는 지폐 상태에서 시리얼 넘버를 직접 추출할 수 없었습니다.
• 저자들은 연속 시간 양자 보행을 사용하여 지폐 상태의 고유값을 추정함으로써 시리얼 넘버 $h$를 효율적으로 계산하는 새로운 알고리즘을 제안했습니다.
• 이는 Cayley 그래프 위의 양자 보행을 시뮬레이션하여 고유값 $\lambda_h = 2\cos(2\pi uh/N)$을 추정하고, 이를 통해 $h$를 복원하는 방식입니다.

D. 재귀적 양자 하틀리 변환 알고리즘

• 기존 QHT 알고리즘 (재귀적 분해 또는 QFT 기반) 보다 게이트 복잡도가 낮은 새로운 재귀적 알고리즘을 제안했습니다.
• 이 알고리즘은 QFT 와 유사한 재귀 구조를 활용하되, 하틀리 변환의 고유한 성질 ($cas$ 함수의 항등식) 을 이용하여 제어된 부등호 (controlled negation) 및 회전 연산을 최적화했습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 공개키 양자 화폐 체계: 하틀리 변환을 기반으로 한 최초의 양자 화폐 체계 제안. 이는 실수 진폭을 갖는 양자 화폐의 가능성을 입증했습니다.
2. 검증 실패 해결을 위한 트위스트 기반 알고리즘: 실수 진폭으로 인한 검증 실패 문제를 그룹 액션의 트위스트 속성을 이용하여 성공적으로 해결했습니다.
3. 효율적인 시리얼 넘버 추출 알고리즘: 양자 보행 (Quantum Walks) 을 기반으로 한 시리얼 넘버 계산 알고리즘을 개발하여, 지폐 상태에서 시리얼 넘버를 효율적으로 추출하는 방법을 제시했습니다.
4. 최적화된 양자 하틀리 변환 알고리즘:
   • 기존 연구 [3, 22] 대비 게이트 복잡도가 약 1.25 배 낮아진 알고리즘을 제안했습니다.
   • 복잡도 분석: $O(\log^2 N)$ (정확히는 $2 \log_2 N + O(\log N)$).
   • 이 알고리즘을 서브루틴으로 사용하여 양자 사인 변환 (Quantum Sine Transform) 등 다른 실수 양자 변환도 효율적으로 구현 가능함을 보였습니다.

4. 결과 (Results)

• 보안성: 제안된 검증 알고리즘은 정당한 지폐는 높은 확률로 승인하고, 위조 지폐는 기각합니다. 특히 트위스트를 이용한 구별 과정은 $h$와 $-h$에 대한 정보를 효과적으로 분리합니다.
• 효율성:
  • 제안된 QHT 알고리즘은 기존 알고리즘보다 게이트 수가 적어 양자 회로의 깊이를 줄였습니다.
  • 시리얼 넘버 계산 알고리즘은 다항 시간 ($poly(\log N)$) 내에 실행 가능합니다.
• 실용성: 이산 사인/코사인 변환 등 다른 실수 변환들을 하틀리 변환을 통해 효율적으로 구현할 수 있음을 증명하여, 양자 신호 처리 및 암호학 전반에 실수 변환의 적용 가능성을 열었습니다.

5. 의의 및 중요성 (Significance)

• 이론적 혁신: 양자 화폐 분야에서 처음으로 **실수 진폭 (Real Amplitudes)**을 핵심 요소로 도입했습니다. 이는 양자 상태의 대칭성과 관련된 새로운 이론적 통찰 (예: 실수 기저 간의 항등식) 을 제공하며, 향후 양자 암호 프로토콜 설계에 새로운 방향을 제시합니다.
• 알고리즘 최적화: 하틀리 변환의 재귀적 구조를 활용한 효율적인 양자 회로 설계는 양자 컴퓨팅의 자원 소모를 줄이는 데 기여합니다.
• 암호학적 확장: Isogeny 기반 암호 등 특정 그룹 액션에서 트위스트 연산이 효율적으로 수행될 때, 이 방식이 실제 양자 화폐 시스템으로 구현될 수 있는 강력한 후보가 됩니다.
• 연구의 시작점: 이 논문은 실수 양자 변환을 양자 암호학 및 양자 컴퓨팅의 주요 도구로 활용하기 위한 기초 작업으로, 향후 더 많은 연구와 최적화를 유도할 것으로 기대됩니다.

요약하자면, 이 논문은 하틀리 변환을 도입하여 실수 진폭을 갖는 새로운 양자 화폐를 제안하고, 이를 위해 트위스트와 양자 보행을 활용한 혁신적인 검증 및 계산 알고리즘을 개발함으로써 양자 화폐의 보안성과 효율성을 동시에 향상시켰다는 점에서 의의가 큽니다.