On the Spectral theory of Isogeny Graphs and Quantum Sampling of Secure Supersingular Elliptic curves

이 논문은 양자 컴퓨팅을 활용하여 엔드모피즘 환 (endomorphism ring) 을 알 수 없는 안전한 초특이 타원곡선 (supersingular elliptic curves) 을 무작위로 샘플링하는 문제를 해결하기 위한 최초의 증명 가능한 양자 다항 시간 알고리즘을 제시합니다. 이는 아이소지니어 기반 암호학 (isogeny-based cryptography) 의 핵심적인 난제 중 하나를 해결하는 것으로, 신뢰할 수 있는 설정 (trusted setup) 없이도 CGL 해시 함수 및 관련 원시들을 안전하게 인스턴스화할 수 있게 합니다.

다음은 논문의 상세한 기술적 요약입니다.

1. 연구 배경 및 문제 정의

• 배경: 아이소지니어 기반 암호학 (예: CGL 해시 함수, CSIDH, VDF 등) 은 초특이 타원곡선 간의 아이소지니어 경로 찾기 문제의 난이도에 기반합니다. 특히 CGL 해시 함수는 초특이 $\ell$-아이소지니어 그래프에서의 무작위 보행 (random walk) 을 기반으로 정의됩니다.
• 핵심 문제: 이러한 암호 체계의 안전성을 보장하려면, 해시 함수의 시작점으로 사용되는 곡선 $E_0$의 엔드모피즘 환 $\text{End}(E_0)$가 알려져서는 안 됩니다. 만약 시작 곡선의 엔드모피즘 환이 알려져 있다면, 무작위 보행 경로를 역추적하여 엔드모피즘 환을 계산하고 충돌 (collision) 을 찾을 수 있기 때문입니다.
• 기존 한계:
  • 기존에는 안전한 곡선을 생성하는 효율적인 고전/양자 알고리즘이 존재하지 않았습니다.
  • 기존 제안들 (예: [KSS22], [BBD+24]) 은 휴리스틱 (heuristic) 에 의존하거나, 신뢰할 수 있는 설정 (trusted setup, 여러 참여자가 협력하여 곡선 생성) 을 필요로 했습니다.
  • 특히 $F_p$ 위에서 정의된 곡선이나 특정 오더 (order) 로 방향이 지정된 (oriented) 곡선을 생성하는 데는 신뢰할 수 있는 설정이 필수적이었습니다.

2. 주요 방법론 및 기술적 접근

저자들은 초특이 아이소지니어 그래프의 **스펙트럼 이론 (Spectral Theory)**과 **방향 지정 아이소지니어 (oriented isogeny) 에서 발생하는 군 작용 (group action)**을 활용하여 두 가지 양자 알고리즘을 개발했습니다.

A. 스펙트럼 분석 및 국소화 (Delocalization)

• 아이소지니어 그래프의 스펙트럼: 초특이 $\ell$-아이소지니어 그래프는 $(\ell+1)$-정규 람마주 (Ramanujan) 그래프이며, 헤케 연산자 (Hecke operators) 의 작용을 통해 대수적 구조를 가집니다.
• 고유벡터의 국소화 (Delocalization): 알고리즘의 안전성은 고유벡터가 그래프의 특정 소수 집합에 집중되지 않고 전체에 고르게 퍼져있는지 (delocalization) 에 달려 있습니다.
  • 주요 결과 1: 저자들은 Quantum Unique Ergodicity (QUE) 추측을 증명하고, 고유벡터의 완전한 국소화 (complete eigenvector delocalization) 에 대한 수치적 증거를 제시했습니다.
  • 최대 노름 (Sup-norm) bound: 고유벡터 $\phi_i$에 대해 $\|\phi_i\|_\infty \ll p^{-1/4+\epsilon}$임을 증명했습니다. 이는 고유벡터가 특정 곡선에 집중될 확률이 매우 낮음을 의미하며, 출력된 곡선이 무작위 분포에 가깝게 됨을 보장합니다.

B. 고유값 분리 (Eigenvalue Separation)

• $\epsilon$-분리 (Separation): 서로 다른 고유벡터들이 서로 다른 고유값 벡터 (spectral tag) 를 갖는지를 확인해야 합니다.
  • 주요 결과 2: 일반화된 리만 가설 (GRH) 하에서, 이전 연구들 ([Kan18], [KSS22] 등) 에서 휴리스틱으로 가정했던 것보다 더 강력한 $\epsilon$-분리 성질을 증명했습니다. 이는 양자 위상 추정 (Quantum Phase Estimation, QPE) 을 통해 고유벡터를 정확하게 식별할 수 있음을 수학적으로 보장합니다.

C. 제안된 알고리즘

1. 알고리즘 1 (전체 그래프 샘플링):

   • 원리: 연속 시간 양자 보행 (Continuous-time quantum walk) 과 $\epsilon$-분리 성질을 활용합니다.
   • 과정: 초기 상태 (초특이 곡선) 에서 시작하여 여러 소수 $\ell_i$에 해당하는 인접 행렬 $A_{\ell_i}$의 해밀토니안 시뮬레이션을 수행하고, 양자 위상 추정 (QPE) 을 통해 고유값을 측정합니다. 이 과정을 반복하여 고유벡터를 식별한 후, 해당 고유벡터의 성분으로 곡선을 샘플링합니다.
   • 특징: 명시적인 아이소지니어 경로를 생성하지 않으므로, 경로 저장 공격 (path-storing attack) 에 안전합니다.

2. 알고리즘 3 (방향 지정 곡선 샘플링):

   • 원리: 허수 이차 오더 $\mathcal{O}$에 대한 방향 지정 초특이 곡선들의 집합에 대한 클래스 군 (Class group) 작용을 활용합니다.
   • 과정: 푸리에 기저 상태 (Fourier basis states) 의 중첩을 준비하고, 위상 피드백 (phase-kickback) 과 양자 푸리에 변환 (QFT) 을 사용하여 군 인덱스를 중첩 상태로 계산한 뒤 측정합니다.
   • 특징: 임의의 허수 이차 오더 $\mathcal{O}$에 대해 균일하게 분포된 방향 지정 곡선을 생성하며, Vectorization 문제의 난이도에 기반한 보안을 제공합니다.

3. 주요 결과 및 복잡도 분석

• 알고리즘 1 의 복잡도:

  • 휴리스틱 버전: $\tilde{O}(\log^4 p)$의 양자 게이트 복잡도를 가집니다.
  • GRH 하의 증명 가능 버전: $\tilde{O}(\log^{13} p)$의 양자 게이트 복잡도를 가지며, 실행 시간과 보안에 대한 엄밀한 보장을 제공합니다.
  • 보안: 평균 사례에서의 엔드모피즘 환 문제 (EndRing) 의 난이도를 가정할 때, 출력된 곡선은 QPT(양자 다항 시간) 적대자에게 엔드모피즘 환을 계산할 확률이 무시할 수 있을 정도로 낮습니다.

• 알고리즘 3 의 복잡도:

  • 임의의 허수 이차 오더 $\mathcal{O}$에 대해 양자 다항 시간 내에 균일한 방향 지정 곡선을 샘플링합니다.
  • 보안은 클래스 군 작용에 대한 Vectorization 문제의 난이도에 기반합니다.

• 수치적 검증:

  • 저자들은 Sage 와 MATLAB 을 사용하여 다양한 소수 $p$와 $\ell$에 대해 고유벡터의 최대 노름과 고유값 분리 ($\epsilon$-separation) 를 계산했습니다.
  • 실험 결과는 국소화 추측과 $\epsilon$-분리가 GRH 하에서 예측된 대로 성립함을 보여주었습니다.

4. 의의 및 기여

1. 신뢰할 수 없는 설정 (Trustless Setup) 해결: 최초로 신뢰할 수 있는 설정 없이도 안전한 초특이 타원곡선을 생성하는 증명 가능한 양자 알고리즘을 제시했습니다. 이는 CGL 해시 함수, 커밋먼트 스키마, VDF 등 다양한 암호 원시들의 안전한 인스턴스화를 가능하게 합니다.
2. 휴리스틱 가정의 제거: 기존 연구들 (예: Kane, Sharif, Silverberg 의 양자 화폐 프로토콜 등) 에서 필수적이었던 휴리스틱 가정 (고유값 분리, 국소화 등) 을 GRH 하에서 엄밀하게 증명하거나, 더 강력한 조건으로 대체했습니다.
3. 스펙트럼 이론의 새로운 통찰: 초특이 아이소지니어 그래프에 대한 Quantum Unique Ergodicity 추측의 증명과 고유벡터의 완전한 국소화 결과는 수론 및 암호학 분야에서 중요한 이론적 기여입니다.
4. 실용적 적용 가능성: 알고리즘 3 은 CSIDH 및 CSI-FiSh 와 같은 기존 프로토콜에 필요한 방향 지정 곡선을 효율적으로 생성할 수 있는 방법을 제공하며, 상호작용형 양자 계산 검증 프로토콜과 결합하여 완전한 보안을 제공할 수 있음을 시사합니다.

결론

이 논문은 양자 알고리즘과 해석적 수론 (Analytic Number Theory) 을 결합하여, 아이소지니어 기반 암호학의 가장 근본적인 난제 중 하나인 "안전한 곡선 생성" 문제를 해결했습니다. 제안된 알고리즘들은 이론적으로 증명 가능한 보안을 제공하며, 향후 양자 내성 암호 표준화 및 구현에 있어 중요한 기반을 마련합니다.