POKEx: Performance analysis of POKE-key exchange and SIDH-variants

인터넷이 사람들이 서로 비밀 편지를 주고받는 거대하고 북적이는 도시라고 상상해 보세요. 이 편지들을 도둑들로부터 안전하게 지키기 위해 우리는 "자물쇠"라고 불리는 암호화(encryption)를 사용합니다. 수십 년 동안 가장 좋은 자물쇠들은 한 방향으로는 수행하기 쉽지만 거꾸로 되돌리기는 매우 어려운 수학 문제, 예를 들어 색을 섞는 것과 같은 문제들을 사용하여 만들어졌습니다. 하지만 과학자들은 미래에 초강력 컴퓨터(양자 컴퓨터라고 불리는)가 이러한 자물쇠들을 순식간에 풀어버려 우리의 비밀을 무방비 상태로 만들 것을 우려하고 있습니다. 이를 막기 위해 연구자들은 "이소제니(isogeny)"라는 특별하고 아름다운 수학 분야를 기반으로 한 새로운 자물쇠를 만들고 있습니다. 이소제니를 도형(수학적 곡선)들을 연결하는 특별한 종류의 다리라고 생각해 보세요. 이 자물쇠의 비밀은 그 다리를 건너는 특정한 경로입니다. 오랫동안 가장 인기 있었던 다리 설계는 SIDH라고 불렸습니다. SIDH는 자물쇠의 크기가 작고 빠르다는 점 덕분에 우리의 미래 디지털 세계를 보호할 강력한 후보로 꼽혔습니다.

하지만 2023년, 한 쌍의 연구자들이 SIDH 다리를 부술 수 있는 영리한 트릭을 발견했습니다. 그들은 다리 설계자들이 실수로 경로의 지도를 누구나 볼 수 있게 노출했다는 사실을 찾아냈고, 이로 인해 몇 초 만에 비밀 경로를 알아낼 수 있었습니다. 이는 엄청난 타격이었는데, 가장 유망했던 "양자 내성" 자물쇠가 사실은 깨져 있었다는 것을 의미했기 때문입니다. 그 이후로 과학자들은 지도를 더 잘 숨길 수 있는 새로운 다리를 만들기 위해 분투해 왔습니다. 어떤 이들은 지도 위에 담요를 덮어 가리는 방식(마스킹)을 시도했고, 다른 이들은 다리를 다른 재료로 만드는 방식을 시도했습니다. 남은 큰 질문은, 우리가 깨지지 않으면서도 현실 세계에서 사용할 수 있을 만큼 빠른 다리를 구축할 수 있는가 하는 점이었습니다.

"POKEx"라는 제목의 이 논문은 이 혼란스러운 건설 현장에 뛰어들어 POKÉ라는 이름의 새롭고 반짝이는 다리 설계를 테스트합니다. 저자인 김현학(Hyeonhak Kim)과 김수리(Suhri Kim)는 POKÉ 암호화 방식을 완전한 키 교환 시스템(그들이 POKEx라고 부르는 것)으로 발전시키기로 결정하고, 이를 무너진 SIDH 다리를 대체하려는 다른 최고의 후보들과 경주하게 했습니다. 그들은 단순히 추측만 한 것이 아니라, 이 시스템들의 작동하는 버전을 직접 구축하고 강력한 컴퓨터로 시간을 측정했습니다. 그들의 주요 발견은 현재 POKEx가 모든 이소제니 기반 다리들 중 가장 빠르고 효율적이라는 것입니다. 테스트 결과, POKEx는 차순위 대안인 terSIDH보다 약 21배 더 빨랐으며, 또 다른 인기 있는 설계인 CSIDH보다는 거의 65배 더 빨랐습니다. 비록 다른 유형의 양자 내성 자물쇠들보다는 여전히 느리지만, 그 속도와 작은 크기는 POKEx가 인터넷을 느리게 만들지 않으면서도 우리의 디지털 비밀을 안전하게 지킬 수 있는 매우 유망한 후보임을 보여줍니다.

부서진 다리와 새로운 해결책의 이야기

이 논문이 왜 중요한지 이해하려면 먼저 "다리" 문제를 살펴봐야 합니다. 암호학의 세계에서 "키 교환(key exchange)"은 두 사람이 비밀을 입 밖으로 내지 않고도 비밀번호를 합의하는 것과 같습니다. 오랫동안 SIDH 시스템은 스타 플레이어였습니다. 이 시스템은 초곡선 타원 곡선(supersingular elliptic curves)—수학적 우주에 존재하는 복잡하고 구불구불한 모양이라고 생각하세요—을 사용했습니다. SIDH의 마법은 이 곡선 위의 특정 랜드마크와 같은 "토션 포인트(torsion points)"를 사용하여 다리를 구축했다는 점에 있었습니다. 이 시스템은 매우 효율적이어서 작은 키(디지털 형태의 가볍고 작은 자물쇠)를 가졌고 매우 빨랐습니다.

하지만 SIDH 다리에는 치명적인 결함이 있었습니다. 다리를 건설하기 위해 시스템은 사용된 랜드마크(토션 포인트)에 대한 일부 정보를 공개해야 했습니다. 2023년, 카스트릭(Castryck)과 데크루(Decru)는 이 공개된 랜드마크들을 "카니의 글루 앤 스플릿(Kani's glue-and-split)"이라 불리는 영리한 수학적 트릭과 결합하여 비밀 경로를 재구성하는 방법을 찾아냈습니다. 그것은 마치 보물로 이어지는 빵부스러기 흔적을 남겨둔 것과 같았습니다. 이 공격이 발견되자, SIDH는 깨진 것으로 간주되어 미래의 인터넷 보안 후보 명단에서 제외되었습니다.

다리를 고치기 위한 경주

SIDH가 무너진 후, 암호학계는 포기하지 않았습니다. 그들은 SIDH를 대체할 새로운 다리들을 만들기 시작했습니다. 어떤 이들은 랜드마크를 무작위 노이즈로 덮어 가리는 방식(M-SIDH라고 불리는 방법)을 시도했습니다. 다른 이들은 "인공 방향성(artificial orientation)"(terSIDH)을 사용하여 다리의 모양 자체를 바꾸려고 했습니다. 또한, 동일한 공격의 영향을 받지 않는 다른 유형의 다리인 CSIDH도 있었습니다. 하지만 CSIDH는 자체적인 속도 문제가 있었습니다.

문제는 이 새로운 다리들이 너무 느리거나 너무 크다는 것이었습니다. 랜드마크를 노이즈로 덮는 방식은 보안을 유지하기 위해 훨씬 더 큰 숫자를 필요로 했고, 이는 자물쇠를 무겁고 느리게 만들었습니다. 다리의 모양을 바꾸는 방식(terSIDH)은 도움이 되었지만, 여전히 위험할 수 있는 속도 편차를 가지고 있었습니다. 커뮤니티에는 보안성과 속도를 모두 갖춘 해결책이 필요했습니다.

POKEx의 등장: 속도의 제왕

여기서 이 논문의 새로운 영웅인 POKEx가 등장합니다. POKEx는 최근 바소(Basso)와 마이노(Maino)가 제안한 POKÉ라는 체계에 기반하고 있습니다. 이 논문의 저자들은 POKÉ를 가져와 키를 생성하고 비밀을 안전하게 교환하는 데 필요한 모든 단계를 갖춘 완전한 키 교환 시스템으로 만들었습니다.

POKEx의 핵심 비결은 "랜드마크"를 처리하는 방식에 있습니다. 예전의 SIDH처럼 1차원 경로만을 사용하는 대신, POKEx는 "2차원 표현(two-dimensional representation)"을 사용합니다. 강을 건너는 것을 상상해 보세요. SIDH는 단 하나의 판자 위를 걷는 것과 같았습니다. 만약 누군가 당신이 어디를 밟는지 본다면, 당신의 경로를 알아낼 수 있습니다. 그러나 POKEx는 두 방향으로 동시에 움직일 수 있는 격자형 판자 위를 걷는 것과 같습니다. 이는 경로를 추측하기 훨씬 어렵게 만듭니다. 또한, POKEx는 다른 새로운 다리들이 훨씬 더 크고 느린 숫자를 사용해야 하는 것과 달리, 매우 빠른 계산을 가능하게 하는 특수한 형태의 수학적 필드(형태가 $2^a3^b5^c-1$인 소수)를 사용합니다.

대결의 결과: 숫자가 말해주는 것

저자들은 단순히 말로만 설명하지 않고, POKEx를 직접 테스트했습니다. 그들은 M-SIDH, terSIDH, CSIDH와 함께 POKEx를 실행할 소프트웨어를 구축했습니다. 그들은 모두 동일한 보안 수준(NIST 보안 레벨 1, 정부의 일급 비밀을 보호하는 표준)으로 설정하고 키를 교환하는 데 걸리는 시간을 측정했습니다.

결과는 놀라웠습니다.

• M-SIDH는 가장 느렸으며, POKEx가 순식간에 해내는 일을 하는 데 거의 190초가 걸렸습니다. 저자들은 이것이 실생활에서 사용하기에는 비현실적이라고 언급했습니다.
• terSIDH는 M-SIDH보다 훨씬 빨랐지만 여전히 약 6.5초가 걸렸습니다.
• CSIDH는 약 20초가 걸렸습니다.
• POKEx는 단 306.95 밀리초(약 0.3초) 만에 임무를 마쳤습니다.

이를 대조해 보면, POKEx는 terSIDH보다 21.21배 더 빨랐고, CSIDH보다는 64.97배 더 빨랐습니다. 이로써 POKEx는 현재 이소제니 기반 키 교환의 챔피언이 되었습니다.

완벽한가요?

이 논문은 이것을 "완벽한" 해결책이라고 부르지 않도록 주의를 기울이고 있습니다. POKEx가 이소제니 다리들 중에서는 가장 빠르지만, ML-KEM(테스트에서 단 0.10 밀리초가 걸림)과 같은 다른 유형의 양자 내성 자물쇠들에 비하면 여전히 훨씬 느립니다. 그러나 저자들은 중요한 절충점을 지적합니다. ML-KEM은 빠르지만, 그 "자물쇠"(공개 키와 암호문)가 매우 커서 인터넷 공간을 많이 차지합니다. 반면 POKEx는 매우 작은 키(공개 키가 324 바이트에 불과함)를 가지고 있어 대역폭을 적게 사용합니다. 인터넷 속도와 데이터 제한이 중요한 세상에서, 이 작은 크기는 엄청난 장점입니다.

결론

이 논문은 오래된 SIDH 다리는 부서졌지만, 새로운 안전한 다리로 가는 길은 열려 있음을 보여줍니다. POKEx는 현재 이소제니 제품군 중에서 가장 유망한 후보로, 높은 속도와 작은 크기라는 보기 드문 조합을 제공합니다. 이는 우리가 디지털 삶을 늦추지 않으면서도 양자 내성을 가진 자물쇠를 만들 수 있음을 증명합니다. 비록 다른 양자 내성 방식들의 속도를 따라잡기 위해 더 많은 작업이 필요하지만, 그 효율성은 POKEx가 시간만큼이나 데이터 공간을 절약하는 것이 중요한 상황에서 미래의 인터넷을 안전하게 지키는 필수적인 도구가 될 수 있음을 시사합니다.