Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

논문 요약: 정수환 (Integer Ring) 의 CRT 를 기반으로 한 점근적 이상적 위계적 비밀 공유

1. 연구 배경 및 문제 제기 (Problem)

• 기존의 한계: 샤미어 (Shamir) 의 비밀 공유 방식은 모든 참가자에게 동등한 권한을 부여합니다. 그러나 실제 응용에서는 참가자 간 권한 수준을 다르게 설정해야 하는 경우가 많습니다. 이를 해결하기 위해 **위계적 비밀 공유 (Hierarchical Secret Sharing, HSS)**가 제안되었습니다.
• 기존 HSS 방식의 문제점:
  • 이산형 (Disjunctive, DHSS) 및 결합형 (Conjunctive, CHSS) 접근: 기존 연구들은 다항식 보간법 (Birkhoff interpolation) 이나 다항모이드 (polymatroids) 를 사용하여 이상적 (Ideal, 정보율 $\rho=1$) 인 방식을 제안했으나,Dealer(비밀 분배자) 의 계산 복잡도가 지수 시간 (exponential time) 이거나 행렬의 비특이성 검증이 필요하여 비효율적입니다.
  • CRT 기반 방식의 결함: 정수환의 중국인의 나머지 정리 (CRT) 를 이용한 방식은 유연한 공유 크기 (share size) 를 제공하지만, 기존 연구들 (Harn et al., Ersoy et al., Tiplea et al. 등) 은 보안 취약점이 있거나 정보율 (Information Rate) 이 1/2 미만으로 낮아 비효율적이었습니다. 최근 제안된 일부 방식은 보안성이 입증되지 않았습니다.
• 목표: 보안성이 보장되면서, 유연한 공유 크기를 지원하고 정보율이 비밀 크기가 커짐에 따라 1 에 점근적으로 수렴하는 (점근적 이상적) DHSS 및 CHSS 방식을 설계하는 것.

2. 방법론 (Methodology)

이 논문은 **정수환 (Integer Ring) 의 중국인의 나머지 정리 (CRT)**와 **일방향 함수 (One-way Functions)**를 결합하여 두 가지 새로운 HSS 방식을 제안합니다.

• 핵심 수학적 도구:
  • k-compact 소수열 (k-compact sequences of co-primes): $m_0 < m_1 < \dots < m_n$ 형태의 소수열로, $km_0 < m_i < km_0 + m_0^\theta$ ($0 < \theta < 1$) 조건을 만족합니다. 이는 Asmuth-Bloom 방식의 제약을 만족하면서도 정보율을 높이는 데 핵심적입니다.
  • 일방향 함수: 보안성을 강화하기 위해 공개된 일방향 함수 $h_\ell(\cdot)$를 사용하여 공유값을 변조합니다.
• 제안된 두 가지 방식:
  1. 점근적 이상적 DHSS (Disjunctive HSS):
     • 접근 구조: 참가자 집합이 $P_1, \dots, P_m$으로 나뉘어 있을 때, 임의의 레벨 $\ell$에서 $\sum_{w=1}^\ell P_w$ 내의 참가자 수가 $t_\ell$ 이상이면 비밀 복구가 가능합니다 (OR 논리).
     • 구현: Dealer 는 비밀 $s$와 무작위 정수 $\alpha_\ell$을 이용해 $y_\ell = s + \alpha_\ell m_0$를 생성합니다. 공유는 CRT 를 통해 생성되지만, 일부 공유는 무작위 값으로 설정하고 일방향 함수를 통해 공개 정보를 생성하여 보안을 강화합니다.
  2. 점근적 이상적 CHSS (Conjunctive HSS):
     • 접근 구조: 모든 레벨 $\ell$에 대해 $\sum_{w=1}^\ell P_w$ 내의 참가자 수가 $t_\ell$ 이상이어야 비밀 복구가 가능합니다 (AND 논리).
     • 구현: 비밀 $s$를 $m$개의 부분 비밀 $\delta_1, \dots, \delta_m$으로 분해 ($s = \sum \delta_i \mod m_0$) 한 후, 각 레벨별로 CRT 를 적용하여 복호화합니다.

3. 주요 기여 (Key Contributions)

1. 보안성과 이상적 특성의 동시 달성: 기존 CRT 기반 방식들은 보안이 취약하거나 정보율이 낮았으나, 본 논문은 **보안 (Secure)**과 점근적 이상적 (Asymptotically Ideal) 특성을 동시에 만족하는 DHSS 및 CHSS 방식을 최초로 제안했습니다.
2. 유연한 공유 크기 지원: 기존 이상적 방식 (Tassa et al., Cheng et al.) 은 공유 크기가 고정되어 있었으나, 본 방식은 CRT 의 특성을 활용해 참가자마다 다른 크기의 공유를 할당할 수 있습니다.
3. 계산 효율성: Dealer 는 행렬 검증이나 지수 시간 알고리즘 없이 다항 시간 (polynomial time) 내에 공유를 생성할 수 있습니다.
4. 보안 증명:
   • 정확성 (Correctness): 권한 있는 집합은 CRT 를 통해 비밀을 정확히 복원할 수 있음을 증명했습니다.
   • 점근적 완전성 (Asymptotic Perfectness): 권한 없는 집합은 비밀에 대한 정보를 얻지 못하며, 비밀의 엔트로피 손실 ($\Delta$) 이 비밀 크기가 무한대로 갈 때 0 에 수렴함을 증명했습니다.
   • 점근적 최대 정보율: 정보율 $\rho$가 비밀 크기 $m_0$가 커짐에 따라 1 에 수렴함을 보였습니다.

4. 결과 (Results)

• 정보율 (Information Rate): 제안된 방식의 정보율 $\rho$는 $\frac{\log_2 m_0}{\log_2 (m_0 + m_0^\theta)}$ 형태로, $m_0 \to \infty$일 때 $\rho \to 1$이 됩니다. 이는 기존 CRT 기반 방식들 (정보율 < 1/2 또는 < 1) 보다 월등히 우수합니다.
• 보안성 비교:
  • 기존 CRT 기반 방식들 (Harn, Ersoy, Tiplea, Yang 등) 은 보안 취약점이 있거나 정보율이 낮았습니다.
  • 본 논문은 이러한 기존 방식들의 단점을 보완하여 보안성과 높은 정보율을 모두 확보했습니다.
• 표 1 및 표 2 분석:
  • DHSS: 기존 이상적 방식은 유연한 공유 크기를 지원하지 못했고, 기존 CRT 방식은 보안이 취약했습니다. 본 방식은 보안 O, 유연한 공유 크기 O, 점근적 이상적을 모두 만족합니다.
  • CHSS: 기존 방식 중 일부는 보안이 취약하거나 정보율이 낮았습니다. 본 방식은 보안 O, 유연한 공유 크기 O, 점근적 이상적을 달성했습니다.

5. 의의 및 결론 (Significance)

• 실용성: 이 연구는 실제 응용 환경에서 요구되는 다양한 권한 수준 (위계적 구조) 을 효율적으로 지원하면서도, 저장 및 통신 오버헤드 (정보율) 를 최소화하는 새로운 HSS 패러다임을 제시합니다.
• 이론적 기여: CRT 기반 비밀 공유의 보안 취약점을 해결하고, 일방향 함수와 k-compact 소수열을 결합하여 점근적 이상적 특성을 달성하는 이론적 틀을 확립했습니다.
• 미래 전망: 제안된 방식은 대규모 분산 시스템, 블록체인, 클라우드 저장소 등 권한 관리가 복잡하고 보안 및 효율성이 동시에 요구되는 분야에서 적용 가능성이 높습니다.

결론적으로, 이 논문은 정수환 CRT 와 일방향 함수를 결합하여 기존 CRT 기반 HSS 의 보안 및 효율성 한계를 극복한, 유연하고 점근적으로 이상적인 새로운 비밀 공유 체계를 제시한 중요한 연구입니다.