CSIDH: 가환 초특이 아이소제니

CSIDH(가환 초특이 등원 디피-헬먼, Castryck 외, 2018년)는 SIDH의 비틀림점 누출을 근본적으로 다른 대수적 구조를 사용하여 완전히 피하는 등원사상 기반 키 교환 방식입니다. CSIDH는 SIDH처럼 Fp2가 아니라 Fp 위의 초특이 곡선을 사용합니다. 보안의 난이도 가정은 클래스군 작용의 가환성입니다. 양측은 각자 공통의 시작 곡선에 비밀 클래스군 원소를 적용하고, 가환성에 의해 양측이 동일한 공유 곡선에 도달합니다. 보조 비틀림점 정보는 공개되지 않으며, 공개 키는 하나의 j-불변량일 뿐입니다. 이 설계는 SIDH에 대한 캐스트릭-드크루 공격을 견뎠습니다.

p = 3 mod 4인 Fp 위에서 초특이 곡선 E에는 특별한 자기준동형사상 pi(프로베니우스)가 존재하며, 자기준동형 대수에는 허수 이차 차수 Z[pi]가 포함됩니다. 아이디얼 클래스군 Cl(Z[pi])은 Fp 위의 초특이 곡선 집합에 자유롭고 추이적으로 작용합니다(동형까지). Cl(Z[pi])의 아이디얼 a는 곡선 E에 작용하여 새로운 곡선 a * E를 만들며, 이는 E[a]가 아이디얼 a에 대응하는 비틀림 부분군일 때 E/E[a]라는 곡선으로 계산됩니다. 이 작용은 가환적이므로 a * (b * E) = b * (a * E) = [ab] * E가 성립합니다. 이것이 CSIDH의 군 작용이며, 가환적인 디피-헬먼 유사 구조를 제공합니다.

CSIDH 키 교환은 다음과 같이 진행됩니다. 공개 매개변수: Fp 위의 초특이 곡선 E0과 작은 홀수 소수 l_1, ..., l_n입니다. 비밀 키: 앨리스는 각 a_i가 {-m, ..., m}에 속하는 무작위 작은 정수인 a = (a_1, ..., a_n)을 선택합니다. 밥은 b = (b_1, ..., b_n)을 선택합니다. 앨리스의 공개 키: E_A = [l_1^a_1 * ... * l_n^a_n] * E0입니다. 밥의 공개 키: E_B = [l_1^b_1 * ... * l_n^b_n] * E0입니다. 공유 비밀: 앨리스는 E_B에 자신의 비밀 지수를 적용하고, 밥은 E_A에 자신의 지수를 적용합니다. 가환성에 의해 양측은 모두 E_AB = [product(l_i^(a_i + b_i))] * E0을 얻습니다. 공유 비밀은 j(E_AB)입니다. 보조점은 공개되지 않습니다.

참조 CSIDH 구현은 p = 4 * l_1 * l_2 * ... * l_74 - 1을 사용하며, l_1부터 l_74까지는 처음 74개의 홀수 소수(3, 5, 7, ..., 373)입니다. 이로 인해 p의 크기는 약 512비트가 됩니다. 각 비밀 키 구성 요소 a_i는 {-5, ..., 5}에 속하므로 구성 요소마다 11가지 선택이 가능하고 구성 요소는 74개입니다. 클래스군의 위수는 대략 sqrt(p)이며, 키 공간의 크기는 11^74입니다. 각 등원사상 단계를 계산할 때는 각 소수 l_i에 대해 l_i-비틀림 부분군을 찾고 벨루 공식을 사용하여 l_i-등원사상을 계산합니다. sqrt-Velu를 사용하면 각 큰 소수 등원사상 단계에는 O(sqrt(l_i))번의 연산이 필요합니다. 최신 하드웨어에서 전체 키 교환에 걸리는 시간은 CSIDH-512의 경우 약 1~5밀리초입니다.

기존 CSIDH는 상수 시간이 아닙니다. 벨루 단계의 수가 비밀 키 값에 따라 달라지므로 타이밍 부채널을 통해 정보가 누출됩니다. CTIDH(상수 시간 ISOGENY 디피-헬먼, Bernstein 외, 2021년)는 고정 가중치 키 형식과 신중하게 설계된 상수 시간 등원사상 계산을 사용하여 이 문제를 해결합니다. CTIDH 비밀 키는 절댓값의 합이 고정된 벡터로 제한됩니다(예: sum |a_i| = 130). 등원사상 계산은 비밀 키 값과 관계없이 고정된 수의 단계로 진행되며, 비밀 지수가 0인 단계는 더미 등원사상 계산으로 채웁니다. CTIDH는 임베디드 환경에 적합한 엄격한 상수 시간 보장을 제공하면서 CSIDH-512와 유사한 보안을 달성합니다.

CSIDH의 양자 보안은 격자 기반 방식의 경우보다 더 미묘합니다. 현재 가장 강력한 양자 공격은 숨은 시프트 문제에 Kuperberg의 알고리즘(2005)을 사용하는 것으로, 준지수 시간 L(1/2) = exp(O(sqrt(log p)))에 클래스 군 작용 구조를 깨뜨립니다. 이는 고전적인 최선의 공격인 sqrt(p)보다 상당히 효율적이므로, 양자 컴퓨터가 고전적 공격자에 비해 CSIDH의 보안을 크게 약화시킨다는 뜻입니다. 128비트 양자내성 보안(L(1/2) 공격에 대한)을 달성하려면 CSIDH에는 약 5000비트 소수(CSIDH-5000)가 필요합니다. 이는 128비트 고전 보안에 필요한 512비트와 비교됩니다. CSIDH-512는 양자 보안 수준이 약 62~72비트로 추정되며, NIST 레벨 1 요구사항보다 훨씬 낮습니다.

CSIDH의 보안은 군 작용 역문제(GAIP)에 의존합니다. E_A = a * E0와 E0가 주어졌을 때 a를 찾는 문제입니다. 현재 알려진 최선의 알고리즘은 Pohlig-Hellman과 유사한 축약과 소단계-대단계 기법을 결합하며, 고전적으로 O(sqrt(|Cl|)) ~ O(p^{1/4})의 시간에 실행됩니다. 양자 환경에서의 난이도(Kuperberg) 때문에 CSIDH는 LWE 기반 방식보다 양자 보안성이 낮습니다. LWE의 최선의 양자 공격인 격자 체질은 더 보수적인 보안 여유를 제공합니다. CSIDH의 장점은 작은 크기입니다. CSIDH-512의 공개 키는 64바이트(j 불변량만 포함)인 반면, ML-KEM-512는 800바이트입니다. 가능한 가장 작은 키가 필요하고 더 낮은 양자 보안 여유를 받아들일 수 있는 응용 분야에서는 CSIDH가 여전히 흥미로운 선택입니다.

여러 CSIDH 변형이 CSIDH의 양자 보안 한계를 해결하고자 제안되었습니다. BSIDH(B는 better를 의미)는 더 높은 차수의 기본 곡선과 타원 곡선의 곱을 사용하여 계산 속도를 유지하면서 클래스 군의 크기를 키웁니다. Csurf(CSIDH on the surface)는 다른 초특이 곡선 집합을 사용하여 더 빠른 군 작용 계산을 가능하게 합니다. 고종수 CSIDH 제안은 Fp 위의 종수 2 곡선의 야코비안을 사용하여 더 큰 군 작용 공간을 제공하고, 잠재적으로 더 나은 양자 보안 여유를 확보합니다. 그러나 이러한 변형 중 널리 채택되거나 NIST의 검토 대상이 된 것은 아직 없습니다. 이는 부분적으로 CSIDH 변형의 양자 보안 분석이 아직 발전 중이며 격자 기반 방식에 비해 덜 성숙하기 때문입니다.

CSIDH와 SIDH는 근본적으로 다릅니다. 가환성: CSIDH는 가환 군 작용(클래스 군)을 사용하는 반면, SIDH는 보조 비틀림 점을 사용하는 비대화형 키 교환이며 아이소제니는 비가환적입니다. 기본체: CSIDH는 Fp 위에서 작동하고, SIDH는 Fp2(이차 확장) 위에서 작동합니다. 공개 키 크기: CSIDH는 Fp 위의 단일 j 불변량으로 64바이트인 반면, SIDH는 곡선과 두 개의 Fp2 점으로 324바이트 이상입니다. 보안: CSIDH는 Castryck-Decru 공격을 견뎠지만 SIDH는 깨졌습니다. 양자 보안: CSIDH가 128비트 양자 보안을 얻으려면 5000비트 소수가 필요하며, SIDH는 고전적 공격으로 깨지기 전에는 이에 필적하는 양자 저항성을 보였습니다. 성능: CSIDH-512는 약 1~5밀리초이며 SIDH도 비슷했지만, CSIDH-5000은 훨씬 느릴 것입니다.

CSIDH의 가환성은 비대화형 키 교환(NIKE)을 가능하게 합니다. Alice는 E_A = a * E0를 공개하고 Bob은 E_B = b * E0를 공개합니다. 이후 추가 통신 없이도 누구나 어느 공개 키에서든 공유 비밀을 계산할 수 있습니다. Alice는 a * E_B = a * (b * E0) = ab * E0를 계산하고, Bob은 b * E_A = b * (a * E0) = ab * E0를 계산합니다. 이 NIKE 속성은 상호 작용 방식의 키 교환이 실용적이지 않은 응용 분야에서 유용합니다. 예를 들어 발신자와 수신자가 동시에 온라인 상태가 아닌 이메일 암호화가 이에 해당합니다. CSIDH의 NIKE는 양자내성 방식이라는 점에서 Diffie-Hellman NIKE와 유사합니다. LWE에 기반한 ML-KEM은 추가 프로토콜 설계 없이는 자연스럽게 NIKE를 지원하지 않습니다.

CSIDH는 표준화되지 않았으며 아직 운영 시스템에 도입되지 않았습니다. CSIDH는 활발한 연구 주제이며 다음과 같은 구현이 제공됩니다. CTIDH(상수 시간), csidh-reference(교육용 Python 구현), supersingular-isogeny-toolbox(최적화된 C 구현)입니다. 도입의 가장 큰 장벽은 양자 보안입니다. CSIDH-512의 양자 보안 수준은 62~72비트로 추정되어 NIST 레벨 1(128비트)보다 낮으므로, NIST 준수가 필요한 양자내성 응용 분야에는 적합하지 않습니다. CSIDH-5000은 보안 기준을 충족하지만 훨씬 느릴 것입니다. 양자 보안 분석을 개선하고 그 격차를 줄이는 변형을 개발하기 위한 연구가 계속되고 있지만, 2024년 기준 CSIDH는 실제 도입이 가능한 기본 암호라기보다 연구용 시제품에 머물러 있습니다.

CSIDH는 프로베니우스 자기준동형인 pi가 정의하는 Fp 위의 초특이 곡선에 대해 Cl(Z[pi])의 가환 클래스 군 작용을 사용합니다. 공개 키는 단일 j 불변량이며 64바이트입니다. 보조 비틀림 점을 공개하지 않으므로 SIDH의 취약점을 피할 수 있습니다. 클래스 군 작용은 가환적이므로 NIKE가 가능합니다. 최선의 고전 공격은 O(p^{1/4})이고, 최선의 양자 공격(Kuperberg)은 준지수 시간 L(1/2)에 실행되므로 128비트 양자 보안을 위해서는 5000비트 소수가 필요합니다. CTIDH는 상수 시간 구현을 제공합니다. CSIDH-512의 양자 보안은 약 65비트에 불과합니다. CSIDH는 표준화되지 않았으며, 연구는 작은 키를 유지하면서 양자 저항성을 높이는 변형에 집중하고 있습니다.