Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS

이 논문은 제한된 증후군 복호 (Restricted Syndrome Decoding, ResSD) 문제와 이를 기반으로 한 포스트 양자 서명 체계인 CROSS의 보안성을 분석한 연구입니다. 저자들은 ResSD 문제를 기존 선형 부호 기반 문제 (Regular Syndrome Decoding) 와 격자 기반 문제 (Closest Vector Problem, List-SVP/CVP) 로 변환하는 새로운 방법론을 제시하고, 이를 통해 CROSS 의 공격 표면 (attack surface) 을 확장했습니다.

다음은 논문의 주요 내용을 기술적으로 요약한 것입니다.

---

1. 연구 배경 및 문제 정의

• 배경: NIST 의 포스트 양자 암호 표준화 과정에서 CROSS 는 제한된 증후군 복호 (ResSD) 문제를 기반으로 하는 서명 체계로, 2 차 라운드 후보에 선정되었습니다. ResSD 는 유한체 위의 선형 부호 복호 문제의 변형으로, 오류 벡터의 각 성분이 고정된 작은 집합 $E$에 속해야 한다는 추가 제약이 있습니다.
• 문제 정의 (ResSD): 주어진 패리티 체크 행렬 $H$와 증후군 $s$에 대해, $eH^T = s$를 만족하고 $e$의 모든 성분이 집합 $E$에 속하는 오류 벡터 $e$를 찾는 문제입니다.
• 현재 상황: CROSS 설계자들은 ResSD 를 해결하기 위해 기존 ISD(Information Set Decoding) 알고리즘의 변형이나 대수적 기법 (Gröbner basis) 을 주로 사용했습니다. 그러나 ResSD 는 상대적으로 새로운 문제이므로, 다양한 관점에서의 보안 분석이 필요했습니다.

2. 주요 방법론 및 기여 (Methodology & Contributions)

저자들은 ResSD 문제를 해결하기 위해 세 가지 주요 접근법을 제시하며, 이를 통해 기존 ISD 기반 분석을 넘어선 새로운 공격 경로를 개척했습니다.

A. ResSD 에서 Regular Syndrome Decoding (RegSD) 으로 축소

• 아이디어: ResSD 의 해를 구하기 위해, 원래의 패리티 체크 행렬 $H$를 직접 사용하는 대신 새로운 행렬 $H'$을 구성합니다. $H$의 각 열 $H_i$에 대해, 허용된 값 집합 $E=\{r_1, \dots, r_z\}$의 각 원소 $r_j$에 대해 $r_j H_i$를 열로 갖는 새로운 행렬을 만듭니다.
• Light-Regular Vector: 이 변환을 통해 ResSD 의 해는 각 블록에 정확히 하나의 1 을 갖는 'light-regular vector'로 변환됩니다. 이는 Regular Syndrome Decoding (RegSD) 문제의 특수한 형태입니다.
• 추가 제약: 각 블록의 합이 1 이 되도록 $n$개의 추가 패리티 체크 방정식을 도입하여, 해가 반드시 light-regular 형태가 되도록 강제합니다.
• 결과: 이 변환된 문제에 기존 ISD 알고리즘 (Permutation-based, Enumeration-based) 을 적용했습니다. 그러나 생성된 부호의 비율 (rate) 이 높아 복잡도가 크게 증가하여, 기존 CROSS 설계자가 제안한 직접적인 ISD 공격보다 효율적이지 않았습니다.

B. ResSD 에서 Closest Vector Problem (CVP) 으로 축소 (격자 기반)

• 아이디어: light-regular vector 는 유클리드 노름 (Euclidean norm) 을 최소화하는 해이기도 하다는 점을 이용합니다.
• 변환: ResSD 문제를 선형 부호에 대응되는 격자 (Lattice) 를 구성하고, 이를 CVP(가장 가까운 벡터 문제) 로 변환합니다. 이는 Lee 거리 기반의 격자 공격과 유사하지만, 더 높은 차원과 많은 수의 짧은 벡터를 포함합니다.
• 하이브리드 공격: 격자의 차원이 너무 커서 직접 해결하기 어렵기 때문에, '블록 추측 (guessing)' 기법을 사용하여 격자 차원을 줄이는 하이브리드 공격 (Hybrid-BatchCVP) 을 제안했습니다.
• 결과: 이 공격은 CROSS 매개변수에 대해 기존 메모리 없는 ISD 공격 (k 좌표 추측) 보다 효율적이지 않았습니다.

C. ResSD 에서 List-CVP/List-SVP 로 직접 축소 (Affine 변환 및 Truncation)

• 아이디어: ResSD 의 해 집합 $E$에 아핀 변환 (Affine substitution, $aE+b$) 을 적용하여$E$의 '아핀 지름 (Affine diameter)'을 최소화합니다. 이는 해의 유클리드 노름을 줄여 격자 공격을 용이하게 합니다.
• Multiplicative Truncation: CROSS 의 $E$가 곱셈 부분군 (multiplicative subgroup) 인 특성을 이용하여, $E$의 크기를 $z'$로 줄이는 확률적 축소 (Truncation) 기법을 적용합니다.
• List-CVP/SVP 변환: 축소된 $E$를 사용하여 ResSD 문제를 List-CVP (주어진 거리 이내의 모든 벡터 나열) 또는 List-SVP 문제로 변환합니다.
• 특이점: 특정 매개변수 (낮은 부호율, 작은 $E$) 에서는 List-CVP/SVP가 단순한 CVP/SVP 문제로 퇴화 (degeneration) 할 수 있음을 보였습니다. 이는 CROSS 설계자가 지적한 2 원소 집합의 부분합 문제 (Subset-sum) 와 유사한 현상을 일반화한 것입니다.

3. 실험 결과 및 보안성 분석 (Results)

저자들은 CROSS 의 제안된 매개변수 (128-bit, 192-bit, 256-bit 보안 수준) 와 축소된 매개변수에 대해 이론적 복잡도와 실험적 평가를 수행했습니다.

• 최적 공격: 제안된 모든 격자 기반 및 RegSD 기반 공격 중 가장 효율적인 것은 하이브리드 List-CVP 공격 (Hybrid-ListCVP) 이었습니다. 특히 $E$의 크기를 $z'=3$로 축소할 때 최적의 시간 - 메모리 트레이드오프를 보였습니다.
• CROSS 보안성:
  • 제안된 모든 공격의 시간 복잡도는 CROSS 설계자가 제안한 기존 ISD 기반 공격 (Shifted representations 등) 보다 높았습니다.
  • 예를 들어, 128-bit 보안 수준 (127, 76) 의 경우, 기존 공격은 $2^{143}$, 제안된 최적 공격 (Hybrid-ListCVP) 은 $2^{196}$ 정도의 복잡도를 가집니다.
  • 결론: 현재 제안된 방법론으로는 CROSS 의 안전성을 위협할 수 없으며, CROSS 는 여전히 안전한 것으로 판단됩니다.
• 메모리 - 시간 트레이드오프: 제안된 List-CVP 기반 공격은 기존 공격에 비해 메모리 사용량을 크게 줄이면서 시간을 약간 증가시키는 새로운 트레이드오프 지점을 제공합니다.

4. 의의 및 결론 (Significance)

• 새로운 분석 관점: ResSD 문제를 단순히 ISD 로만 접근하는 것을 넘어, Regular Syndrome Decoding 및 격자 기반 문제 (CVP, SVP) 와의 깊은 연결고리를 규명했습니다. 이는 ResSD 문제의 구조적 특성을 이해하는 데 중요한 통찰을 제공합니다.
• 미래 설계에 대한 기여: CROSS 는 현재 ResSD 를 기반으로 하는 유일한 체계이지만, 이 연구에서 제시된 축소 기법 (Reduction) 과 분석 방법은 향후 ResSD 를 기반으로 할 수 있는 다른 포스트 양자 암호 체계의 설계 및 보안 평가에 유용하게 활용될 것입니다.
• 약한 키 (Weak-key) 공격: $E$가 곱셈 부분군인 경우, 약한 키 공격을 일반적인 확률적 공격으로 변환할 수 있음을 보였습니다.

요약하자면, 이 논문은 CROSS 의 핵심 문제인 ResSD 에 대해 다양한 패러다임 (부호 기반, 격자 기반) 을 활용한 새로운 공격 기법을 제안했으나, 현재 CROSS 매개변수에서는 기존 공격보다 우월하지 않음을 증명했습니다. 다만, 문제 간의 변환 관계를 규명함으로써 포스트 양자 암호 분석의 지평을 넓혔다는 점에서 의의가 큽니다.