Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

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

• 속성 기반 암호화 (ABE): 암호화된 데이터에 대한 세밀한 접근 제어를 가능하게 하는 암호 체계입니다. 특히 CP-ABE에서는 각 암호문이 특정 접근 정책 (Access Policy) 과 연관되어 있으며, 사용자의 속성 (Attribute) 이 정책을 만족할 때만 복호화가 가능합니다.
• 기존 기술의 한계:
  • 기존 LWE 기반 CP-ABE 방식들은 대부분 암호문 크기가 정책의 복잡도 (회로 크기 $s$ 또는 깊이 $d$) 에 비례하여 증가하는 문제가 있었습니다.
  • 일부 연구 (예: Wee24, Wee25) 는 암호문 크기를 속성 길이 $\ell$에 무관하게 만들거나 회로 크기에 무관하게 만들었으나, 여전히 공개키 크기나 다른 파라미터들이 회로 크기에 의존하거나, 특정 비표준 가정을 필요로 했습니다.
  • 목표: NC1 회로 (다항식 크기, 로그 깊이) 를 지원하는 CP-ABE 를 구성하되, **암호문 크기를 상수 (상수 크기)**로 유지하고, 공개키와 비밀키 크기를 최적화하는 것입니다.

2. 방법론 (Methodology)

이 논문은 **Wee (CRYPTO 2024)**가 제안한 $\ell$-Succinct LWE 가정을 핵심적으로 활용합니다.

2.1 핵심 기술적 요소

1. Succinct LWE 가정:

   • 기존 LWE 와 달리, 공개 매개변수 중 일부 ($B, W, T$) 가 특정 구조를 가지며, 이 구조를 통해 효율적인 트랩도어 (Trapdoor) 를 생성할 수 있게 합니다.
   • 이 가정은 $poly(\lambda)$-succinct LWE 로, 모듈러스 - 노이즈 비율이 부분 지수 (sub-exponential) 인 경우 안전성이 보장됩니다.

2. DKW21 방식의 개선 및 행렬 커밋먼트 (Matrix Commitment) 활용:

   • 기존 DKW21 방식 (LSSS 기반 CP-ABE) 은 암호문 크기가 접근 정책 행렬의 행 수 ($\ell$) 에 비례했습니다.
   • 본 논문은 Wee25 의 행렬 커밋먼트 (Matrix Commitment) 기법을 도입하여 암호문 크기를 압축합니다.
   • 기법:
     • 각 속성 $u$에 대한 행렬 $A_u$ 대신 하나의 공통 행렬 $B$를 사용합니다.
     • 암호문 구성 요소 중 정책과 관련된 정보를 행렬 커밋먼트 $C$로 대체합니다.
     • 암호문은 $(c_1, c_2, c_3)$로 구성되며, $c_2$는 커밋먼트 행렬 $C$와 공개 행렬 $A$의 합에 대한 LWE 샘플 형태를 띱니다.

3. 보안 증명 전략 (Hybrid Games):

   • 선택적 안전성 (Selective Security) 을 증명하기 위해 일련의 하이브리드 게임을 정의합니다.
   • 핵심 아이디어: 공격자가 권한이 없는 속성 집합에 대해 비밀키를 요청할 때, 공격자가 LWE 샘플에 대한 추가 정보를 얻지 못하도록 합니다.
   • 이를 위해 Succinct LWE 의 공개 매개변수 $T$를 사용하여, 새로운 행렬 $[I_{\ell'} \otimes B | W']$에 대한 트랩도어를 생성합니다. 이 트랩도어는 원래의 $td_B$를 사용하지 않고도 생성 가능하므로, 암호문 구성 요소를 균일한 값으로 교체하는 과정에서도 비밀키 생성이 가능하게 됩니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1 제안된 CP-ABE 방식의 파라미터

$\lambda$를 보안 파라미터, $d$를 회로 깊이, $s$를 회로 크기, $\ell$을 입력 비트 수라고 할 때:

• **암호문 크기 ($|ct|$):**$O(1)$(회로 깊이$d$, 크기$s$, 입력 길이$\ell$에 무관). 이는 점근적으로 최적입니다.
• **공개키 크기 ($|pk|$):**$O(s)$ (회로 크기에 비례).
  • 주석: 공개키의 대부분은 균일하게 샘플링된 요소들이므로, 의사난수 생성기 (PRG) 를 사용하여 실제 저장 크기를 $O(1)$로 압축할 수 있습니다.
• **비밀키 크기 ($|sk|$):**$O(\ell)$ (속성 개수에 비례).
  • 사용자가 가진 속성 수가 $O(1)$인 경우, 비밀키 크기도 $O(1)$로 줄일 수 있습니다.

3.2 브로드캐스트 암호화 (Broadcast Encryption) 적용

NC1 회로를 사용하여 $N$명의 사용자 중 특정 사용자 집합에 대한 멤버십을 확인하는 방식으로 변환합니다.

• 파라미터:
  • $|pk| = poly(\lambda)$ (PRG 압축 적용 시)
  • $|sk| = poly(\lambda, \log N)$
  • $|ct| = poly(\lambda)$ (사용자 수 $N$에 무관)
• 이는 기존에 비해 암호문 크기가 $N$이나 $\log N$에 의존하지 않는 최적의 브로드캐스트 암호화를 제공합니다.

3.3 보안성

• 가정: $poly(\lambda)$-succinct LWE 가정 (Wee24).
• 모델: 표준 모델 (Standard Model) 에서 선택적 안전성 (Selective Security) 을 보장합니다.
• 협동 공격: 무제한의 협동 (Unbounded Collusions) 에 대해 안전합니다.

4. 기존 연구와의 비교 (Comparison)

• Wee25 와의 비교:
  • 장점:
    1. 암호문, 공개키, 비밀키 크기가 회로 깊이 $d$에 무관합니다.
    2. 브로드캐스트 암호화에서 암호문 크기가 사용자 수 $N$의 로그 ($\log N$) 에도 무관합니다.
    3. 암호화 과정에서 단일 행렬 커밋먼트만 수행하여 효율성이 높습니다.
  • 단점:
    • 지원되는 접근 정책의 범위가 더 좁습니다 (NC1 회로에 국한).
    • 비밀키 크기가 Wee25 에 비해 더 클 수 있습니다.

5. 의의 및 결론 (Significance)

이 논문은 양자 내성 (Post-Quantum) 암호화 분야에서 중요한 진전을 이룹니다.

1. 효율성 극대화: NC1 회로 기반 CP-ABE 에서 암호문 크기를 상수로 줄인 것은 실용적인 측면 (대용량 데이터 암호화, IoT 환경 등) 에서 매우 중요합니다.
2. 새로운 보안 기반: Wee24 의 Succinct LWE 가정을 활용하여, 기존의 복잡한 가정 (Evasive LWE 등) 없이도 강력한 보안을 제공하면서도 효율적인 파라미터를 달성했습니다.
3. 브로드캐스트 암호화 최적화: 사용자 수가 늘어나도 암호문 크기가 증가하지 않는 브로드캐스트 암호화 방식을 제안하여, 대규모 사용자 환경에서의 적용 가능성을 높였습니다.

요약하자면, 이 연구는 Succinct LWE와 행렬 커밋먼트를 결합하여 상수 크기의 암호문을 갖는 효율적이고 안전한 CP-ABE 및 브로드캐스트 암호화 체계를 최초로 제안한 것으로 평가됩니다.