Logarithmic Density of Rank $\geq 1$ and Rank $\geq 2$ Genus-2 Jacobians and Applications to Hyperelliptic Curve Cryptography

기술 요약: 계수(Rank) $\ge 1$ 및 $\ge 2$인 종수(Genus)-2 야코비안의 로그 밀도와 하이퍼엘립틱 곡선 암호학에 대한 응용

문제 정의
본 논문은 $\mathbb{Q}$ 위에서 정의된 종수-2 곡선의 야코비안(Jacobian)에 대한 모델-바일(Mordell–Weil) 계수의 정량적 분포를 다룬다. 모델-바일 정리는 야코비안 상의 유리수 점들의 군이 유한한 비틀림 부분군(torsion subgroup)과 계수 $r$을 갖는 자유 아벨 군(free abelian group)으로 분해됨을 보장하지만, 산술적 크기에 따라 정렬된 가계(family) 내에서 $r \ge 1$ 또는 $r \ge 2$인 곡선의 빈도를 이해하는 것은 산술 기하학의 핵심적인 과제로 남아 있다. 구체적으로, 저자들은 정수 위에로스틀라스 모델(integral Weierstrass model)의 나이브 높이(naive height)에 의해 정렬된 하이퍼엘립틱 곡선들에 대해 이러한 분포를 조사한다. 부차적인 목표는 분할된 야코비안(split Jacobians)을 가진 곡선을 중심으로 이차 및 이중 이차 트위스트(quadratic and biquadratic twists) 가계 내에서의 계수 분포를 분석하여, 레게브(Regev)의 이산 로그 문제(DLP)에 대한 양자 알고리즘에 대한 유용성을 평가하는 것이다.

방법론
저자들은 다음과 같은 기하학적, 해석적, 계산적 기법들을 결합하여 사용한다:

1. 기하학적 프레임워크 및 보편적 섹션(Universal Sections): 연구는 $y^2 + h(x)y = f(x)$ 형태의 정수 위로스틀라스 모델의 파라미터 공간을 활용한다. 저자들은 두 무한 원점(points at infinity)의 차이에 대응하는 보편적 야코비안 상의 보편적 섹션 $\alpha_{\text{univ}} = [\infty_+ - \infty_-]$를 정의한다. 그들은 이 섹션이 일반 파이버(generic fiber)에서 비틀림(torsion)이 아님을 증명한다.
2. 비틀림 로커스(Torsion Loci) 및 높이 경계: $\alpha_{\text{univ}}$가 비틀림 점(torsion point)으로 특수화되는 로커스가 높이가 낮은 차원을 가진 자리스키 닫힌 집합(Zariski-closed subset)임을 확립함으로써, 그리고 파탈트 높이(Faltings height)와 $\theta$-높이 비교를 사용하여 비틀림 부분군의 크기를 곡선의 높이에 따라 제한함으로써, 저자들은 이 섹션이 비틀림이 되는 곡선의 비율이 높이 경계 $X \to \infty$에 따라 0으로 수렴함을 보여준다.
3. 네론 특수화(Néron Specialization): 계수 $\ge 2$를 확립하기 위해, 저자들은 두 개의 독립적인 섹션(하나인 $\alpha_{\text{univ}}$와 특정 특수화를 통해 구성된 다른 하나)이 일반적으로 독립적인 두 파라미터 부가 가계(two-parameter subfamilies)를 구성한다. 그들은 네론의 특수화 정리를 적용하여, 거의 모든 특수화에 대해 계수가 최소 2 이상임을 보여준다.
4. 분할 야코비안 구성: 분할된 야코비안(엘립틱 곡선의 곱과 동형인 경우)을 가진 곡선들을 위해, 저자들은 글루잉 구성(gluing constructions, Gajović–Park 및 [33]을 따름)을 활용하여 분할된 야코비안의 계수와 구성 엘립틱 곡선들의 계수를 연결한다. 그들은 이 분할 곡선들의 이차 및 이중 이차 트위스트 가계를 분석한다.
5. 계산적 검증: 이론적 결과는 특정 가계(CM 곡선 및 분할 야코비안 곡선 포함)에서 섹션의 독립성을 검증하고 계수를 계산하기 위한 LMFDB 데이터베이스 검색 및 커스텀 스크립트(GitHub 저장소 이용 가능)를 통한 명시적 탐색에 의해 뒷받침된다.

주요 기여 및 결과

• 계수 $\ge 1$에 대한 로그 밀도: 저자들은 두 개의 유리수 무한 원점을 가지는(따라서 섹션 $\alpha_{\text{univ}}$의 존재를 보장하는) 종수-2 곡선의 부분집합이 높이에 의해 정렬된 정수 모델 가계에 대해 최소 $13/14$의 로그 밀도를 가짐을 증명한다. 이 섹션은 거의 모든 모델에서 비틀림이 아니므로, 이는 계수 $r \ge 1$인 곡선들에 대해 $13/14$라는 무조건적인 하한 밀도를 제공한다.
• 계수 $\ge 2$에 대한 로그 밀도:
  • 명시적인 두 개의 독립적인 유리수 섹션을 가진 부가 가계를 구성함으로써, 저자들은 계수 $r \ge 2$인 곡선들에 대해 최소 $5/7$의 무조건적인 로그 밀도를 입증한다.
  • 또한, 계수가 $\ge 2$인 분할 야코비안 곡선의 부가 가계를 식별하여, 최소 $2/21$의 로그 밀도를 도출한다.
• 트위스트 가계:
  • 완전한 유리수 2-토션(full rational 2-torsion)을 갖는 $E_1 \times E_2$에 동형인 분할 야코비안을 가진 종수-2 곡선들에 대해, 저자들은 버치-스위너튼-다이어(BSD) 추측을 가정할 때, 이중 이차 트위스트 가계가 계수 $\ge 2$인 곡들을 양의 비율($1/4$)로 포함함을 보여준다.
  • 야코비안이 $E^2$에 동형이고 $E$가 유리수 3-이소제니(3-isogeny)를 허용하는 곡선들에 대해, 저자들은 이차 트위스트 가계가 계수 $\ge 2$인 곡들을 양의 비율로 포함함을 무조건적으로 증명한다.
• 암호학적 함의: 본 논문은 레게브의 양자 알고리즘 맥락에서 "높은 계수 곡선 문제(High Rank Curve Problem)"와 "높은 계수 트위스트 문제(High Rank Twist Problem)"를 분석한다. 레게브의 알고리즘은 유리수 리프트(rational lift) 또는 호환 가능한 트위스트의 계수 $r$에 대해 $d = r + 2$라는 파라미터의 이득을 얻는다. 결과는 높은 계수를 가진 곡(또는 트위스트)을 찾는 것이 단순한 브루트 포스 탐색보다 훨씬 효율적임을 시사하며, 관련 높이 정렬에서 계수 $\ge 1$의 경우 복잡도가 $O(X^7)$에서 $O(X^{1/2})$로, 계수 $\ge 2$의 경우 $O(X^2)$로 감소함을 보여준다. 저자들은 $y^2 = x^5 + a$ 및 분할 야코비안 가계와 같이 하이퍼엘립틱 곡선 암호(HECC)에 사용되는 곡선들에 대한 고계수 트위스트의 명시적 사례를 제공하며, 계수 6에서 8 사이의 트위스트가 계산 가능한 탐색 공간 내에 존재함을 입증한다.

의의
본 논문은 나이브 높이에 의해 정렬된, 양의 모델-바일 계수를 갖는 종수-2 곡선의 로그 밀도에 대한 최초의 무조건적 하한을 제공한다. 이는 랜덤 행렬 모델(random matrix models)과 같은 휴리스틱 예측을 넘어 엄밀한 기하학적 증명으로 나아간 것이다.

그 의의는 두 가지 측면에서 중요하다:

1. 산술 기하학: 본 연구는 높은 계수의 곡들이 기존에 정량화되었던 것보다 훨씬 더 조밀하다(로그 의미에서)는 것을 보여줌으로써, 높은 계수의 곡들의 존재와 밀도를 정량적인 방식으로 해결한다. 계수 $\ge 2$인 명시적인 부가 가계를 구성하는 것은 이러한 곡들의 구체적인 출처를 제공한다.
2. 암호 해독: 본 결과는 레게브의 양자 알고리즘에 대한 하이퍼엘립틱 곡선 암호의 보안 분석에 직접적인 영향을 미친다. 높은 계수의 트위스트와 리프트의 풍부함을 정량화함으로써, 본 논문은 높은 계수 구조가 존재하는 곡들에 대해, 해당 특정 양자 공격에 대한 유효 보안이 예상보다 낮을 수 있음을 시사한다. 즉, 파라미터 $d$를 증가시켜 양자 회로 크기를 줄일 수 있기 때문이다.

저자들은 암호학적 함의에 대해 겸허한 어조를 유지하며, 본 연구가 안전한 곡 선택을 위한 권고가 아니라 레게브 방식의 공격을 위한 입력값으로서 적합한 곡들을 식별하는 것임을 명확히 한다. 그들은 이러한 구조들이 높은 계수의 전처리를 용이하게 하지만, 이것이 일반적인 종수-2 야코비안에 대해 기존 방법보다 더 빠른 이산 로그 알고리즘을 현재로써 의미하는 것은 아니며, 단지 특정 양자 공격을 더 실행 가능하게 만든다는 점을 강조한다.