定理(TBE2PKE)の証明 - 暗号理論教室

定理(TBE2PKE暗号)の証明のアイデア

攻撃者Aが構成(TBE2PKE暗号)の公開鍵pkに関する暗号文

• c* = (c*_tbe, vk*, σ*)

を入手したとする。

部品であるタグベース暗号の識別不可能性より、
c*_tbeはその復号文m_bの情報を漏らさない。
また、vk*, σ* はもともとメッセージと無関係なので、もちろん復号文m_bの情報を漏らさない。

攻撃者Aが構成(TBE2PKE暗号)の妥当な暗号文 c = (c_tbe, vk, σ) を生成したとすると、
c ≠ c* より、

• vk = vk*, (c_tbe, σ) ≠ (c*_tbe, σ*)

または、

• vk ≠ vk*

である。

前者ならば、攻撃者Aは部品であるワンタイム署名の強い意味での偽造不可能性を破っている。
後者ならば、タグが異なるということだから、タグ選択暗号文攻撃に関する識別不可能性より、
cの復号文は、攻撃者Aにとって役にたたない。

定理(TBE2PKE)の証明

構成(TBE2PKE)に対する任意のCCA攻撃者をAとする。
Aを用いてTBEに対する(タグ選択)攻撃者Bを構成する：

攻撃者B: (1ⁿ)を入力として、

• ※ Bは最初にタグvk*を選択し、そのタグvk*に関する暗号文c*を破りたい。
• (vk*, sigk*) ← SKG(1ⁿ)
• vk*をチャレンジャーに出力し、 公開鍵pkを受け取る。
• pkを入力としてAを起動する。
  • Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
    • (m₀,m₁)を自身のチャレンジクエリとしてチャレンジャーに出力し、暗号文c_tbe*を受け取る。
    • σ* ← SIGN(sigk*, c_tbe*)
    • c* = (c_tbe*, vk*, σ*)を応答する。
  • Aから復号オラクルに対する問い合わせ(c_tbe, vk, σ)を受け取ったら、
    • VFY(vk, c_tbe, σ) =^? reject : ⊥を返す。
    • else vk =^? vk* : アボート
    • else (vk, c_tbe) を自身の復号オラクルに問い合わせ、受け取った復号文を応答する。
    • ※ vk≠vk* なので、この復号オラクルへの問い合わせは妥当。
• Aが出力b'で停止したら、b'を自身の出力として停止する。

攻撃者Bの解析：
Bがアボートさえ起こさなければ、BのAに対するシミュレーションは完ぺきである。
Aが攻撃に成功するとき、必ずBも攻撃に成功する。
よって、

• (Aの識別利得) - Pr[Bがアボート] ≦ (Bの識別利得).

よって、後は以下の主張を示せばよい。

主張 Pr[Bがアボート] はネグリジブル。
証明 攻撃者Aを用いて、ワンタイム署名OTSの偽造者Fを構成する：

偽造者F: 検証鍵vk*を入力として、

• ※ Fは検証鍵vk*のもとで妥当なメッセージ署名対(c_tbe,σ)を偽造したい。
• (pk, sk) ← Gen_tbe
• pkを入力としてAを起動する。
  • Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
    • b ← {0,1},　c*_tbe ← Enc_tbe(pk, vk*, m_b)
    • c*_tbe を自身の署名オラクルに問い合わせ、署名σ* を受け取る。
    • c* = (c*_tbe, vk*, σ*)を応答する。
  • Aから復号オラクルに対する問い合わせ(c_tbe, vk, σ)を受け取ったら、
    • VFY(vk, c_tbe, σ) =^? reject : ⊥を返す。
    • else vk =^? vk* ：　(c_tbe, σ)を出力して停止。
    • else Dec_tbe(sk, vk, c_tbe) を応答する。
• Aが停止したら、停止する。

偽造者Fの解析：
明らかに、

• Fは署名オラクルに一度しか問い合わせていない。
• Pr[Bがアボート] = Pr[Fが偽造に成功].

よって、OTSは強いワンタイム署名なので、Pr[Bがアボート] はネグリジブルである。
q.e.d.

Q.E.D.

上へ

---