これえぐいっすね (DSSE＆Forward Privacy＆verifiableを同時に実現した研究)

2026-08-06 2026-08-19

sgt

本論文は，クラウド上に暗号化したデータを保存しながら検索できる
Dynamic Searchable Symmetric Encryption（DSSE）に対して，
「クラウドが返した検索結果は本当に正しいのか」を検証できる仕組みを追加する研究である．

特に，既存のDSSEが抱える
クラウドによる検索結果の改ざんという問題に対して，
Forward PrivacyとPublic Verifiabilityを両立することを目的としている．

論文全体の核心

この論文を一言で表すと，

「検索可能暗号で検索できるだけではなく，
クラウドが返してきた検索結果が正しいことまで第三者が検証できるようにする」

という研究である．

通常のDSSEでは，クラウドは暗号化された検索インデックスを使って検索結果を返す．
しかし，クラウドが悪意を持っている場合，
「本来10件あるのに5件しか返さない」
「別のキーワードの結果を返す」
「結果の文書IDを改ざんする」
といった攻撃が可能になる．

本論文では，この検索結果の正しさを，
BLS署名，HMAC，PRFなどを利用して検証可能にする．

また，DSSEではデータ追加時に過去の検索結果との関係が漏れる問題があるため，
Forward Privacyも維持する．

第1章 Introduction

1.1 背景

クラウドに機密データを保存する場合，
クラウドを完全には信用できないため，データを暗号化して保存したい．

しかし，データを普通に暗号化すると，
クラウド側ではデータの内容を検索できなくなる．

そこでSearchable Symmetric Encryption（SSE）を利用する．
SSEでは，データを暗号化したまま，
クラウド上でキーワード検索を実行できる．

さらに，データの追加・削除などの更新をサポートしたものが
Dynamic SSE（DSSE）である．

1.2 問題点

既存の多くのDSSEでは，クラウドは
honest-but-curious，
つまり「プロトコルには従うが，できるだけ情報を盗もうとする」
サーバとして想定されている．

しかし，クラウドがmaliciousだった場合，
プロトコルそのものを破って，
検索結果を意図的に改ざんする可能性がある．

本来の検索結果の一部だけ返す
別のキーワードの結果を返す
文書IDを書き換える
検索結果を勝手に削除する

そこで，
「暗号化されているから内容は守られている」
だけでは不十分で，
検索結果そのものが正しいことを検証する必要がある
と論じる．

1.3 本論文の貢献

検証可能DSSEの形式的な定義を与える．
既存のSSEを検証可能にする汎用的な方式 Ψs を提案する．
Forward Privacyを持つDSSEを，Publicly Verifiableにする汎用的な方式 Ψf を提案する．
所有者側に検証用の追加ストレージを必要としない．
所有者側の計算量を小さく抑える．
ランダムオラクルモデルで適応的安全性を証明する．

第2章 Related Works

ここでは，SSE，DSSE，Forward Private SSE，Verifiable SSEなど，
それまでの研究を整理している．

2.1 SSEからDSSEへ

SSEによって暗号化データのキーワード検索が可能になった．
その後，実際のデータベースではデータが追加・削除されるため，
動的な更新を扱えるDSSEが研究された．

2.2 Forward Privacy

DSSEでは，データ追加時に
「この新しい文書が，過去に検索されたどのキーワードに対応するのか」
がクラウドに分かってしまう問題がある．

これを防ぐ性質がForward Privacyである．

本論文では，
新しくキーワード・文書の組を追加しても，
それが過去の検索結果にどのように対応するかを
クラウドが知ることができない性質として扱っている．

2.3 Verifiable SSE

既存研究には，
検索結果が正しいことを検証するVerifiable SSEが存在する．

しかし，

所有者だけが検証できるPrivate Verifiability
第三者も検証できるPublic Verifiability
動的更新
Forward Privacy

をすべて同時に満たすことは難しい．

特に本論文は，
Forward Private DSSE + Public Verifiability
を狙っている．

第3章 Preliminaries

この章は，本論文の方式を理解するために必要な暗号技術，
システムモデル，安全性の定義を説明する章である．

3.1 Cryptographic Tools

主に以下の暗号要素を利用する．

双線形写像（Bilinear Map）
双線形ハッシュ（Bilinear Hash）
BLS署名
暗号学的ハッシュ関数
PRNG / PRF
HMAC

特にBLS署名が，
「検索結果に対応する署名を作り，
その署名を使って検索結果の正しさを第三者が検証する」
ために重要になる．

3.2 System Model

システムには3者が存在する．

Owner：データ所有者かつ検索者
Cloud：暗号化データと検索インデックスを保存・検索するサーバ
Auditor：クラウドの検索結果を検証する第三者

Cloudはmaliciousと仮定する．
つまり，正しい検索結果を返すとは限らない．

一方，Auditorはhonest-but-curiousであり，
Cloudとは共謀しないと仮定する．

3.3 Design Goals

本論文の目標は主に4つである．

Confidentiality：クラウドに平文情報を漏らさない．
Efficiency：計算能力の低いOwnerの負担を小さくする．
Scalability：大量のデータをクラウドへ預けられる．
Forward Privacy：データ追加によって過去の検索情報を漏らさない．

3.4～3.5 VDSSEの定義

VDSSEは，

Dynamic Searchable Symmetric Encryption
＋
Verifiability

と考えればよい．

つまり，
「暗号化したまま検索できる」
＋
「検索結果が正しいか確認できる」
という仕組みである．

3.6 Security Definitions

安全性を大きく2つに分ける．

Confidentiality

許可された漏洩以外の情報をクラウドへ与えないこと．

Soundness

クラウドが嘘の検索結果を返しても，
検証で発見できること．

本論文では，特に
「クラウドが誤った検索結果を返して，
それなのに検証を通過してしまう」
ことが起こらないことをSoundnessとして定義する．

第4章 Verifiable SSE with Static Data

ここではまず，
データが更新されない静的SSE
を検証可能にする方法を考える．

4.1 既存方式の問題

例えばキーワード「猫」に対応する文書IDが，

doc1
doc2
doc3

だったとする．

これらを連結してハッシュし，

tag = H(doc1 || doc2 || doc3)

のようなタグを作れば，
検索結果が正しいか確認できそうに見える．

しかし，このタグまでクラウドへ預けると問題がある．

例えば本来「犬」の検索結果を返すべきところに，
過去に得た「猫」の検索結果とタグをそのまま返せば，
単純な整合性確認を通過できてしまう可能性がある．

つまり，
単純に検索結果へハッシュを付けるだけでは，
悪意あるクラウドを十分に防げない
と指摘する．

4.2 提案する汎用方式 Ψs

本論文では，
既存のSSE方式に追加情報を付与することで，
検証可能にする汎用的な構成を提案する．

各キーワードについて，
そのキーワードに対応する文書ID列からタグを作る．

tag_w = H(k_w || id1 || id2 || ... || idc)

ここでk_wはキーワードに対応する秘密情報である．

検索時には通常のSSE検索を実行し，
得られた文書ID列から再びタグを計算する．

そのタグが保存されているタグと一致すれば，
検索結果を受理する．

この章のポイント

「既存SSEを作り直すのではなく，
検証用のタグを追加するだけで検証可能にする」

という汎用的なアイデアを示している．

Owner側は検索結果についてハッシュ値を1回計算する程度の
小さな追加計算で検証できるとしている．

第5章 Proposed Forward Secure Publicly Verifiable DSSE

ここがこの論文の本丸である．

第4章では静的SSEを検証可能にした．
第5章ではさらに，

Dynamic
Forward Private
Publicly Verifiable

を同時に実現する．

5.1 基本方針

既存のForward Private DSSEを
Σf
とする．

本論文の方式Ψfは，
このΣfを丸ごと置き換えるのではなく，
検証用の暗号化データ構造を追加する
という考え方を取る．

つまり，

既存Forward Private DSSE
        ＋
検証用の仕組み
        ↓
Forward Private
Publicly Verifiable
DSSE

という構造になっている．

5.2 何を保存するのか

各キーワードwについて，
そのキーワードを含む文書数cwをOwner側で管理する．

また，

Ks：検索用のseed生成に利用
Kt：keyword tag生成に利用
sk / pk：BLS署名の秘密鍵・公開鍵
KΣf：組み込むForward Private DSSEの鍵

などを用意する．

5.3 Keyword Tag

各キーワードについて，

tag_w = F(Kt, w)

のような固定タグを作る．

ただし，このタグそのものからキーワードが分からないようにする．

5.4 Keyword-Document Pairごとの位置

キーワードwと文書ID idの組ごとに，

pos = F(tag_w, id || i)

のような位置情報を作る．

このposを，クラウド上の署名テーブルTsigの
key-value構造におけるキーとして利用する．

重要なのは，

クラウドは検索結果として正しい文書IDを得ない限り，
対応する署名の位置を正しく求められない

という点である．

5.5 BLS署名

各keyword-document pairについて署名を作る．

署名は単純に文書IDだけへ付けるのではなく，
キーワードとランダム値などと結び付ける．

これにより，
「別のキーワードの検索結果を流用する」
「文書IDを改ざんする」
といった攻撃を検証で検出できる．

5.6 Initialization

初期化時には，

秘密鍵・公開鍵を生成する．
既存のForward Private DSSEの鍵を生成する．
検索用seedとtag用の秘密値を生成する．
各keyword-document pairについて署名を作る．
署名を位置情報と対応付けてTsigへ格納する．
通常のForward Private DSSEの検索インデックスも構築する．
γ，暗号化DB，Tsigをクラウドへ預ける．

5.7 Search Phase

「猫」で検索するとする．

Ownerはまず，
組み込まれているForward Private DSSEの検索トークンを生成する．

さらに，

tag_cat
seed_cat

を生成してクラウドへ渡す．

クラウドは通常のDSSE検索を実行して，
文書ID集合を得る．

例えば，

doc1
doc2
doc3

が得られたとする．

クラウドは各文書IDについて対応するposを計算し，
Tsigから対応する署名を取得する．

そして取得した複数の署名をまとめて，
1つの集約署名としてAuditorへ送る．

5.8 Auditorによる検証

Owner側も検索結果を利用して，
ランダム値を使ったメッセージmを生成する．

Auditorには，

Owner側が生成した検証用メッセージ
Cloud側が生成した集約署名

が渡される．

AuditorはBLS署名のVerifyを実行する．

検証に成功すれば，

Cloudが返した検索結果は，正しい結果集合に対応している

と判断できる．

しかもAuditorは検索結果の内容そのものを知る必要がない．

5.9 Update Phase

新しい文書を追加するときは，
その文書に含まれる各キーワードについて処理する．

例えば，

doc4 = 「猫カフェ」

なら，

猫 → doc4
カフェ → doc4

それぞれについて，
Forward Private DSSEの更新処理と，
検証用のposition・署名の追加を行う．

クラウドには単純なkey-value pairとして追加されるため，
追加されたデータから直接キーワードを推測することが難しい．

5.10 Forward Privacy

本方式では，新しいkeyword-document pairを追加しても，
その追加データが過去の検索結果のどれに対応するのかを
クラウドが直接判断できないようにする．

特に，文書IDからクラウド上の文書名を直接復元できないように
一方向関数H0を利用する．

そのため，
新しい文書の追加と過去の検索結果とのリンクを
クラウドから隠すことを狙っている．

5.11 Soundness

クラウドが不正な結果を返す場合について検討している．

主に以下の3種類を考える．

文書IDの数を勝手に変える．
別のキーワードと同じ件数の結果を返す．
文書IDそのものを改ざんする．

しかし署名がキーワードやランダム値などと結び付いているため，
改ざんされた結果では署名検証に失敗すると説明している．

5.12 Deletion Support

削除にも拡張可能としている．

追加用の方式とは別に，
削除されたファイルを扱うための複製された構造Ψ'fを保持する．

検索時には追加側と削除側の両方を検証し，
最終的な結果を差し引きによって求める．

第6章 Comparison with Existing Schemes

既存の検証可能DSSE方式と，
本論文のΨfを比較している．

6.1 本方式の特徴

本方式Ψfは，

Forward Privacy：あり
Public Verifiability：あり
Owner側の追加ストレージ：O(1)
Cloud側の追加ストレージ：O(N)
Owner側の検索時追加計算：O(|Rw|)
Auditorとの追加通信：O(1)

という特徴を持つ．

ここでNはkeyword-document pairの総数，
|Rw|は検索結果数である．

6.2 Owner側の負担

この論文が特に重視しているのが，
Owner側を軽量にすること
である．

Cloudは計算資源が豊富である一方，
Ownerは計算能力やストレージが限られていると仮定している．

そのため，
検証処理の一部をAuditorへ移し，
Ownerの負担を小さくする．

本方式では，
検索結果の件数に比例した整数の乗算・加算をOwnerが行う必要があるが，
他方式と比較して小さいとしている．

6.3 ストレージコスト

検証用の署名をkeyword-document pairごとに保存するため，
Cloud側の追加ストレージはO(N)となる．

つまり，

検索可能暗号のインデックス
+
検証用署名テーブル

という構成になる．

一方，
Owner側には検証のための追加ストレージを要求しないことが特徴である．

第7章 Conclusion

本論文では，

Forward Private DSSE
＋
Public Verifiability

を実現する汎用的な方式を提案した．

また，
静的SSEを検証可能にする方式Ψsと，
動的かつForward PrivateなDSSEを検証可能にする方式Ψfを示した．

どちらも比較的単純な構造で実装可能であり，
特にリソースの少ないOwner側の計算量・通信量を抑えることを目標としている．

一方で，
本論文の方式は単一キーワード検索を対象としている．

今後の課題として，

複合キーワード検索
Boolean Query
より複雑なクエリ
Forward Privacyを維持した複雑な検索

などが挙げられている．

この論文を超ざっくり図解すると

【通常のDSSE】

Owner
  │
  │ 検索トークン
  ▼
Cloud
  │
  │ 検索
  ▼
検索結果
  │
  ▼
Owner


問題：
Cloudが嘘の結果を返しても分からない


────────────────────────


【この論文】

Owner
  │
  ├──── 検索トークン ──────► Cloud
  │                              │
  │                              │ 検索
  │                              ▼
  │                         検索結果＋署名
  │                              │
  │                              ▼
  │                           Auditor
  │                              │
  │                         署名を検証
  │                              │
  │                              ▼
  │                       「正しい／不正」
  │
  └──────── 検証用情報 ───────► Auditor


ポイント：

① DSSEなので暗号化したまま検索できる
② Dynamicなのでデータを追加できる
③ Forward Privateなので追加による情報漏洩を抑える
④ Publicly Verifiableなので第三者Auditorが結果を検証できる
⑤ Owner側の負担を小さくする

あなたの研究との関係

この論文をあなたの研究の文脈で読むなら，
特に重要なのは「検索可能暗号そのもの」より，
検索結果の信頼性をどう担保するかという部分である．

あなたのOS統合型検索可能暗号システムに当てはめると，
現在の基本構造が，

OS
 ↓
検索トークン生成
 ↓
クラウド
 ↓
暗号化DBを検索
 ↓
結果を返す

だとすると，
本論文はその後ろに，

クラウド
 ↓
「本当に正しい検索結果を返した？」
 ↓
Auditor / 検証処理

を追加する研究だと考えると分かりやすい．

特に重要なのは，

「暗号化されているのでクラウドから内容を盗まれない」

と

「クラウドが正しい結果を返している」

は別問題だという点である．

前者はConfidentiality，
後者はSoundness / Verifiabilityの問題である．

したがって，
検索可能暗号をOSレベルへ統合する研究を考える場合でも，
「クラウドを信用しなくてよい」とするなら，
「クラウドが返した検索結果自体を信用してよいのか？」
という次の問題が自然に出てくる．

一言でまとめると

この論文は，
「クラウドに暗号化データを預けて検索させるだけではなく，
そのクラウドが返した検索結果が正しいことまで検証できる，
Forward Privateな動的検索可能暗号を作った」
という論文である．

＼ Get the latest news ／

Categories: 研究

Tags: DSSE Forward Privacy 整合性保証