Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings

기술 요약: Kani의 보조정리와 Bruhat-Tits 트리에서의 경로 찾기를 연결하여 초특이 엔도모피즘 환을 계산하기

문제 정의
본 연구가 다루는 근본적인 문제는 $\mathbb{F}_{p^2}$ 상에 정의된 초특이 타원 곡선 $E$의 엔도모피즘 환 $\text{End}(E)$를 결정론적으로 계산하는 것이다. 상염수(ordinary) 곡선의 엔도모피즘 환을 계산하는 것은 최근 GRH(일반화된 리만 가설)와 인수분해 오라클 하에서 다항 시간 알고리즘의 발전을 이루었으나, 초특이(supersingular) 사례는 여전히 도전적인 과제로 남아 있다. Kohel의 사이클 찾기 알고리즘과 같은 기존 접근 방식은 $O(p^{1+\epsilon})$의 시간을 소요한다. [EHL+20]과 같은 최근의 아지수법(subexponential) 알고리즘들은 휴리스틱에 의존하며 입력 순서가 Bass order여야 한다는 제약이 있다. 또한, 단일 비스칼라(non-scalar) 엔도모피즘을 찾는 것과 전체 환을 찾는 것 사이의 확률적 다항 시간 환원(reduction)은 존재하지만(예: [PW24]), 제한된 입력을 가진 결정론적 방법은 한정적이었다.

본 논문은 다음의 조건이 주어졌을 때 $\text{End}(E)$를 계산하는 결정론적 다항 시간 알고리즘을 제공하는 것을 목표로 한다:

1. 곡선 $E$.
2. 부분 순서(suborder) $O_0 \subset \text{End}(E)$를 생성하는 두 개의 비가환 엔도모피즘 $\alpha_1, \alpha_2$.
3. $O_0$의 축소 판별식(reduced discriminant) $\Delta$의 인수분해.

이 알고리즘의 복잡도는 $\log p$, 입력 엔도모피즘의 차수, 그리고 $\Delta/p$의 가장 큰 소인수에 대한 다항식이다.

방법론
저자들은 쿼터니언 대수의 **국소-전역 원리(local-global principle)**를 활용한다. $\text{End}(E)$는 $B_{p,\infty}$(즉, $p$와 $\infty$에서 분기되는 쿼터니언 대수)의 극대 순서(maximal order)이므로, $\text{End}(E)$를 전역적으로 결정하는 것은 $O_0$의 축소 판별식을 나누는 모든 소수 $q$에 대해 국소 완비(local completion) $\text{End}(E) \otimes \mathbb{Z}_q$를 결정하는 것과 같다.

방법론은 $O_0$가 maximal하지 않은 각 소수 $q \neq p$에 대해 두 가지 주요 단계로 진행된다:

1. 국소 확장 및 임베딩 (Local Enlargement and Embedding):

   • 알고리즘은 $O_0$의 $q$-maximal $q$-enlargement $O_q$($q$에서는 maximal이지만 다른 곳에서는 $O_0$와 동일한 순서)를 구성한다.
   • Voight의 기법을 사용하여, $O_q \otimes \mathbb{Z}_q$에서 $M_2(\mathbb{Z}_q)$로의 동형 사상 $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$를 계산하여, 국소 순서를 $GL_2(\mathbb{Q}_q)$의 Bruhat-Tits 트리의 루트(root)로 매핑한다.
   • 대상 $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$는 이 트리의 정점(vertex)이다. 목표는 루트에서 $\Lambda_E$까지의 경로를 찾는 것이다.

2. Bruhat-Tits 트리에서의 경로 찾기 (Path-Finding in the Bruhat-Tits Tree):

   • 거리 계산 (Distance Computation): 알고-리즘은 먼저 루트와 $\Lambda_E$ 사이의 거리 $r$을 결정한다. 이는 $q^r O_q \subset \text{End}(E)$를 만족하는 최소 정수 $r$을 찾는 방식으로 수행된다. 이는 엔도모피즘의 유리수 배가 정수(integral)인지 테스트하는 나눗셈 알고리즘(Proposition 2.7)에 의존한다.
   • 경로 복구 (Path Recovery): $r$을 알게 되면, 알고리즘은 $\Lambda_E$로 향하는 특정 경로(행렬 시퀀스)를 복구한다.
     • 일반적인 경우 (General Case): 단계별로 후보들을 테스트한다. 길이 $k$인 경로에 대해, 후보 경로를 따르는 maximal order들의 교집합에 해당하는 전역 순서를 구성한다. 그 후, 이 전역 순서가 $\text{End}(E)$에 포함되는지 확인하기 위해 나눗셈 알고리즘을 사용한다. 만약 포함된다면 경로는 계속되고, 그렇지 않으면 해당 브랜치는 가지치기(pruning)된다. 이는 유한한 maximal order들의 교집합이 최대 3개의 교집합으로 환원될 수 있다는 점(Tu의 정리)을 활용한다.
     • Bass의 경우 (Bass Case): $O_0$가 $q$에서 Bass order라면, 이를 포함하는 maximal order들은 트리 상에서 단순한 경로를 형성한다. 알고리즘은 이 경로를 따라 이진 탐색(binary search)을 수행하여 $\text{End}(E) \otimes \mathbb{Z}_q$를 효율적으로 찾아낸다.

3. 전역 재구성 (Global Reconstruction):

   • 모든 관련 $q$에 대해 국소 maximal order $\tilde{O}_q$가 식별되면, 이들을 원래의 순서 $O_0$와 결합하여 전역 maximal order $\text{End}(E)$를 형성한다.

핵심 기술 도구

• Kani의 보조정리와 고차원 이소제니 (Kani's Lemma and Higher-Dimensional Isogenies): 나눗셈 알고리즘(Proposition 2.7)의 핵심 엔진은 Kani의 보조정리이다. 이는 엔도모피즘을 정수로 나누는 문제를 고차원 설정(타원 곡선 곱 사이의 이소제니)으로 변환할 수 있게 한다. 이러한 유연성은 [Rob22]와 [PW24]에서 사용되었던 기술을 적용하여, Bruhat-Tits 트리를 결정론적으로 탐색하기 위해 필요한 powersmoothness 조건을 부과할 수 있게 한다.
• 교집합에 관한 Tu의 정리 (Tu's Theorem on Intersections): 본 논문은 $M_2(\mathbb{Q}_q)$ 내의 임의의 유한한 maximal order들의 교집합이 최대 3개의 교집합과 같다는 Tu[Tu11]의 정리를 활용한다. 이를 통해 복잡한 국소 순서들의 교집합을 테스트하기 위해 그에 대응하는 전역 순서를 구성하고, 이를 $\text{End}(E)$와 대조함으로써 대규모의 후보 집합을 동시에 배제할 수 있다.
• HD 표현 (HD Representation): 엔도모피즘은 "HD 표현"(torsion points 상의 이미지)을 사용하여 표현되며, 이는 효율적인 평가와 차수 분석을 가능하게 하여 결정론적 다항 시간 실행 시간에 필수적이다.

결과 및 복잡도
본 논문은 $\log p$, 입력 차수, 그리고 판별식의 인수분해에 대해 결정론적 다항 시간 내에 $\text{End}(E)$를 계산하는 알고리즘이 존재한다는 정리 1.1을 제시한다.

• 일반적인 경우: 복잡도는 $\Delta/p$를 나누는 소수의 개수와 가장 큰 소수에 비례한다. 나눗셈 알고리즘의 호출 횟수는 각 소수 $q$당 $4(e_q + 2)$로 제한된다 (여기서 $e_q = v_q(\text{discrd}(O_0))$).
• Bass의 경우: $O_0$가 $q$에서 Bass order인 경우, 이진 탐색을 통해 나눗셈 알고리즘 호출 횟수가 $4 \log_2(e_q + 1)$로 개선된다.
• 비교: 이는 Bass 제약을 요구하고 휴리스틱에 의존했던 [EHL+20]보다 개선된 결과이다. 또한, 비스칼라 엔도모피즘에 대한 오라클을 요구하지 않으며, 인수분해를 가정하더라도 [PW24]와 달리 결정론적이라는 점에서 차이가 있다.

의의 및 주장
저자들은 본 연구가 하위 링(subring)을 생성하고 이를 전체 링으로 확장하는 Kohel의 접근 방식을 완성하며, 이전의 방법들이 휴리스틱이거나 확률적이었던 것과 달리 결정론적인 솔루션을 제공한다고 주장한다.

• 암호학적 관련성: 초특이 엔도모피즘 환을 계산하는 것은 이소제니 기반 암호 체계(예: 2022년에 깨진 SIDH)의 보안의 중심이다. 엔도모피즘 환 계산의 어려움은 이러한 체계의 보안을 위한 필요 조건이다.
• 방법론적 발전: 본 논문은 SIDH를 깨고 초특이 곡선의 엔도모피즘 환을 계산하기 위해 개발되었던 고차원 이소제니(Kani의 보조정리를 통한) 기술을 초특이 곡선의 Bruhat-Tits 트리를 탐색하는 데 효과적으로 재용도화할 수 있음을 보여준다.
• 일반성: 입력 순서가 Bass order여야 했던 기존 알고리즘들과 달리, 이 방법은 일반적인 순서에 대해서도 작동하므로 초특이 엔도모피즘 환을 분석하는 데 더 강력한 도구를 제공한다.

논문은 마지막으로 $p=103$인 구체적인 예시를 제공하여, 순서를 확장하고, 거리를 계산하며, 전체 엔도모피즘 환을 재구성하기 위해 Bruhat-Tits 트리의 경로를 찾는 단계를 단계별로 보여주며 마무리된다.