Cycles of supersingular elliptic curves for pairing-based proof systems

디지털 세상에서, 비밀 자체를 드러내지 않고 자신이 그 비밀을 알고 있다는 것을 증명하는 것은 강력한 도구입니다. 이것이 현대 암호학의 핵심이며, 여기서 "증명 시스템(proof systems)"은 컴퓨터가 전체 계산을 다시 실행할 필요 없이 계산이 올바르게 수행되었음을 사용자에게 확신시킬 수 있게 해줍니다. 이러한 증명이 현실 세계에서 유용해지려면, 증명은 짧고 검증하기 빨라야 합니다. "간결한 비대화형 인자(succinct non-interactive argument)"라고 알려진 특정 유형의 증명은 이 기술의 초석이 되었습니다. 이러한 증명을 더욱 강력하게 만들기 위해, 연구자들은 하나의 증명이 다른 증명을 검증할 수 있도록 증명을 쌓아 올리는 방법, 즉 무한히 성장할 수 있는 신뢰의 사슬을 만드는 방법을 개발했습니다. "재귀(recursion)"라고 불리는 이 과정은 오늘날 사용되는 가장 진보된 프라이버시 및 확장 기술 뒤에 있는 엔진입니다. 그러나 이러한 사슬을 구축하려면 매우 특정한 종류의 수학적 토대, 즉 퍼즐 조각처럼 완벽하게 맞물리는 타원 곡선 쌍이 필요합니다. 수년 동안, 이 설명에 부합하는 알려진 조각들은 매우 희귀하고 찾기 어려우며 수적으로도 제한적이어서, 이 기술의 병목 현상을 만들어냈습니다.

연구팀은 이제 이러한 필수적인 곡선 쌍을 생성하는 새로운 방법을 발견하여, 이전에 접근할 수 없었던 방대한 공급원을 열어젖혔습니다. 그들은 "초특이 곡선(supersingular curves)"이라는 다른 클래스의 수학적 객체를 사용함으로써, 이러한 퍼즐 조각 쌍의 무한한 가족을 구축할 수 있다는 것을 발견했습니다. 특정 조건에 의존하여 새로운 쌍을 찾는 것이 운과 엄청난 계산적 노력에 달려 있었던 이전 방식과 달리, 이 새로운 접근 방식은 선택된 거의 모든 숫자에 대해 안정적으로 작동합니다. 연구진은 이러한 새로운 사이클을 구축하고 이를 다른 효율적인 곡선들과 연결하여 소위 "롤리팝(lollipops)"을 형성할 수 있음을 입증했습니다. 이러한 구조는 증명의 초기 단계인 무거운 작업은 작고 빠른 필드에서 수행하게 하고, 재귀적인 적층은 더 크고 안전한 사이클에서 수행할 수 있게 합니다. 실질적인 탐색 과정에서, 그들은 이 새로운 구조의 18가지 뚜렷한 사례를 성공적으로 구축하였으며, 이는 차세대 보안 디지털 시스템을 위한 유연하고 풍부한 자원을 제공합니다.

이 발견으로의 여정은 기존 기술의 한계에서 시작되었습니다. 현재의 재귀적 증명 시스템의 표준은 흔히 "사이클(cycle)"이라 불리는 두 타원 곡선의 특정 배치에 의존합니다. 이 배치에서는 첫 번째 곡선의 점의 개수가 두 번째 곡선을 정의하는 필드의 크기와 일치하고, 그 반대도 마찬가지입니다. 이 섬세한 균형은 증명이 한 곡선에서 다른 곡선으로 매끄럽게 전달되도록 합니다. 10년 넘게, 이러한 사이클을 구축하는 유일한 방법은 미야지(Miyaji), 나카바야시(Nakabayashi), 다카노(Takano)가 개발한 "보통(ordinary)" 곡선을 사용하는 것이었습니다. 이 방법은 이론적으로는 작동하지만, 실제로는 매우 희소합니다. 새로운 쌍을 찾는 것은 숫자들이 아주 정교하게 맞아야 하는 복잡한 수학 방정식을 푸는 것과 같습니다. 보안 요구 사항이 커짐에 따라, 유효한 쌍을 우연히 발견할 확률은 거의 제로에 가깝습니다. 이는 정밀한 기준을 충족하는 특정 모래알을 찾는 것과 같습니다. 해변은 무한하지만, 적절한 모래알은 극도로 희귀합니다. 이러한 희소성은 개발자들이 더 오래되고 덜 안전한 파라미터를 사용하거나, 짧고 제한된 사슬을 위해 무한한 재귀라는 이상을 포기하도록 강요했습니다.

연구자들은 병목 현상이 사이클이라는 개념 자체가 아니라, 사용되는 곡선의 특정 유형에 있다는 것을 깨달았습니다. 그들은 "초특이(supersingular)" 곡선에 주목했습니다. 이들은 일반적인 암호학에서는 덜 흔하지만, 이 특정 작업에 이상적인 독특한 속성을 지닌 다른 종류의 수학적 변종입니다. 트레이드오프는 이 곡선들이 약간 더 큰 수학적 필드 위에서 정의되어야 하므로 일부 계산이 조금 더 무거워진다는 점입니다. 그러나 그 이점은 압도적입니다. 새로운 구축 방식은 기본적인 소수 판별 테스트를 통과하기만 하면 선택된 거의 모든 숫자에 대해 작동합니다. 더 이상 희귀하고 운 좋은 숫자를 찾아 헤맬 필요가 없습니다. 연구진은 유효한 숫자라면 어떤 것이든 즉시 작동하는 초특이 곡선 쌍을 생성할 수 있음을 보여주었습니다. 이는 문제를 '보물 찾기'에서 '제조 공정'으로 변화시킵니다. 흩어져 있는 몇 개의 사례를 찾는 대신, 이제 주문에 따라 무한한 수의 이러한 사이클을 생산할 수 있습니다.

이 개념이 현실 세계에서 작동함을 증명하기 위해, 팀은 단순히 이론에만 의존하지 않고 구체적인 사례를 찾기 위한 검색 엔진을 구축했습니다. 그들은 "롤리팝"이라 부르는 구조를 구축하고자 했습니다. 캔디 케인을 상상해 보십시오. 막대 부분은 효율적인 곡선들의 사슬이고, 윗부분의 둥근 부분은 재귀적 사이클입니다. 막대는 증명이 작은, 빠른 필드에서 시작할 수 있게 하여 초기 계산 단계를 매우 빠르게 만듭니다. 둥근 부분인 사이클은 증명이 제한 없이 재귀적으로 쌓이고 검증될 수 있게 합니다. 연구진은 "펠 방정식(Pell equation)"이라고 알려진 특정 유형의 숫자 퍼즐을 해결함으로써 이러한 구조를 찾는 알고리즘을 개발했습니다. 그들은 강력한 컴퓨터를 사용하여 수백만 개의 가능성을 탐색하며 이 알고리즘을 실행했습니다. 검색은 성공적이었습니다. 그들은 80비트에서 128비트 이상까지의 보안 수준을 지원하는 다양한 크기의 18가지 뚜렷한 롤리팝 사례를 찾아냈습니다. 956비트 필드를 가진 하나의 거대한 사례는 실질적인 관심의 경계를 넓히며, 이러한 구조가 미래의 보안 요구 사항을 충족하기 위해 어떻게 확장될 수 있는지를 보여주었습니다.

이 발견의 의의는 설계자들에게 제공하는 유연성에 있습니다. 기존 방식에서 설계자들은 다른 옵션이 존재하지 않았기 때문에 종종 비효적인 특정 파라미터를 사용해야만 했습니다. 만약 더 높은 보안을 원한다면, 더 느린 성능이나 더 작은 재귀 한계를 받아들여야 했습니다. 새로운 초특이 사이클을 통해, 설계자들은 계산이 특히 빠른 필드나 하드웨어 가속에 도움이 되는 특정 속성을 가진 필드와 같이 속도에 최적화된 파라미터를 선택할 수 있습니다. 또한, 이들은 이러한 사이클을 페어링 친화적(pairing-friendly)이지는 않지만 증명의 초기 단계에 매우 효율적인 다른 유형의 곡선들과 연결할 수도 있습니다. 특정 애플리케이션을 위해 맞춤형 "롤리팝"을 생성하기 위해 구성 요소들을 혼합하고 조합할 수 있는 이 능력은 이전 기술로는 불가능했습니다. 연구진은 새로운 곡선들이 일부 부분에서 약간 더 크지만, 나머지 시스템을 최적화할 수 있는 능력과 가용한 사이클의 풍부함이 그 트레이드오프를 충분히 가치 있게 만든다고 언급했습니다.

논문은 이것이 건설적인 돌파구임을 강조하며 끝을 맺습니다. 연구진은 단순히 이러한 사이클이 존재함을 증证明했을 뿐만 아니라, 이를 구축할 수 있는 도구와 18개의 작동하는 사례 목록을 제공했습니다. 그들은 다음 단계가 실제 소프트웨어에 이러한 새로운 사이클을 구현하여 정확한 성능 이득을 측정하는 것이며, 이론적인 이점이 더 큰 필드로 인한 실질적인 비용과 비교 검토되어야 함을 인정합니다. 그러나 문은 이제 열렸습니다. 재귀적 증명 시스템의 성장을 제한했던 희소성이 제거되었습니다. 초특이 곡선으로 전환함으로써, 연구진은 더 안전할 뿐만 아니라 현실 세계의 다양한 요구에 더 잘 적응할 수 있는 증명 시스템을 위한 무한한 수학적 빌딩 블록의 공급원을 제공하였습니다.