기술 요약: AVX-512를 이용한 벡터화된 SQIsign 구현

문제 정의

SQIsign은 NIST 양자 내성 암호 표준화 과정에 제출된 유일한 아이소제니(isogeny) 기반 디지털 서명 방식이다. 이 방식은 초곡선(supersingular elliptic curves)의 엔도모피즘 링(endomorphism ring) 문제의 난이도를 바탕으로 매우 압축적인 키 및 서명 크기를 제공하지만, 현재 실질적인 배포는 계산 집약적인 서명 절차로 인해 제약을 받고 있다. 성능 병목 현상은 주로 "곡선 측(curve-side)" 계산에 존재하며, 여기에는 거대 소수체($\mathbb{F}_p$) 및 그 이차 확장체($\mathbb{F}_{p^2}$) 상에서의 광범위한 산술 연산, 타원 곡선 연산(점 배가 및 스칼라 곱셈), 그리고 주 극립 아벨 곡면(principally polarized abelian surfaces, PPAS) 상에서의 고차원 아이소제니 평가가 포함된다. 기존의 참조 구현들은 스칼라 산술에 크게 의존하며, 종종 쿼터니언 대수(quaternion algebra) 구성 요소에 GNU 다중 정밀도 산술 라이브러리(GMP)를 활용하는데, 이는 처리량(throughput)을 제한하는 원인이 된다.

방법론

본 논문은 AVX-512 정수 융합 곱셈-덧셈(Integer Fused Multiply-Add, IFMA) 명령어 집합 아키텍처를 활용하여 SQIsign의 "곡선 측" 구성 요소에 대한 최초의 포괄적인 벡터화 구현을 제시한다. 저자들은 쿼터니언 대수 구성 요소(IdealToIsogeny)는 스칼라 방식으로 유지되며 본 연구에서 최적화되지 않았음을 명시하면서, 모든 주요 알고리즘 계층에 걸쳐 SIMD(Single Instruction, Multiple Data) 병렬성을 활용하도록 계산 스택을 체계적으로 재설계하였다.

핵심 기술 전략

1. 유한체 산술 ($\mathbb{F}_p$ 및 $\mathbb{F}_{p^2}$):

   • 표현: 구현 방식은 유한체 원소를 5개의 51비트 림(limb)으로 분해하는 radix-$2^{51}$ 표현법을 채택한다. 이 크기는 IFMA 연산 중 오버플로를 방지하면서 지연된 리덕션(deferred reduction)을 위한 여유 공간을 확보하기 위해 64비트 레인의 하위 52비트 안에 들어가도록 선택되었다.
   • 병렬화: 단일 512비트 ZMM 레지스터 내에서 8개의 독립적인 유한체 원소를 동시에 처리하는 $(8 \times 1)$-방향 병렬화 전략이 채택되었다.
   • 확장: $\mathbb{F}_{p^2}$의 경우, 저자들은 알고리즘적 요구 사항(예: 배치 연산 대 내부 구성 요소 병렬성)에 따라 처리량과 레지스터 압박 사이의 균형을 맞추기 위해 세 가지 별도의 병렬화 패턴—$(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$, $(2 \times 4 \times 1)$—을 구현하였다.
   • 명령어: 설계는 vpmadd52luq 및 vpmadd52huq 명령어를 활용하여 8개의 병렬 $52 \times 52$-비트 곱셈을 실행하고 융합 곱셈-덧셈 기능을 수행함으로써, 몽고메리 곱셈(Montgomery multiplication) 및 캐리 전파(carry propagation)를 위한 명령어 수를 크게 줄인다.

2. 타원 곡선 연산:

   • 점 배가(Point Doubling): 저자들은 $x$-전용 좌표(Montgomery 곡선)와 전체 사영 좌표(Jacobian 및 Modified Jacobian) 모두에 대해 점 배가를 최적화하였다. $x$-전용 좌표의 경우, 데이터 흐름을 유지하기 위해 벡터화된 문맥에서 정규화(normalization) 단계를 일관되게 생략하며, 여러 점을 동시에 배가할 때만 정규화를 적용하여 병렬성을 극대화한다.
   • 스칼라 곱셈: 몽고메리 래더(Montgomery ladder), 3-점 래더(three-point ladder), 그리고 2차원 래더(LadderBiscalar)를 벡터화한다. 주요 기여 중 하나는 일반적인 $(A_{24}:C_{24})$ 파라미터 형식을 수용하는 재설계된 4-방향 벡터화 전략을 xDBLADD 함수에 적용한 것이며, 이는 이전의 벡터화 시도들이 가졌던 특수 형태 의존성을 회피한다.
   • 페어링(Pairings): 저자들은 기저 생성(basis generation)에 사용되는 Tate-Lichtenbaum 페어링 계산을 다룬다. 하나의 점 배가와 두 개의 미분 덧셈(differential additions)을 결합함으로써, 저자들은 필요한 페어링을 생성하기 위해 세 개의 4-방향 병렬 곱셈과 하나의 4-방향 병렬 제곱 연산을 사용하는 cubicalDBLADDADD 알고리즘을 구축하였다.

3. 아이소제니 평가:

   • 차원 1 & 2: 저자들은 아이소제니 평가에 배치(batching) 전략을 적용하였다. 점들을 순차적으로 처리하는 대신, AVX-512 레인에 걸쳐 여러 점의 좌표를 인터리빙(interleaving)하여 SIMD 곱셈기를 포화시킨다. 이 접근 방식은 4-아이소제니(타원 곡선)와 세타 좌표 산술을 사용하는 (2,2)-아이소제니(PPAS) 모두에 적용된다.

4. 아키텍처 맥락:

   • 본 논문은 AVX-512의 노후화에 대한 오해를 다루며, Intel의 차기 AVX10 아키텍처(2026년 말 예정인 revision 10.2)가 성능 코어와 효율 코어 모두에 이러한 기능을 표준화하여 장기적인 생존 가능성을 보장할 것임을 언급한다.

주요 기여

1. SQIsign 곡선 측 연산의 포괄적 벡터화: 본 연구는 소수체 산술, 이차 확장, 타원 곡선 연산(스칼라 곱셈 및 페어링 포함), 그리고 1차원 및 2차원 아이소제니 평가를 포함한 SQIsign의 "곡선 측" 구성 요소 전체를 AVX-512IFMA를 사용하여 벡터화한 최초의 작업이다. 쿼터니언 대수 구성 요소는 스칼라 방식으로 남겨져 있다.
2. x86-64 상의 확장된 벡터화 분석: NEON을 사용한 De Feo 등의 ARM 기반 벡터화 노력과 달리, 본 연구는 복잡한 스칼라 곱셈 전략과 세타 좌표 연산을 포함하여 x86-64 플랫폼 상에서 훨씬 더 넓은 범위의 함수를 탐구한다. 알고리즘 설계는 아키텍처 불가지론적(architecture-agnostic)으로 설계되어, ARM SVE나 RISC-V와 같은 다른 SIMD 플랫폼으로의 이전을 위한 토대를 제공한다.
3. 일반화 가능한 최적화: 점 배가, 배치 스칼라 곱셈, 벡터화된 세타-점 산술을 위해 개발된 기술들은 특정 SQIsign 변형에 국한되지 않고, 더 높은 차원의 아벨 다양체를 사용하는 다른 아이소제니 기반 암호 체계에도 적용 가능한 방법론적 기초로 제시된다.

실험 결과

구현체는 Ubuntu 24.04에서 실행되는 Intel Core i7-11700F CPU(2.50GHz)에서 벤치마크되었다. 결과는 64비트 림을 사용하는 Broadwell에 최적화된 공식 참조 구현과 비교되었다.

• 성능 이득:
  • 키 생성(Key Generation): $1.03\times$에서 $1.28\times$ 사이의 속도 향상.
  • 서명(Signing): $1.08\times$에서 $1.26\times$ 사이의 속도 향상.
  • 검증(Verification): $1.46\times$에서 $1.84\times$ 사이의 속도 향상.
• Qlapoti와 결합 시: Qlapoti 기술과 결합했을 때, 구현체는 NIST 보안 레벨 I에서 서명 시 $2.69\times$의 속도 향상과 검증 시 $3.18\times$의 개선을 달 achieves 한다.
• 검증 격차: 논문은 검증이 곡선 측 벡터화 연산만을 전적으로 사용하기 때문에 서명보다 더 큰 이득을 얻는다고 설명한다. 서명은 여전히 현재 스칼라 GMP(본 연구에서 최적화되지 않은 구성 요소)를 통해 실행되는 쿼터니언 대수 연산을 포함하기 때문이다.

의의 및 주장

저자들은 본 연구가 SIMD 벡터화가 양자 내성 아이소제니 기반 방식에 있어 중요하지만 아직 충분히 탐구되지 않은 최적화 차원임을 입증한다고 주장한다.

• 알고리즘적 발전과의 독립성: 이러한 최적화는 최근의 고수준 알고리즘 개선(예: Qlapoti 또는 Superglue)과 직교(orthogonal)한다. 이는 벡터화를 통한 성능 이득이 곱셈적(multiplicative)임을 의미하며, 미래의 프로토콜 수준 혁신이 이 벡터화된 기반 위에 적용되어 성능 개선을 배가시킬 수 있음을 시사한다.
• 장기적 생존 가능성: Intel의 차기 아키텍처(AVX10)에서 AVX-512 기능이 표준화됨을 강조함으로써, 저자들은 이러한 최적화 기술이 일시적인 해결책이 아니라 효율적인 아이소제니 기반 암호학을 위한 지속 가능한 경로라고 주장한다.
• 보편성: 본 방법론은 다양한 아이소제니 기반 구성(예: SQIsignHD, SQIsign2D-East, SQIPrime)에 적용 가능하다고 주장되는데, 이는 이들이 모두 최적화의 대상인 동일한 기초 프리미티브($\mathbb{F}_{p^2}$ 산술, 세타 좌표, 타원 곡선 연산)를 공유하기 때문이다.

본 논문은 "쿼터니언 측"이 SQIsign의 스칼라 병목 구간으로 남아있음에도 불구하고, "곡선 측"의 벡터화가 이론적 압축성과 실질적인 배포 효율성 사이의 간극을 크게 메워준다고 결론짓는다.