기술 요약: 동일 차수 방정식 시스템 해결의 복잡성

문제 정의

다변수 암호학 및 양자 내성 암호 설정에서 수많은 암호 체계의 보안은 유한체 위에서 다변수 다항식 방정식 시스템을 푸는 계산적 어려움에 의존한다. 그뢰브너 기저(Gröbner basis) 방법을 통한 이러한 시스템 해결의 복잡성은 주로 정규도(degree of regularity, $d_{reg}$)와 해결 차수(solving degree)에 의해 결정된다. 정규도는 그뢰브너 기저 계산의 복잡성에 대한 상한을 제공하지만, 암호학적 규모의 시스템에 대해 이를 계산하거나 추정하는 것은 종종 어렵다.

일반적인 관행은 시스템이 준정규(semiregular 또는 cryptographic semiregular)라는 휴리스틱 가정에 의존하며, 이는 정규도에 대한 명시적인 공식을 도출해낸다. 그러나 이 가정은 항상 유효한 것은 아니다; 특정 파라미터 선택이나 체(field)에서는 준정규 수열이 존재하지 않을 수 있다. 결과적으로, 준정규성 가정에 의존하지 않고, 정규도가 유한한 시스템에 적용될 수 있는 정규도 및 해결 차수에 대한 증명된 비-휴리스틱 상한이 필요하다.

방법론

저자들은 교환 대수학의 도구를 사용하여 문제를 접근하며, 특히 주어진 차수 $D$에서 $n$개의 다항식으로 이루어진 정규 수열(regular sequence)을 상위 차수 부분(top-degree parts)의 아이디얼이 포함하는 시스템에 초점을 맞춘다.

1. 프레임워크: 본 논문은 체 $F$ 위에서 $n$개의 변수를 가진 $m$개의 다항식으로 구성된 시스템 $F = \{f_1, \dots, f_m\}$을 고려한다. 분석은 상위 차수 부분 $f_1^{top}, \dots, f_m^{top}$이 선형 독립이며, 시스템이 차수 $D$에서 정규(즉, 상위 차수 부분에 의해 생성된 아이디얼이 차수 $D$인 $n$개의 다항수로 이루어진 정규 수열을 포함함)라고 가정한다.
2. LPP 아이디얼로의 환원: 카스텔누오보-문드(Castelnuovo-Mumford) 정규도를 제한하기 위해, 저자들은 Eisenbud-Green-Harris (EGH) 추측을 활용한다. 이 추측은 특정 차수의 정규 수열을 포함하는 모든 동차 아이디얼 중에서, Lex-Plus-Powers (LPP) 아이디얼이 최대 정규도를 가진다고 상정한다.
3. 조합론적 분석: 저자들은 주어진 파라미터($n, m, D$)와 관련된 특정 LPP 아이디얼을 구성한다. 사전식 순서(lexicographic order) 하에서 이 아이디얼들의 구조를 분석함으로써, 저자들은 원래 시스템의 정규도의 상한 역할을 하는 LPP 아이디얼의 정규도를 결정한다(EGH 추측을 조건으로 함).
4. 체 방정식(Field Equations): 이 방법론은 시스템에 체 방정식($x_i^q - x_i$)이 추가된 경우로 확장되는데, 이는 방정식의 차수 $D$가 체의 크기 $q$보다 크거나 같은 유한체 $\mathbb{F}_q$ 위의 시스템에서 매우 중요하다.

주요 기여 및 결과

1. 차수 $D$에서 정규인 시스템에 대한 상한 (체 방정식 미포함)

정리 23은 시스템이 차수 $D$에서 정규라고 가정할 때, $n$개의 변수를 가진 $m$개의 차수 $D$ 방정식 시스템의 정규도에 대한 날카로운(sharp) 상한을 제공한다.

• 이 상한은 방정식의 개수($m$), 변수의 개수($n$), 그리고 차수($D$)에 의존한다.
• 공식은 $m-n$이 조합적 합($\sigma_{k,t}$)에 의해 정의된 특정 구간 내에 떨어지도록 하는 고유한 정수 $k$와 $t$를 식별하는 과정을 포함한다.
• 도출된 상한은 다음과 같다: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• 이 상한은 모든 $m, n, D$ 값에 대해 날카로우며(sharp), 상위 차수 부분이 특정 LPP 아이디얼을 형성하는 시스템에 의해 충족된다.

따름정리 27은 이를 뮤턴트(mutant) 알고리즘을 위한 해결 차수의 상한으로 변환한다:
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. 체 방정식을 포함하는 시스템에 대한 상한

본 논문은 $D \ge q$인 경우, 즉 체 방정식이 시스템에 추가되는 경우를 다룬다.

• 명제 31: 매우 과결정된(very overdetermined) 시스템(시스템이 다항식 공간의 차원을 초과하는 경우)의 경우, 정규도는 정확히 $D$이다.
• 정리 33: $q \le D \le n(q-1)$이고 상위 차수 부분이 체 방정식에 대해 선형 독립인 시스템에 대해, 저자들은 정규도에 대한 상한을 제공한다.
  • 이 상한은 $(x_1^q, \dots, x_n^q)$에 대한 차수 $D$의 사전식 순서 내에서 $m$번째 단항식의 위치를 분석하여 도출된다.
  • 상한은 $B = q - t + (n - k)(q - 1)$에 의해 표현된다 (여기서 $k$와 $t$는 $m$을 포함하는 구간에 의해 결정됨).
  • $m, D, t$에 관한 특정 조건에 따라, 상한은 $B$ 또는 $B-1$이 된다.

따름정리 34는 이러한 결과들을 이진 시스템(binary systems, $q=2$)에 특화하여, $\mathbb{F}_2$ 상의 차수 $D$ 시스템에 대한 정규도 및 해결 차수의 단순화된 공식을 제공한다.

3. 특정 스킴에 대한 적용

저자들은 자신들의 상한을 구체적인 암호 스킴에 적용한다:

• Cubic Simple Matrix: 저자들은 $d_{reg} \le 2n - 1$이라는 증명된 상한을 도출하였으며, 이는 이 시스템에 대한 최초의 증명된 상한으로, 기존의 휴리스틱 추정치와 대조된다.
• Unbalanced Oil and Vinegar (UOV): 이 상한들은 체 방정식이 포함되었을 때 정규도가 어떻게 거동하는지를 보여주기 위해 $\mathbb{F}_2$ 상의 UOV 시스템에 적용된다.

의의 및 주장

본 논문은 다항식 시스템 해결의 복잡성에 대해 증명된 비-휴리스틱 상한을 제공한다는 점에서 주요한 의의를 갖는다고 주장한다.

• 신뢰성: 준정규성 가정에 기반한 추정치(특정 파라미터에서 실패할 수 있음)와 달리, 이 상한들은 정규도가 유한하고 주어진 차수에서 정규인 모든 시스템에 대해 유효하다.
• 일반성: 결과는 임의의 체에 대한 시스템에 적용되며, 체 방정식이 있는 경우와 없는 경우를 모두 포괄한다.
• 날카로움(Sharpness): 상한들은 "날카롭다"고 기술되는데, 이는 특정 시스템(LPP 아이디얼)에 의해 달성됨을 의미하며, 보안 분석을 위한 현실적인 최악의 경우 추정치를 제공한다.
• 한({Limitations}): 저자들은 자신들의 상한이 일반적으로 준정규성 휴리스틱 하에서 얻어지는 것보다 덜 타이트히(즉, 더 높게) 나타난다는 점을 명시적으로 인정한다. 그러나 저자들은 준정규 수열이 존재하지 않는 시나리오를 포함하여, 증명되지 않은 가정을 피하기 위해 이러한 트레이드오프가 필요하다고 주장한다.

이 연구는 새로운 알고리즘이나 실험적 구현을 제안하는 것이 아니라, 암호학적으로 관련이 있는 광범위한 다변수 다항식 시스템에 대해 기존의 그뢰브너 기저 방법(표준 및 뮤턴트 모두)의 이론적 한계를 확립하는 데 목적이 있다.