아이소제니 기반 암호의 미래

2022년 7월 Castryck-Decru의 SIKE 파괴 공격은 아이소제니 분야를 크게 바꾸었습니다. 이 공격 전에는 아이소제니 기반 암호가 작은 키 크기, 활발한 표준화 노력, 성장하는 연구 공동체를 갖춘 유망한 양자내성 방향이었습니다. SIKE가 무너진 뒤 이 분야는 기반을 재검토해야 했습니다. 핵심 질문은 새로운 Richelot 아이소제니 기법이 등장한 이후에도 아이소제니 기반 암호의 어떤 부분이 여전히 어려운가였습니다. 현재로서는 SQISign에서 사용하는 자기준동형환 기반 난이도와 CSIDH의 가환 클래스 군 작용은 여전히 안전한 것으로 보입니다. 깨진 부분은 SIDH에 특유한 보조 비틀림 점 누출이지, 아이소제니 전반이 아닙니다.

SQISign(짧은 사원수 및 아이소제니 서명, De Feo et al., 2020)은 현재 알려진 가장 작은 양자내성 서명 방식입니다. 공개 키는 64바이트(초특이 j 불변량)이고, 서명은 레벨 1에서 177바이트입니다. 비교하면 ML-DSA(Dilithium)는 레벨 2에서 공개 키가 1312바이트이고 서명이 2420바이트입니다. SQISign의 보안은 Deuring 대응에 기반합니다. 주어진 두 초특이 곡선 사이에서 지정된 차수의 아이소제니를 계산하는 문제는 자기준동형환의 사원수 대수에서 아이디얼을 찾는 문제와 동등합니다. SQISign은 이 어려운 문제에 Fiat-Shamir 식별 방식을 적용하여, 응답 아이소제니를 압축한 표현으로 서명을 생성합니다.

SQISign의 작은 크기에는 심각한 성능 비용이 따릅니다. 서명하려면 사원수 대수에서 아이디얼을 아이소제니로 변환하여 큰 차수(약 p^{1/4})의 아이소제니를 계산해야 하므로 계산량이 매우 많습니다. 매개변수 집합에 따라 데스크톱 CPU에서 약 60~600초가 걸립니다. 검증은 더 빠른 약 200밀리초이지만, ML-DSA의 검증 시간인 마이크로초보다 여전히 훨씬 느립니다. SQISign 2.0(2023)은 알고리즘 개선을 통해 성능을 100배 향상하여 서명 시간을 1~10초로 줄였습니다. SQISign HD(고차수)와 다른 변형도 계속 최적화되고 있습니다. 목표 응용 분야는 IoT 인증서, 블록체인 데이터, 우주 통신처럼 대역폭이 매우 제한되고 계산 속도는 부차적인 사용 사례입니다.

FESTA(초특이 비틀림 공격을 통한 고속 암호화, 2023)는 SIDH 방식의 비틀림 점 누출을 피하도록 명시적으로 설계된 KEM입니다. 핵심 설계 통찰은 SIDH처럼 phi_A(P_B)와 phi_A(Q_B)를 공개하는 대신, 암호화 수행자의 공개 키가 상 곡선만 포함하도록 다른 아이소제니 구조를 사용하는 것입니다. 즉 비틀림 점의 상을 공개하지 않습니다. FESTA는 2^n-아이소제니를 변형된 방식으로 사용하여 상대방의 비틀림 기저 상 없이도 복호화할 수 있게 합니다. 초기 분석에 따르면 FESTA는 보조 정보 구조가 다르기 때문에 Castryck-Decru 공격에 저항하는 것으로 보입니다. FESTA는 유망한 방향이지만 더 많은 암호분석 검토가 필요합니다. SIKE가 예기치 않게 무너진 뒤 아이소제니 연구 공동체는 신중한 태도를 유지하고 있습니다.

SCALLOP(대형 지향 소수를 사용하는 확장 가능한 가환 작용, 2023)은 CSIDH의 양자 보안 약점을 해결합니다. 작은 512비트 소수를 사용하는 CSIDH는 Kuperberg의 준지수 알고리즘 때문에 양자 보안이 약 65비트에 불과합니다. SCALLOP은 다른 대수 구조를 사용합니다. 즉 큰 허수 이차 정수환에 의한 복소 곱셈을 갖는 곡선을 사용하며, 여기서 클래스 군은 Kuperberg 방식의 양자 공격에 저항하도록 특별히 설계되었습니다. SCALLOP은 CSIDH-5000보다 작은 매개변수 크기에서 128비트 양자 보안을 제공하는 더 큰 유효 클래스 군을 달성합니다. 대신 SCALLOP의 대수적 구성이 더 복잡하고 CSIDH보다 독립적인 분석을 덜 받았다는 단점이 있습니다.

아이소제니 방식은 고유한 작은 크기(SQISign의 177바이트 서명과 CSIDH의 64바이트 키)를 제공하고 격자 방식과는 다른 난이도 가정을 사용하므로, 심층 방어를 위해 아이소제니 구성 요소와 격자 구성 요소를 결합한 하이브리드 구성이 사용됩니다. 하이브리드 KEM에서는 ML-KEM-512 AND CSIDH-512로 캡슐화하고 두 비밀을 함께 해시합니다. 결합된 키를 얻으려면 ML-KEM(LWE 난이도)과 CSIDH(클래스 군 작용)를 동시에 깨야 합니다. 둘 중 하나라도 깨지지 않는다면 하이브리드는 안전합니다. 이 암호 민첩성 접근법은 단일 양자내성 기본 암호를 넘어 추가적인 보장을 원하는 조직을 위해 NIST와 NSA가 권장하고 있으며, 특히 양자 컴퓨터의 등장 시점을 확실히 예측하기 어려운 경우에 유용합니다.

아이소제니 기반 영지식 증명은 새롭게 떠오르는 연구 방향입니다. 두 곡선이 모두 주어졌을 때 phi: E -> E'를 찾는 아이소제니 경로 문제는 지식 증명 방식의 어려운 문제로 사용할 수 있습니다. 《E에서 E'로 가는 아이소제니를 알고 있다》를 증명하는 시그마 프로토콜을 사용하면 아이소제니를 공개하지 않고도 인증할 수 있습니다. Vero(2022)는 실용적인 아이소제니 기반 ZK 증명 시스템을 보여 줍니다. 이러한 ZK 증명은 명제가 단지 두 개의 j 불변량이므로 본질적으로 작지만, 현재는 실제 도입에 사용하기에는 너무 느립니다. 아이소제니 계산이 개선되면, 가정의 다양성이 중요한 경우 아이소제니 기반 ZK 증명이 격자 기반 또는 해시 기반 증명의 대안이 될 수 있습니다.

아이소제니 기법은 양자내성 암호에만 관련된 것이 아니라 고전적 타원 곡선 암호에도 활용됩니다. 타원 곡선의 점 개수를 세는 Schoof-Elkies-Atkin(SEA) 알고리즘은 아이소제니를 사용하여 프로베니우스 자취를 계산하고, 이를 통해 안전한 타원 곡선 매개변수를 효율적으로 생성합니다. 아이소제니는 ECDLP 계산을 위한 Pollard의 rho 알고리즘 개선에도 등장합니다. 지정된 위수를 갖는 곡선을 구성하는 CM(복소 곱셈) 방법은 본질적으로 아이소제니 객체인 클래스 다항식을 사용합니다. 아이소제니 기반 암호분석 도구(매끄러운 차수의 아이소제니 경로 찾기)는 숨은 함정문이 있는지 제안된 타원 곡선 매개변수를 평가하는 데 사용되며, 이는 Dual EC DRBG 우려와 직접 관련됩니다.

2024년 기준으로 NIST나 다른 주요 기관이 표준화한 아이소제니 기반 방식은 없습니다. NIST PQC 과정에서는 ML-KEM, ML-DSA, SLH-DSA, FN-DSA를 표준화했으며, 모두 격자 기반 또는 해시 기반입니다. NIST는 PQC 서명에 대한 2차 평가를 진행하고 있고, SQISign도 제출되었지만 성능 문제에 직면해 있습니다. 아이소제니 연구 공동체는 실용적인 서명 시간(1초 미만을 목표로 함)을 달성하는 더 성숙한 SQISign 3.0을 개발하기 위해 노력하고 있습니다. ISO와 ETSI는 어떤 아이소제니 방식도 표준화하지 않았습니다. 가까운 시일 내에 가장 가능성 높은 표준화 경로는 최소한의 서명 크기가 필요한 틈새 응용 분야를 위한 SQISign이며, 필수 기본 암호가 아닌 정보 제공용 표준이 될 가능성이 있습니다. 널리 도입되려면 성능이 10배 이상 향상되어야 합니다.

2024년 기준 아이소제니 기반 암호에서 활발히 연구되는 방향은 다음과 같습니다. (1) 서명 성능을 1초 미만의 실행 시간에 가깝게 개선하는 SQISign 변형(SQISign 2.0, HD, Fast SQISign). (2) CSIDH와 그 변형의 양자 보안 분석: Kuperberg 공격 추정치를 정밀화하고 해당 공격에 저항하는 대수 구조를 탐색합니다. (3) 새로운 난이도 가정: 초특이 자기준동형환 계산과 허수 이차 환 위의 모듈 문제를 연구합니다. (4) 아이소제니 기반 망각형 의사난수 함수와 개인정보 보호 프로토콜에의 응용. (5) 아이소제니 연산의 하드웨어 구현: FPGA 병렬성을 활용하여 CSIDH의 클래스 군 작용을 구현합니다. (6) 새로운 함수형 암호와 속성 기반 방식을 위해 아이소제니 기반 군 작용을 일반 군 작용 암호 프레임워크와 통합합니다.

SIKE 공격은 아이소제니 기반 암호를 완전히 포기해야 한다는 생각을 하게 만들 수도 있습니다. 하지만 암호학계는 정반대로 봅니다. 이 공격이 가치 있었던 이유는 어떤 구조가 안전하지 않은지(SIDH의 토션점 유출), 어떤 구조가 여전히 풀기 어려운지(자기준동형환, 류군 작용)를 밝혀냈기 때문입니다. 아이소제니를 연구하는 일은 여전히 중요합니다. 그 이유는 다음과 같습니다. (1) 양자 내성 암호의 다양성 — LWE가 깨지더라도 격자에만 의존하지 않는 보안 가정을 확보하면 시스템 전체의 위험을 줄일 수 있습니다. (2) 에스큐아이사인은 현재 경쟁 기술이 없는 독특하게 작은 서명을 제공합니다. (3) 아이소제니 기법은 타원곡선 암호해석과 매개변수 검증에 통찰을 제공합니다. (4) 수학적으로 아름답고 생산적입니다. SIKE 공격을 위해 개발된 도구는 다른 분야에서 사용되는 타원곡선 자기준동형환에 대한 이해를 직접적으로 높였습니다.

에스큐아이사인 서명의 기반이 되는 난이도 가정은 무엇입니까?

SIKE가 2022년에 공격받은 이후에도 아이소제니 암호는 서로 다른 난이도 가정을 바탕으로 계속 발전하고 있습니다. 에스큐아이사인은 자기준동형환 문제의 난이도에 기반하여 177바이트의 양자 내성 서명을 제공합니다. 이는 현재 알려진 것 중 가장 작으며, 성능도 향상되고 있어 1초 미만을 목표로 하고 있습니다. FESTA는 SIDH의 토션점 유출을 피하도록 키 캡슐화 메커니즘을 설계합니다. SCALLOP은 방향이 지정된 곡선을 사용해 128비트 양자 보안을 목표로 합니다. 아이소제니와 격자를 결합한 방식은 보안 가정의 다양성을 제공합니다. 현재 표준화된 아이소제니 방식은 없습니다. 에스큐아이사인의 표준화가 가까운 시일 내에 가장 가능성 높은 경로입니다. SIKE 공격은 아이소제니 프로토콜에서 무엇을 숨겨야 하는지에 대한 이해를 높였고, 타원곡선 암호학 전반에서 사용되는 새로운 수학적 도구를 만들어 냈습니다.