Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

기술 요약: 합성 차수 체(Composite Order Fields) 상에서의 누출 내성(Leakage-Resilient) 샤미르 비밀 공유를 위한 부분적 무작위성 제거(Partial Derandomization)

1. 문제 정의

본 논문은 합성 차수 체($d \ge 2$인 $\mathbb{F}_{p^d}$)에서 **물리적 비트 누출(physical-bit leakage)**에 내성을 갖는 샤미르 비밀 공유(SSS)의 명시적인 평가 지점(evaluation places) 구축 문제를 다룬다.

표준적인 SSS에서 비밀은 $n$명의 당사자에게 공유되며, $k$명이 모이면 이를 복구할 수 있다. 무작위적 구성(평가 지점을 균등 분포로 무작위 선택)은 로컬 누출에 대해 통계적 보안성을 갖는 것으로 알려져 있으나, 이는 신뢰할 수 있는 공개 무작위성이 필요하다. 실제 환경에서 공격자는 무작위 시드(random seed)에 영향을 미쳐, 스킴을 취약한 평가 지점으로 유도할 수 있다.

기존 연구를 통해 다음이 확립되었다:

• 소수 체($\mathbb{F}_p$) 상에서는 무작위 평가 지점이 높은 확률로 누출 내성을 제공한다.
• 합성 체($\mathbb{F}_{p^d}$) 상에서는, Nguyen(EUROCRYPT 2025)이 모든 선형 코드 기반 비밀 공유 스킴이 물리적 비트 누출에 대해 완벽한 보안(통계적 거리 0)을 갖거나 혹은 완전히 무방비(completely insecure) 상태라는 **완벽한 이분법(perfect dichotomy)**을 확립했다.
• 그러나 합성 체의 경우, $k > 2$ 또는 일반적인 블록 누출(block-leakage) 체제에 대해 명시적이고 결정론적인 평가 지점 패밀리는 알려진 바가 없었다. 소수 체를 위한 기존의 명시적 구성들은 합성 체의 선형 좌표 맵에는 적용되지 않는 비선형 비트 추출 특성에 의존했다.

핵심 과제는 (평가 지점을 지정하는 데 필요한 엔트로피를 줄이면서) **무작위성을 부분적으로 제거(derandomize)**하여, 합성 체 환경에서도 물리적 비트 누출에 대한 완벽한 보안을 유지하는 것이다.

2. 방법론 및 구성

저자는 부분적 무작위성 제거(partial derandomization) 전략을 제안한다. $n$개의 독립적인 무작위 평가 지점을 선택하는 대신, 무작위로 선택된 기저 지점(base point) $x_0$에 유리 함수(rational function) $\Phi$를 반복 적용하여 평가 지점을 구성한다.

구성 방식:

• 체 설정: $\alpha$를 원시 원소(primitive element)로 하는 $\mathbb{F} = \mathbb{F}_{p^d}$를 정의한다.
• 단계 연산자(Step Operator): 뫼비우스 변환 $\Phi(x) = \frac{\alpha x}{x + 1}$를 정의한다.
• 평가 지점: $n$개의 평가 지점은 $j = 0, \dots, n-1$에 대해 $x_j = \Phi^j(x_0)$로 정의된다. 여기서 $x_0 \in \mathbb{F}^*$는 무작위로 선택된 기저 지점이다.
• 엔트로피 감소: 이 스킴을 지정하기 위해서는 $n d \log p$ 비트가 아닌, 단 $d \log p$ 비트(즉, $x_0$를 선택하기 위한 비트)만 필요하므로 상당한 수준의 엔트로피 감소가 이루어진다.

핵심 구조적 통찰:
보안 분석은 $\Phi^j$의 **서로 다른 극(distinct poles)**에 의존한다.

• $\Phi^0(x) = x$는 $\infty$에서 극을 갖는다.
• $j \ge 1$인 경우, $\Phi^j(x)$는 $\mathbb{F}^*$ 내의 서로 다른 유한한 지점에서 극을 갖는다.
  이 "극의 구별성(pole-distinctness)"은 매우 중요하다. 저자는 후보인 $\Psi(x) = \alpha x$ (순수 확대 변환)와 대조하는데, $\Psi(x)$의 모든 반복 항은 동일한 극 $\infty$를 공유하므로 보안 논리가 붕립된다.

3. 기술적 접근 방식

증명은 Nguyen(2025)이 확립한 완벽한 이분법을 활용하여 세 단계로 진행된다.

1. 완벽한 이분법 (1단계):
   본 논문은 $\mathbb{F}_{p^d}$에서의 좌표 추출이 $\mathbb{F}_p$-선형임을 이용한다. 결과적으로 누출 맵(leakage map)은 선형이다. 이는 서로 다른 비밀들에 대한 누출 분포 사이의 통계적 거리가 0 또는 1임을 의미한다. 완벽한 보안은 누출 맵이 전사(surjective)일 때만 달성된다. 이 조건은 테스트 행렬 $\Theta_{\vec{i}}$(평가 지점과 누출 패턴으로부터 유도됨)가 $\mathbb{F}_p$ 위에서 풀 컬럼 랭크(full column rank)를 갖는 것과 동치이다.

2. 부분 분수 비퇴화성 (2단계):
   테스트 행렬이 풀 랭크임을 증명하기 위해, 저자는 평가 지수의 거듭제곱들의 비자명한 선형 결합이 0이 되지 않음을 보여야 한다. 이를 위해 유리 함수 $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$를 정의한다.
   **부분 분수 분해(partial fraction decomposition)**를 사용하여, 저자는 $\Phi^j$의 극이 서로 다름을 이용한다. 극들이 서로 다르기 때문에, 임의의 특정 극에서의 $G_\ell$의 유수(residue)는 합의 단일 항에 의해 결정된다. 만약 $G_\ell$이 항등적으로 0이라면, 모든 계수가 0이어야만 한다. 이 "비퇴화성(nondegeneracy)" 논증은 랭크 조건을 실패하게 만드는 "나쁜(bad)" 기저 지점 $x_0$의 수를 제한한다.

3. 멀티 블록 확장 (3단계):
   이 논증을 멀티 블록 누출(각 쉐어당 여러 좌표가 누출되는 경우)로 확장한다. 저자는 쉐어 내의 선형 결합에서 발생하는 체 계수(field coefficients)를 처리하며, 누출 패턴이 "허용 가능한(admissible)" 형태(쉐어당 서로 다른 블록 위치)라면 부분 분수 논증이 여전히 유효함을 보여준다.

4. 주요 결과

정리 1.1 (단일 블록 누출에 대한 완벽한 보안):
매개변수 $n = O(d / \log_p d)$와 임의의 임계값 $k \ge 2$에 대하여, 크기가 $|Bad| \le n + n(dp)^n$인 "나쁜" 기저 지점 집합 $Bad \subset \mathbb{F}^*$가 존재한다. $x_0 \notin Bad$인 임의의 $x_0$에 대해, 평가 지점을 $x_j = \Phi^j(x_0)$로 사용하는 스킴은 모든 단일 블록 누출 패턴에 대해 완벽한 보안(통계적 거리 정확히 0)을 제공한다.

• 이는 임의의 소수 $p$에 대해 쉐어당 단일 물리적 비트 누출에 대한 완벽한 보안을 의미한다.
• $d > n(1 + \log_p d) + \log_p(2n)$일 때 좋은 $x_0$의 존재가 보장된다.

정리 1.2 (멀티 블록 누출):
총 $M$개의 블록이 누출되는 고정된 허용 가능 누출 패턴에 대하여, 나쁜 집합의 크기는 $|Bad| \le n + n \cdot p^M$으로 제한된다. $M < d - \log_p(2n)$일 때 좋은 $x_0$가 존재한다.

• $\le M$개의 블록을 가진 모든 패턴에 대한 보편적 보안의 경우, $|Bad| \le n + n(dpe)^M$이며, $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$일 때 존재가 보장된다.

분류기(Classifier):
본 논문은 후보 $x_0$가 주어졌을 때, 모든 누출 패턴에 대해 풀 랭크 조건을 검증하는 명시적 분류기(Algorithm 1)를 제공한다. 이는 구조화된 구성의 보안성을 인증하는 건전한 테스트 역할을 한다.

5. 의의 및 비교

본 논문은 다음과 같은 기여와 차별점을 주장한다:

• 완벽한 보안 vs 통계적 보안: 합성 체 상에서의 기존 무작위적 구성들이 통계적 보안($\epsilon = 2^{-\Omega(d)}$)을 제공했던 것과 달리, 본 구성은 특정 매개변수 범위에서 완벽한 보안(통계적 거리 0)을 달성한다.
• 무작위성 제거: 평가 지점을 하나의 파라미터 패밀리(궤도 $\Phi$의 궤적)로 제한함으로써, 스킴을 지정하는 데 필요한 무작위성을 $nd \log p$ 비트에서 $d \log p$ 비트로 줄였다.
• 명시적 구성: 물리적 비트 누출에 저항하는 합성 체 상의 $k > 2$를 위한 최초의 명시적 평가 지점 패밀리를 제공하여, "무작위 지점" 패러다임을 넘어섰다.
• 한계 및 트레이드오프:
  • 당사자 수 $n$은 $O(d / \log_p d)$로 제한되는 반면, 무작위 구성은 $O(dk / \log_p d)$를 지원한다. 저자는 이 $k$ 배의 손실이 단일 파라미터 구성에서 발생하는 필연적인 현상이라고 추측한다.
  • 멀티 블록 보편성은 현재 패턴 열거(enumeration)의 병목 현상으로 인해, $M$에 대해 지수적인 나쁜 집합 경계치를 갖는다.
  • 본 구성은 뫼비우스 변환 $\Phi(x) = \alpha x / (x+1)$의 특정한 대수적 구조에 의존하며, 대안인 확대 변환 $\alpha x$는 보안을 제공하지 못한다.

본 연구는 모든 매개변수 범위에 대해 무작위성 제거 문제를 해결한다고 주장하는 것이 아니라, 단일 파라미터 구성에서 발생하는 $k$ 배의 손실을 식별하고, 유리 함수의 반복(iterates)이 갖는 서로 다른 극을 활용하여 특정 실용적 범위에서 완벽한 보안을 달성하는 엄격한 부분적 무작위성 제거를 수행하는 데 주력하였다.