A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

기술 요약: 다중 사용자, 다중 챌린지 환경에서 긴밀하게 안전한 브로드캐스트 인증 키워드 검색 (BAEKS)

1. 문제 정의

검색 가능 암호화(Searchable Encryption, SE)는 사용자가 암호화된 데이터에 대해 검색할 수 있게 해준다. 공개키 키워드 검색(PEks)은 이를 가능하게 하지만, 키워드 추측 공격(Keyword Guessing Attack, KGA)에 취약하다. 이는 공격자가 트랩도어(trapdoor)를 테스트하기 위해 사이퍼텍스트(ciphertext)를 생성하여 키워드를 유추하는 방식이다. 이를 완화하기 위해, 송신자의 비밀키를 암호화에 요구하는 PAEKS가 도입되었다. 이는 이후 송신자가 허가된 수신자 집단에게 키워드를 암호화할 수 있도록 지원하는 BAEKS로 일반화되었다.

기존의 BAEKS 및 PAEKS 연구에도 불구하고 몇 가지 결정적인 격차가 남아 있다:

• 보안 모델: 기존 방식들은 실제 배포 시스템에서 더 현실적인 다중 사용자, 다중 챌린지 환경에 대한 보안 정의가 부족한 경우가 많다. 구체적으로, 이들은 적응적 부패(adaptive corruptions)(공격자가 사용자의 비밀키를 획득하는 상황)와 인터리브드 쿼리(interleaved queries)(공격자가 사이퍼텍스트와 트랩도어를 동시에 챌레인지하는 상황)를 고려하지 못한다.
• 긴밀성(Tightness): 현재의 보안 환원은 비사소한 곱셈적 보안 손실(예: 쿼리 또는 사용자의 수에 비례함)을 겪으며, 이는 시스템이 확장됨에 따라 보안 보장이 크게 저하됨을 의미한다.
• 일관성(Consistency): BAEKS(특히 Emura의 연구)의 계산적 일관성에 대한 기존 증명은 불완전하거나 공식적인 환원 논거가 부족한 것으로 확인되었다.
• 익명성: 많은 방식이 강력한 공격자 모델 하에서 사이퍼텍스트와 트랩도어 모두에 대해 키워드, 송신자 식별자, 그리고 수신자 식별자를 동시에 숨기지 못한다.

2. 방법론 및 구성

저자는 Type-3 양의 쌍선형 그룹(bilinear pairing groups)에서 구축된 새로운 BAEKS 방식인 baeks를 제안한다. 방법론은 다음과 같다:

• 새로운 보안 정의: 본 논문은 공격자가 사이퍼텍스트, 트랩도어, 비밀키에 대해 인터리브드 챌린지 쿼리를 수행할 수 있는 full-cfa 보안 정의를 도입한다. 또한, 저자는 full-cfa 보안에 의해 함의된다고 주장하는 위조 불가능성(unforgeability) 개념(ct-cma 및 trap-cma)을 정의한다.
• 인코딩 전략: 선형 의존성으로 인해 다중 챌린지 환경에서 무너지는 기존의 Boneh-Boyen 해시 인코딩과 달리, 저자는 무작위화된 Naor-Reingold PRF 구조를 사용하는, 긴밀하게 안전한 ID 기반 암호화(IBE) 및 계층적 IBE(HIBE)에서 영감을 얻은 구조를 채택한다.
  • 사용자는 행렬 $U_j$ (송신자)와 $V_j$ (수신자)로 표현된다.
  • 키워드는 행렬 $K_{\iota, b}$를 통해 인코딩된다.
  • 튜플 $(S, \omega, R)$은 이러한 구성 요소들의 합으로 인코딩된다: $\sum U_{S,i} + \sum K_{\omega,i} + \sum V_{R,i}$.
  • 무작위성은 사이퍼텍스트 및 트랩도어 인코딩에 $RF(S||\omega||R)$라는 무작위 함수를 통해 주입된다.
• 증명 기법: 보안 증명은 일련의 게임($G_0$부터 $G_6$)을 포함하는 **하이브리드 논법(hybrid argument)**을 활용한다. 핵심 구성 요소는 특정 오라클 쿼리 하에서 시스템의 구별 불가능성을 확립하는 핵심 레마(Core Lemma) (정리 2)이다. 증명은 Lateral Matrix Diffie-Hellman (lat-MDDH) 가정을 기반으로 한다.
  • 저자는 챌린지받지 않은 사용자의 비밀키가 노출되더라도, 챌린지받은 사용자의 키의 엔트로피가 탐지 없이 무작위성을 주입하기에 충분하도록 보장함으로써 적응적 부패를 처리한다.
  • 저자는 공격자가 챌린지 사이퍼텍스트나 트랩도어에 관여된 사용자의 비밀키를 쿼리하는 것을 제한함으로써 "비사소성(non-triviality)" 조건을 다룬다.

3. 주요 기여

1. 새로운 보안 정의: 본 논문은 다중 사용자, 다중 챌린지, 적응적 부패 및 인터리브드 쿼리를 포함하는 BAEKS를 위한 full-cfa 보안을 정의한다. 이는 긴밀한 보안(보안 환원 손실이 쿼리 수와 무관하게 상수인 것)을 달라는 첫 번째 BAEKS(및 PAEKS) 정의이다.
2. 긴밀하게 안전한 구성: 저자는 표준 모델에서 표준 lat-MDDH 가정 하에 적응적 full-cfa 보안을 달성하는 새로운 BAEKS 구성을 제시한다. 이를 단일 수신자로 제한하면 긴밀하게 안전한 PAEKS가 된다.
3. 위조 불가능성: 본 논문은 제안된 full-cfa 보안 개념이 사이퍼텍스트와 트랩도어 모두에 대한 위조 불가능성을 본질적으로 함의함을 입증한다.
4. 일관성 분석: 저자는 기존 연구(특히 Emura의 연구)의 일관성 증명을 엄밀하게 분석하여 격차를 식별하고, 자신의 방식에 대해 통계적으로 일관된 구성을 제공한다.
5. 구현: 본 방식은 Charm 프레임워크를 사용하여 Python으로 구현되었다. 가상 머신에서 실험을 수행하여 수신자 수($\ell$), 보안 수준($k$), 키워드/사용자 공간 크기($\alpha, u$)에 따른 성능을 평가하였다.

4. 결과

• 보안: 본 방식은 표준 모델에서 lat-MDDH 가정 하에 안전함이 증명되었다. 보안 환원은 긴밀하며(tight), 기존 BAEKS 및 PAEKS 방식에서 발견되는 곱셈적 손실($\Theta(|Q_{Ct}| + |Q_{Tr}|)$)을 피한다.
• 성능:
  • Setup 및 KeyGen: 이는 시스템/사용자당 한 번 실행된다. 설정 복잡도는 키워드 공간 크기 $\alpha$에 따라 선형적으로 확장된다.
  • SrchEnc 및 TrapGen: 이들은 효율적이다. 암호화 및 트랩도어 생성 비용은 사용자 수 $u$와 무관하며, 키워드 길이 $\alpha$와 수신자 수 $\ell$에 따라 선형적으로 확장된다.
  • Test: 클라우드 서버는 매칭을 검증하기 위해 $2\ell$번의 쌍선형 패링(bilinear pairings)을 수행한다. PAEKS($\ell=1$)의 경우, 이는 2번의 패링만을 필요로 한다.
  • 실험 데이터: 저자는 $\ell=1$ (PAEKS)인 경우, 본 방식이 기존 연구들과 대등한 효율성을 제공하면서도 더 긴밀한 보안을 제공한다고 보고한다. $\ell$이 커질 경우 오버헤드가 발생하지만 관리 가능한 수준이며, Mukherjee [42]의 통계적 일관성 방식에 비해 사이퍼텍스트/키 크기는 약간 덜 효율적이지만 보안 보장 측면에서는 우수하다.

5. 의의 및 주장

본 논문은 가장 현실적인 위협 시나리오인 적응적 부패와 인터리브드 챌린지를 포함하는 다중 사용자 환경을 다룸으로써 기존 BAEKS 보안 모델을 개편한다고 주장한다. 주요 의의는 BAEKS 및 PAEKS를 위해 이전에 미해결 과제였던 **긴밀한 보안(tight security)**을 달성했다는 점에 있다.

저자는 자신의 BAAKS 구성이 다음을 동시에 보장하는 최초의 형식화라고 강조한다:

• 키워드 은닉.
• 송신자 및 수신자 익명성.
• 적응적 부패에 대한 저항성.
• 긴밀한 보안 환원.

본 논문은 현재의 구성이 실용적인 개념 증명(proof-of-concept)임을 언급하며 겸허히 결론짓는다. 향후 연구는 자신만의 키 쌍을 생성하는 악의적인 공격자에게도 견고한 구성을 목표로 할 수 있으며, 잠재적으로 사이퍼텍스트 크기를 더욱 최적화할 수 있다. 또한, 본 연구는 BAEKS 구성의 긴밀한 보안이 즉각적으로 PAEKS의 긴밀한 보안으로 이어진다는 점을 강조하며, 단일 수신자 인증 검색 가능 암호화의 공백을 메운다.