Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers: Bounds and Constructions

기술 요약: 비협력 서버들로 구성된 결합 체계적 MDS 코딩 기반의 프라이빗 정보 검색(PIR)

문제 정의
본 논문은 $M$개의 파일이 $[N, K]$ 최대 거리 분리(Maximum Distance Separable, MDS) 코드를 사용하여 $N$개의 비협력 서버에 저장된 분산 스토리지 시스템에서의 프라이빗 정보 검색(Private Information Retrieval, PIR) 문제를 다룬다. 각 파일을 독립적으로 인코딩하는 전통적인 "분리형(separate)" MDS 코딩 PIR 방식과 달리, 본 연구는 결합 MDS 코딩(joint MDS-coded) PIR에 초점을 맞춘다. 이 모델에서는 모든 $M$개의 파일이 하나의 체계적 MDS 어레이 코드를 사용하여 함께 인코딩된다. 사용자는 개별 서버에 자신의 요청 파일의 정체 $\theta$를 드러내지 않으면서 특정 파일 $W_\theta$를 검색하고자 한다.

주요 동기는 Sun과 Tian [28]의 관찰에서 비롯되었다. 그들은 특정 파라미터 영역에서 결합 인코딩이 분리형 MDS 코딩 PIR(Banawan 및 Ulukus [9]가 확립한 것)의 용량 한계를 돌파할 수 있음을 보여주었다. 그러나 결합 MDS 코딩 PIR의 이론적 용량, 특히 저장 패턴과 체계적 제약이 달성 가능한 검색률에 미치는 영향에 대한 연구는 그동안 거의 이루어지지 않았다.

방법론 및 시스템 모델
저자들은 두 가지 핵심 구성 요소를 도입하여 시스템 모델을 정교화한다:

1. 저장 패턴 ($P$): $M$개의 파일이 스토리지 코드의 $K$개 체계적 입력 블록에 어떻게 배치되는지를 기술하는 행렬.
2. 체계적 MDS 어레이 코드 ($C$): 이 블록들을 $N$개의 서버에 걸쳐 인코딩하는 코드.

본 논문은 고정된 저장 패턴 $P$에 대해 가능한 모든 체계적 MDS 어레이 코드에 대한 검색률의 상한(supremum)인 용량 $C^{(s)}_{JMDS-PIR}(M, N, K, P)$를 정의한다. 연구는 다음 두 가지 특정 저장 패턴에 집중한다:

• 사례 1: $K = Mt$이며 패턴$P = \ell I_M \otimes \mathbf{1}_t$ 인 경우.
• 사례 2: $K = Mt + 1$이며 패턴$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$ 인 경우.

이론적 한계를 도출하기 위해 저자들은 정보 이론적 도구, 구체적으로 서버 응답의 조건부 독립 구조를 규명하고(Lemma 3), Han의 부등식을 기반으로 재귀적 부등식을 유도한다(Lemmas 5 및 8). 구성을 위해서는, 프라이버시를 보장하면서 유용한 정보의 다운로드를 극대화하기 위해 무작위 순열(random permutations)과 저장된 심볼들의 선형 결합을 활용한다.

주요 기여 및 결과

1. 용량의 상한 (Upper Bounds on Capacity):

   • **$K = Mt$** 이고 패턴$P = \ell I_M \otimes \mathbf{1}_t$인 경우, 저자들은$1 - (1 - \frac{1}{M})\frac{K}{N}$ 의 상한을 도출한다.
   • **$K = Mt + 1$** 이고 패턴$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$인 경우, 저자들은$\frac{K(N-K+t)}{(K-1)(N-1)}$ 의 상한을 도출한다.
   • 결정적으로, $K = Mt$이고$N \le K + t$ 인 경우, 도출된 상한은 Sun과 Tian [28]이 제안한 방식의 성능과 일치하며, 이는 해당 특정 저장 패턴 하에서 그들의 방식이 최적임을 입증하는 첫 번째 증명이다.

2. 스키마 구성 (Scheme Constructions):
   본 논문은 세 가지 결합 체계적 MDS 코딩 PIR 스키마를 구성한다:

   • 구성 1 ($N \le K + t, K = Mt$): 이 스키마는 상한인 $1 - (1 - \frac{1}{M})\frac{K}{N}$ 을 달성하여, 이 영역에서의 정확한 용량을 확립한다.
   • **구성 2 ($N > K + t, K = Mt$):** 이 스키마는$\frac{N+K-t}{NM}$ 의 검색률을 달성한다.
   • 구성 3 ($N \le K + t, K = Mt + 1$): 이 스키마는 $\frac{K(N-K+t)}{M((t+1)N-K)}$ 의 검색률을 달성한다.

3. 성능 개선:
   제안된 스키마들을 용량을 달성하는 분리형 MDS 코딩 PIR 방식(예: [9], [17], [18])과 비교하였다. 분석 결과, 제안된 결합 방식들이 특정 파라미터 범위에서 엄격하게 더 높은 검색률을 달성함을 보여준다:

   • $K = Mt$의 경우, 저장률$r = K/N$ 이 높을 때 개선 효과가 상당하다.
   • $K = Mt + 1$의 경우,$K < N \le K + t$ 일 때 결합 방식이 항상 분리형 방식보다 우수하다.
   • 정량적 이득: 상대적인 검색률 개선도는 $M \ge 4$ 일 때 **15%**를 초과하고, $M \ge 9$ 일 때 **20%**를 초과하며, $M$이 증가함에 따라 점진적으로 $1 - 2/e \approx 26.42\%$ 에 수렴한다.
   • 또한, 제안된 구성들은 기존의 결합 방식 [28]에 비해 더 작은 파일 크기를 요구하며, 일부 경우(예: $M=2, N=3t$) 훨씬 더 작은 유한체(finite field) 크기를 요구한다.

의의
본 논문의 주요 의의는 규정된 저장 패턴 하에서 결합 체계적 MDS 코딩 PIR의 용량을 이론적으로 규명했다는 점에 있으며, 이는 이전에 미해결 상태였던 문제였다. 특정 파라미터에 대해 Sun과 Tian [28]의 방식의 최적성을 증명하고 더 넓은 파라미터 집합에 대한 새로운 구성을 제공함으로써, 본 연구는 결합 인코딩이 단순한 휴리스틱이 아니라 분산 스토리지의 PIR을 위한 증명 가능한 우월한 전략임을 입증한다. 결과적으로 결합 MDS 코딩 PIR이 분리형 코딩의 용량 한계를 돌파할 수 있음을 확인하였으며, 특히 파일의 수($M$)가 증가함에 따라 프라이버시를 해치지 않으면서도 검색 효율성을 크게 향상시킬 수 있음을 보여준다. 저자들은 본 연구의 결과가 특정 파라미터 영역을 다루고 있으나, 이를 보다 일반적인 결합 MDS 코딩 PIR 설정으로 확장하는 것이 향후 연구의 도전적인 방향임을 언급하였다.