Constant-time decoding of Gabidulin codes and their generalizations with application to RQC

제목: Gabidulin 부호 및 그 일반화된 형태의 상수 시간 디코딩과 RQC에 대한 응용

저자: Nicolas Aragon, Chloé Baïsse, Anthony Fraga, Philippe Gaborit, 그리고 Ilaria Zappatore (XLIM, CNRS UMR 7252, Université de Limoges)

1. 문제 정의

Gabidulin 부호는 Reed-Solomon 부호의 랭크(rank) 메트릭 아날로그이며, RQC(Rank Quasi-Cyclic) 및 Loidreau 암호 체계를 포함한 여러 효율적인 랭크 기반 암호 체계의 기초가 됩니다. 이러한 암호학적 유용성에도 불구하고, 실질적인 배포 측면에서는 중요한 격차가 존재했습니다. 즉, Gabidulin 부호 디코딩을 위한 **상수 시간 구현(constant-time implementation)**이 존재하지 않았습니다.

포스트 양자 암호 맥락, 특히 NIST 표준화 프로세스 이후에는 타이밍 부채널 공격(timing side-channel attacks)을 방지하기 위해 상수 시간 실행이 필수 요구 사항입니다. 이전의 RQC 구현들은 "거의" 상수 시간이었으나, 구체적으로 Gabidulin 부호의 디코딩이 Loidreau 알고리즘의 유클리드 나눗셈 단계와 같은 가변 시간 연산에 의존한다는 문제가 있었습니다. 또한, 최근의 RQC 개선안은 더 작은 파라미터 크기를 달enc하기 위해 증강 Gabidulin (AG) 부호(제로 열이 추가된 Gabidulin 부호)와 블록 단위 에러를 활용합니다. 그러나 이러한 특정 AG 부호를 위한 상수 시간 디코딩 알고리즘은 존재하지 않아, 이 암호 체계들의 안전한 실세계 개발을 저해해 왔습니다.

2. 방법론

저자들은 AG 부호의 상수 시간 디코딩을 달성하기 위해 알고리즘적 축소(algorithmic reduction)와 저수준 구현 최적화를 결합한 종합적인 솔루션을 제안합니다.

알고리즘적 축소:
핵심적인 이론적 기여는 AG 부호 디코딩 문제를 표준 Gabidulin 디코딩 문제로 축소하는 것입니다.

• 서포트 소멸 복구 (Support Erasure Recovery): AG 부호는 표준 Gabidulin 부호에 제로 열을 추가하여 구성됩니다. 저자들은 수신된 벡터의 구조를 활용하는데, 여기서 마지막 $n-n'$ 성분은 제로 패딩된 위치에서의 에러에 해당합니다. 이 "서포트 소멸"(이 에러 성분들이 생성하는 부분 공간)을 복구함으로써, AG 디코딩 문제를 길이가 더 짧고($n'$), 차원이 증가하며($k+\varepsilon$), 에러 랭크가 감소한($t-\varepsilon$) 표준 Gabidulin 디코딩 문제로 변환할 수 있습니다.
• 복잡도 감소: 이 축소 방식은 AG 부호 디코딩 문제를 재구성 단계에서 Loidreau 알고리즘을 사용할 수 있는 문제로 변환합니다. 기존의 AG 부호 접근 방식들이 지수적 또는 높은 다항식 복잡도를 갖는 거대 선형 시스템을 푸는 데 의존했던 반면, 이 방법은 이차 복잡도($O((n-n')^2)$)를 달성합니다.

상수 시간 구현:
타이밍 공격에 대한 저항성을 보장하기 위해, 저자들은 $q$-다항식 산술에 초점을 맞추어 RBC (Rank-Based Cryptography) 라이브러리를 수정했습니다.

• 고정 반복 횟수 (Fixed Iteration Bounds): (비밀 값인) $q$-다항식의 실제 차수에 의존하던 연산들을 고정된 상한값($max\_degree$)에 의end하도록 수정되었습니다.
• 상수 시간 좌측 나눗셈 (Constant-Time Left Division): 작업의 상당 부분은 $q$-다항식의 좌측 유클리드 나눗셈에 대한 상수 시간 버전을 만드는 데 할애되었습니다. 표준 알고리즘의 반복 횟수는 나머지의 차수에 따라 달라집니다. 저자들은 실제 업데이트가 필요하지 않을 때 "더미(dummy)" 연산을 수행하여 실제 차이를 마스킹하는, 항상 고정된 횟수($max\_A + 1$)만큼 실행되는 루프를 구현했습니다.
• 최적화: 상수 시간 실행을 보장하면서 효율성을 유지하기 위해 다음과 같은 몇 가지 최적화가 도입되었습니다:
  • $q$-차수와 선행 계수의 결합 계산.
  • 반복된 프로베니우스 자가 동형 사상(iterated Frobenius automorphism)의 상수 시간 역원 계산.
  • $q$-다항식에 단항식을 곱하는 전용 함수.
  • 불필요한 할당을 피하기 위한 몫(quotient)의 직접적인 계수 업데이트.

3. 주요 기여

1. 최초의 상수 시간 AG 디코딩: 본 논문은 현대적인 RQC 변형의 핵심 구성 요소인 증강 Gabidulin 부호를 위한 최초의 상수 시간 디코딩 알고리즘을 제시합니다.
2. 이차 복잡도 증명: 저자들은 AG 부호 디코딩이 Loidreau 알고리즘을 통해 해결 가능한 표준 Gabidulin 재구성 문제로 축소됨으로써 이차 복잡도로 달성될 수 있음을 증명하며, 이는 높은 복잡도의 선형 대수 접근법을 피하게 해줍니다.
3. 상수 시간 $q$-다항식 산술: 본 논문은 $q$-다항식의 완전한 상수 시간 연산, 특히 랭크 메트릭 디코딩의 병목 구간인 좌측 나눗셈에 대한 설명과 구현을 제공합니다.
4. 통합 및 벤치마킹: 제안된 알고리즘들은 RQC-Block-MS-AG 스킴에 통합되었습니다. 구현체는 타이밍 공격에 대해 검증되었으며 다른 포스트 양자 후보들과 비교되었습니다.

4. 결과

저자들은 Intel Core i7-13700 CPU에서 구현체를 평가했습니다.

• 원래 RQC 대비 성능: 새로운 상수 시간 RQC-Block-MS-AG 구현은 모든 연산(KeyGen, Encapsulation, Decapsulation)에서 원래의 RQC 구현(NIST 제안 모델)보다 우수한 성능을 보였습니다.
• HQC 대비 성능: NIST에 의해 선정된 Hamming-메트릭 기반 KEM인 HQC와 비교했을 때, RQC-Block-MS-AG 구현은 CPU 사이클 기준으로 약 4~5배 느립니다.
• 크기 트레이드오프: 성능 격차에도 불구하고, RQC-Block-MS-AG 스킴은 HQC보다 약 4배 작은 공개키 및 암호문 크기를 달성합니다.
• Extended Gabidulin (EG) 부호와의 비교: 저자들은 AG 디코딩 접근 방식을 EG 부호 디코딩과 비교했습니다. 결과에 따르면, 동일한 파라미터에 대해 AG 디코딩이 EG 디코딩보다 현저히 빠르며(곱셈 및 프로베니우스 연산 약 3배 적음, CPU 사이클 약 2배 적음), 이는 AG 부호의 특정한 구조가 복호화에 더 효율적임을 확인시켜 줍니다.
• 상수 시간 검증:
  • 타이밍 분석: 평균 디코딩 시간은 다양한 에러 가중치(0에서 36까지)에 대해 0.2% 미만으로 변동하여, 이전 알고리즘에서 발견되었던 에러 가중치와 실행 시간 사이의 상관관계를 제거했습니다.
  • Valgrind 분석: 데이터 포이즈닝(data poisoning)을 포함한 Valgrind의 memcheck 도구를 사용하여, 구현체에 비밀 의존적 분기(secret-dependent branches)나 메모리 접근이 남아 있지 않음을 검증했습니다.

5. 의의 및 주장

본 논문은 랭크 메트릭 암호학의 결정적인 보안 병목 현상을 해결한다고 주장합니다. AG 부호를 위한 최초의 상수 시간 디코딩을 제공함으로써, 저자들은 RQC 암호 체계 및 그 변형들의 안전한 실세계 배포를 가능하게 합니다.

이 연구의 의의는 그것이 제공하는 트레이드오프에 있습니다. 구현이 주요 Hamming-메트릭 후보인 HQC보다 느리지만, 4배의 키 및 암호문 크기 감소를 제공합니다. 저자들은 이것이 대역폭이나 저장 공간이 제한된 환경에서 "매력적인 트레이드오프"라고 주장합니다.

또한, 본 논문은 AG 부호를 위해 개발된 기술들(특히 상수 시간 좌측 나눗셈 및 축소 전략)이 표준 Gabidulin 부호 디코딩을 최적화하는 데 직접 적용될 수 있음을 강조합니다(AG 디코딩이 Gabidulin 케이스를 일반화하기 때문). 저자들은 향후 연구에서 콤팩트한 파라미터를 유지하면서 성능을 더욱 향상시키기 위해 고차원 Gabidulin 부호에 대한 신드롬 디코딩(syndrome decoding)을 탐구할 수 있을 것이라고 제안합니다.