암호화된 데이터에 대한 범위 질의(range query)는 데이터와 질의를 비밀로 유지하면서 빠른 질의 처리를 달성하기 위해 널리 연구되어 왔다. 선행 연구에서는 데이터의 순서(ordering) 정보까지도 숨기지만, 그 대가로 정확성(예: 오탐/위양성, false positives)과 효율성(예: 도메인 크기에 대한 지수적 복잡도, exponential complexity)을 희생해왔다. 또한 순서만 숨기는 것으로는 최근 범위 질의를 악용하는 데이터베이스 재구성 공격(접근 패턴 및 볼륨(volume) 누출에 기반)을 막기에 충분하지 않다. 이러한 정보 누출을 방지하는 몇 가지 대응책이 존재하지만, 데이터베이스에 삽입된 가짜 레코드(fake records)와 데이터베이스 재암호화 절차(database re-encryption procedures)로 인해 실질적으로 받아들이기 어려운 수준의 저장 또는 계산 오버헤드를 초래한다. 본 논문에서는 먼저 높은 효율성을 가지되 순서 정보를 드러내는 범위 질의 방식 RevealRE를 제안한다. 다음으로 RevealRE를 확장하여 데이터의 순서 정보를 누출하지 않으면서 정확함(즉, 오탐/미탐이 없음)과 효율성(즉, 로그 시간의 검색 시간)을 보장하는 범위 질의 방식 HideRE를 구성한다. HideRE는 질의된 범위를 난독화(obfuscating)하는 동시에 정규 질의와 구별되지 않는 기만적 질의(deceptive queries)를 도입함으로써 데이터베이스 재구성 공격을 완화할 수 있다. 다양한 데이터 분포 모델에서의 실험을 통해 본 구성의 효율성이 확인되며, 그 실용성을 입증한다. 데이터베이스 재구성 공격에 대한 본 순서-은닉 범위 질의 방식의 내성은 형식적으로 증명된다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.