타원 곡선 아이소제니: 수학적 기반

체 k 위의 두 타원 곡선 E와 E' 사이의 아이소제니는 비상수 유리 사상 phi: E -> E'이며, 동시에 군 준동형입니다. 즉 E의 군 연산을 E'의 군 연산으로 보냅니다. 모든 아이소제니 phi에는 쌍대 아이소제니 phi_hat: E' -> E가 존재하며, phi_hat과 phi의 합성은 E에서 deg(phi)에 의한 곱셈과 같습니다. 아이소제니의 차수는 핵의 크기입니다. 차수 l인 아이소제니의 핵 크기는 l입니다. 아이소제니는 스칼라 곱셈의 일반화입니다. n에 의한 곱셈은 E에서 자기 자신으로 가는 차수 n^2의 아이소제니입니다. 유한체 위의 아이소제니는 유리 함수(다항식)로 표현되며 이를 효율적으로 계산할 수 있습니다.

Velu 공식(1971)은 E의 부분군 G가 주어졌을 때 아이소제니 phi: E -> E/G를 계산하기 위한 명시적인 공식을 제공합니다. 상 곡선 E/G = E'와 유리 사상 phi는 모두 G에 의해 완전히 결정됩니다. Velu 공식은 상 곡선의 계수와 유리 사상을 |G|와 같은 차수의 유리 함수로 계산합니다. 소수 l을 차수로 갖는 핵 부분군 G의 경우 아이소제니의 차수는 l이며 O(l)번의 연산으로 계산할 수 있습니다. sqrt-Velu 알고리즘(Bernstein 등, 2019)은 큰 l에 대해 이를 O(sqrt(l))번의 연산으로 줄여 CSIDH에서 큰 소수 아이소제니를 효율적으로 사용할 수 있게 합니다. Velu 공식은 모든 아이소제니 기반 암호의 계산 핵심입니다.

유한체 Fp 위의 타원 곡선은 아이소제니 그래프로 구성할 수 있습니다. 꼭짓점은 타원 곡선의 j-불변량입니다(동형까지 곡선을 결정하는 표준 불변량입니다). 변은 l-아이소제니입니다. 작은 소수 l에 대해 각 보통 곡선에는 정확히 l+1개의 나가는 l-아이소제니가 있습니다(l-비틀림 부분군의 구조에 따름). Fp 위의 l-아이소제니 그래프는 (l+1)-정규 그래프입니다. 이 그래프의 라마누잔 성질(팽창 그래프)로 인해 그래프 위의 무작위 보행은 빠르게 혼합됩니다. 이는 아이소제니 기반 암호의 보안 가정이 되는 난이도를 제공합니다. 길이가 O(log p)인 무작위 보행은 j-불변량에 대해 균등한 분포를 만듭니다.

Fp 위의 타원 곡선은 두 범주로 나뉩니다. 보통 곡선은 자명하지 않은 p-랭크를 가지며, p^2개의 동형류와 화산 구조(분화구와 바닥)를 갖는 복잡한 아이소제니 그래프를 이룹니다. 초특이 곡선은 p-랭크가 0이며 Fp2 위의 하나의 연결된 아이소제니 그래프에 모두 속합니다. Fp 위의 초특이 j-불변량의 수는 대략 p/12입니다. SIDH와 SIKE는 아이소제니 그래프가 강한 팽창 성질을 지닌 라마누잔 그래프이고 보행 방향을 드러낼 수 있는 화산 구조가 없기 때문에 초특이 곡선을 사용합니다. CSIDH도 초특이 곡선을 사용하지만 Fp2가 아닌 Fp 위에서 서로 다른 대수적 구조를 활용합니다.

아이소제니 기반 암호는 서로 관련된 두 가지 어려운 문제를 기반으로 합니다. 초특이 아이소제니 문제(SSIP): Fp2 위의 두 초특이 타원 곡선 E와 E'가 주어졌을 때 아이소제니 phi: E -> E'를 찾는 문제입니다. 계산적 초특이 아이소제니(CSSI) 문제: E, E' = phi(E), 그리고 phi의 차수가 주어졌을 때 phi를 찾는 문제입니다. SSIP에 대한 최선의 고전 알고리즘은 O(p^{1/4}) 시간에 실행됩니다. 최선의 양자 알고리즘(Tani의 클로 탐색)은 O(p^{1/6}) 시간에 실행됩니다. p = 2^{434}이면 이는 128비트 고전 보안 수준을 제공합니다. 이러한 양자 속도 향상은 RSA/ECC에 대한 Shor 알고리즘의 지수적 속도 향상보다 훨씬 작으므로 아이소제니 기반 방식은 양자 내성을 갖습니다.

SIDH(초특이 아이소제니 Diffie-Hellman)는 특수한 형태의 소수 p = 2^a * 3^b - 1을 사용합니다. 이 소수는 Fp2 위의 곡선 E가 2^a-비틀림 점(2^a * P = 0을 만족하는 점 P의 집합)과 접근 가능한 3^b-비틀림 점을 갖도록 합니다. 앨리스의 비밀값은 2^a-아이소제니 phi_A: E -> E_A이며, 그 핵은 2^a-비틀림의 무작위 원소가 생성합니다. 밥의 비밀값은 3^b-아이소제니 phi_B: E -> E_B입니다. 두 사람은 비틀림 점의 상을 교환합니다. 앨리스는 E_A와 phi_A(P_B), phi_A(Q_B)를 공개하고, 밥은 E_B와 phi_B(P_A), phi_B(Q_A)를 공개합니다. 이를 통해 각 당사자는 상대방의 곡선에서 아이소제니를 계산하여 동일한 공유 j-불변량에 도달할 수 있습니다.

타원 곡선의 자기준동형환 End(E)은 E에서 자기 자신으로 가는 모든 아이소제니(스칼라 곱셈 포함)의 환입니다. Fp 위의 보통 곡선에서 End(E)는 허수 이차체의 정입니다. 초특이 곡선에서 End(E)는 p와 무한대에서 분기하는 사원수 대수의 최대 정입니다. End(E)의 구조는 곡선을 동형까지 완전히 결정합니다. 자기준동형환 문제, 즉 주어진 E에서 End(E)를 계산하는 문제는 어렵다고 여겨집니다(초특이 곡선에서는 SSIP와 동등합니다). Castryck-Decru 공격은 SIDH 프로토콜에서 유출된 추가 정보를 이용하여 자기준동형환의 일부를 효율적으로 재구성하고 방식을 깨뜨렸습니다.

차수 l인 아이소제니 phi: E -> E'는 차수 l의 다항식으로 표현할 수 있습니다. 점의 역원이 같은 x 좌표를 갖는다는 사실을 이용한 대칭 최적화를 적용하면 차수 l/2의 다항식으로도 표현할 수 있습니다. 주어진 점 P에 대해 phi(P)를 계산하는 데는 Velu 공식을 사용하여 O(l)번의 곱셈이 필요합니다. l = 2^a가 약 2^216인 SIDH에서는 이 비용이 감당하기 어려워 보이지만, SIDH는 2^a-아이소제니가 a개의 개별 2-아이소제니 사슬로 분해될 수 있다는 사실을 활용합니다. 각 2-아이소제니는 계산 비용이 낮으며, a단계 사슬을 통해 2^a-아이소제니를 만들 수 있습니다. 3^b도 마찬가지입니다. sqrt-Velu를 사용하면 CSIDH에서 큰 홀수 소수 아이소제니를 O(l)이 아닌 O(sqrt(l))의 비용으로 계산할 수 있어 CSIDH를 실용적으로 사용할 수 있습니다.

SIKE(초특이 아이소제니 키 캡슐화)는 NIST PQC 후보였으며 4라운드까지 살아남았지만 결국 깨졌습니다. SIKE는 모든 NIST 후보 중 가장 작은 키 크기로 주목받았습니다. SIKEp434(NIST 보안 수준 1)의 공개 키는 374바이트였습니다. 비교하면 ML-KEM-512의 공개 키는 800바이트입니다. SIKE는 공유 비밀이 단일 j-불변량(약 430비트인 체 원소)에서 도출되기 때문에 이렇게 작은 크기를 달성했습니다. 그러나 이러한 소형화에는 대가가 따랐습니다. SIKE는 다른 후보보다 100~1000배 느렸습니다. Castryck과 Decru가 2022년 7월 노트북에서 수 분 만에 실행되는 고전적 공격으로 SIKE를 깨뜨리자, SIKE는 NIST 공모전에서 즉시 탈락했습니다.

아이소제니 기반 암호는 양자 이후 암호 접근 방식 중 독특한 위치를 차지합니다. 키 크기는 격자 기반 방식(ML-KEM: 800바이트 이상)이나 해시 기반 서명(SLH-DSA: 공개 키 32~49바이트, 서명 7856~49856바이트)보다 훨씬 작습니다. 성능은 모든 대안보다 훨씬 낮습니다(SIKE는 ML-KEM보다 100~1000배 느렸습니다). 보안 가정은 LWE(ML-KEM/ML-DSA에서 사용), SIS 또는 해시 함수와 구별되므로 암호학적 다양성을 제공합니다. 양자 이후 보안의 근거인 아이소제니 경로 문제에는 알려진 다항 시간 양자 알고리즘이 없지만, RSA/ECC는 Shor 알고리즘으로 완전히 깨집니다. SIKE가 고전적 공격으로 깨진 사례는 오랫동안 연구된 LWE 문제와 달리 아이소제니의 난이도가 아직 완전히 이해되지 않았음을 보여 줍니다.

SIKE가 공격으로 무너진 뒤에도 아이소제니 기반 암호는 활발한 연구 분야로 남아 있습니다. SQISign(짧은 사원수 및 아이소제니 서명)은 177바이트의 서명을 제공하는 아이소제니 기반 서명 방식입니다(ML-DSA의 보안 수준 2 서명은 2420바이트입니다). 이는 현재 알려진 가장 작은 PQC 서명입니다. SQISign은 주어진 두 초특이 곡선 사이에서 지정된 차수의 아이소제니를 계산하는 난제를 사용하며, 이 난제는 자기준동형환 문제로 정식화됩니다. FESTA(초특이 비틀림 공격을 이용한 고속 암호화)는 SIDH를 취약하게 만든 추가 비틀림 점 보조 데이터를 피하는 새로운 KEM 설계입니다. CTIDH(상수 시간 CSIDH)는 CSIDH의 성능을 개선합니다. 이러한 방식들 덕분에 SIKE가 탈락한 후에도 아이소제니 연구는 여전히 중요합니다.

타원 곡선 사이의 아이소제니란 무엇입니까?

아이소제니는 군 준동형인 유리 사상 phi: E -> E'이며, 그 차수는 핵의 크기와 같습니다. Velu 공식은 핵 부분군으로부터 상 곡선과 사상을 계산합니다. 아이소제니 그래프는 곡선을 꼭짓점으로, l-아이소제니를 변으로 구성하며 (l+1)-정규 라마누잔 그래프를 이룹니다. 초특이 곡선(SIDH/SIKE/CSIDH에서 사용)의 아이소제니 그래프는 강한 팽창 성질을 가집니다. SSIP와 CSSI 문제가 아이소제니 보안의 기반입니다. SIDH는 2-아이소제니와 3-아이소제니를 번갈아 사용하는 사슬과 비틀림 점 구조를 이용합니다. 자기준동형환 계산은 SSIP와 동등합니다. SQISign과 FESTA는 자기준동형환의 난이도를 이용하는 SIKE 이후의 활발한 연구 방향을 보여 줍니다.