『耐量子計算機暗号』読書メモ

1. 暗号分野への導入

2022-07-23

1.1 計算量的安全性と公開鍵暗号

• 暗号: 情報に対する安全性を保証する技術の総称

  • 秘匿化
  • 認証
  • 署名: 署名鍵と検証鍵で

• 共通鍵暗号

  • onetime padは究極形
    • Perfect Secure を実現
    • cons: 鍵長と平文長が同じ = 1GBのデータには1GBの鍵が必要
    • 1つの鍵に対して1回しか使えない
    • 鍵配送を考えなれけば行けない

• 現実的に解読するのに沢山時間がかかる: 計算量的安全性

• DH鍵共有

• ディフィーとヘルマンが鍵を公開鍵と秘密鍵に分けるアイデア

  • 具体的な構成は RSA暗号 が与えたが形が結構違う
  • より直接的な形として ElGamal暗号

1.2 アルゴリズムと計算量

• オーダーの話

1.2.1 確率的(乱択)アルゴリズムと乱数の近似

確率的アルゴリズム $\mathcal{A}$ に対し, 入力 $x$, 乱数 $r$ で $\mathcal{A}(x;r)$

def. 1.2.5 統計距離

有限集合 $S$ に値をとる確率変数 $X,Y$ に対して

$$\Delta (X,Y):=\frac{1}{2}\sum _{s\in S}|Pr[s\leftarrow X]-Pr[s\leftarrow Y]|$$

• 計算機での乱数は独立したランダムなビット列だけど連続的な確率分布に十分近似できる

• $E^{+}=\{s\mid Pr[s\leftarrow X]>Pr[s\leftarrow Y]\}$ に対して

$$\Delta (X,Y)=\sum _{s\in E^{+}}(Pr[s\leftarrow X]-Pr[s\leftarrow Y])$$

lem. 1.2.6

有限集合 $A$ に値を取る $X,Y$
有限集合 $B$ に値を取る $Z$ ($X,Y$ とは独立)

この時, 関数 ${}^{\exists }f$ について,

$$\Delta (f(X,Z),f(Y,Z))\le \Delta (X,Y)$$

ただし, 関数 $h$, 有限集合 $D$ について, $h(D)$ を

$$Pr[a\leftarrow h(D)]=\sum _{b\in h^{-1}[a]}Pr[b\leftarrow D]$$

$X$ を十分な精度で近似できれば $Z=f(X)$ も十分な精度で近似できることを示す

ex. 1.2.7

• $N$: $k$ bits, $X:=\{0,\cdots ,N-1\}$ 一様.
• $X$ を近似するために, 整数 $\ell \ge k$ を決めて $r\in \{0,1{\}}^{\ell }$, $Y:=r\mathrm{mod}N$ で表される
  • $2^{\ell }=QN+R,Q:=\lfloor \frac{2^{\ell }}{N}\rfloor ,R:=2^{\ell }\mathrm{mod}N$
  • $Y$ の値の候補 $a$ で, $Y=a$ となる $r$ は $Q$ 個 ($a\ge R$) か $Q+1$ 個($a<R$) なので
  • $Delta(X,Y)=R(\frac{Q+1}{2^{\ell }}-\frac{1}{N})$

以降この近似手法を前提に

1.2.2 アルゴリズムの空間計算量とクエリ計算量

• oracle $\mathcal{O}$ へのクエリ $q$ を使うモデルも考えられる
• oracle $\mathcal{O}$ を用いたアルゴリズム $\mathcal{A}$ を ${\mathcal{A}}^{\mathcal{O}}$ で表す
  • 演算は $\mathcal{O}(1)$ で出来る
  • クエリ計算量で何回アクセスするかが考慮される

1.3 暗号技術の安全性定義の例

• 安全性を評価するために攻撃アルゴリズムの安全性の下界を与えたい
  • が, 現時点では極めて困難
• 証明可能安全性 では計算量的安全性を絶対ではなく相対評価している
  • この問題が不可能ならばこの暗号を破るのも不可能

1.3.1 暗号技術の定式化

• セキュリティパラメータの話

def. 1.3.1 公開鍵暗号化方式

• 方式は scheme と呼ばれることが多い

$\Pi =(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$

• keygen: $(\mathrm{pk},\mathrm{sk})\leftarrow \mathrm{Gen}(1^{\kappa })$
• enc: $m\in \mathcal{M},c\leftarrow {\mathrm{Enc}}_{\mathrm{pk}}(m)$
• dec: $c\in \mathcal{C},m^{\prime }\mid \perp \leftarrow {\mathrm{Dec}}_{\mathrm{sk}}(c)$
  • $\perp$ は復号失敗の意

def. 1.3.2 正当性

$\Pi$ が正当であるとは, ${}^{\forall }\mathrm{pk},{}^{\forall }\mathrm{sk},{}^{\forall }m$ で

$${\mathrm{Dec}}_{\mathrm{sk}}({\mathrm{Enc}}_{\mathrm{pk}}(m))=m$$

1.3.2 安全性の定式化

• 攻撃者: 公開鍵と暗号文のみを用いて平文に関する部分的な情報を得ようとする
• Semantic Secure に対する定式化は複雑なので, 具体的なshcemeに適用するのが難しい
  • ので現在の暗号分野では同値な言い換えとして, CPA に対して, IND であることを言う -> IND-CPA
  • 攻撃者と挑戦者による IND-CPA game によって証明
• 現代は IND-CCA game で優位な差がない IND-CCA が標準的な安全性になっている

1.4 暗号技術の安全性証明の例

• 群 の話
• ElGamal暗号 の話
  • DDH assumption

1.4.3 安全性証明の例

• ElGamal暗号 の IND-CPA game におけるPPT adv ${\mathcal{A}}^{\mathrm{Elg}}=({\mathcal{A}}_1^{\mathrm{Elg}},{\mathcal{A}}_2^{\mathrm{Elg}})$ が与えられ
• それに対して, 仮定のアルゴリズム(DDH問題 ${\mathcal{A}}^{\mathrm{DDH}}$) を構成して
• 計算量とadvを議論する

もし, advantage に関して

$$\mathrm{Adv}({\mathcal{A}}^{\mathrm{Elg}})\le P(\kappa )\cdot \mathrm{Adv}({\mathcal{A}}^{\mathrm{DDH}})+ϵ(\kappa )$$

が示せたなら, DDH仮定において, $\mathrm{Adv}({\mathcal{A}}^{\mathrm{DDH}})$ はneglとなり, $\mathrm{Adv}({\mathcal{A}}^{\mathrm{Elg}})$ もneglとなり, IND-CPA が証明で出来る.

• 独特な技法が使われているし, とても長くなる事が多い

• 今回の状況では IND-CPA game の攻撃アルゴリズム ${\mathcal{A}}^{\mathrm{Eig}}$ を 内部で実行する形で ${\mathcal{A}}^{\mathrm{DDH}}$ をうまく構成したい

  • 内部で, IND-CPA game を模倣する(確率的な挙動を十分な精度で近似する)

th. 1.4.4

ElGamal暗号 の IND-CPA 性は DDH assumption に帰着できる

proof1
todo

• 内部のDDH仮定の性質に注目して $\mathrm{Adv}({\mathcal{A}}^{\mathrm{Elg}})=2\cdot \mathrm{Adv}({\mathcal{A}}^{\mathrm{DDH}})$ , 右辺neglより左辺もnegl

proof2
todo

• gameに IND な変更を1回して, advが常に0の自明に困難なgameに変換した

  • 一般にゲームに変換を繰り返して自明に困難なゲームに到達することで元のゲームの困難性を示すのを game-hopping という

• DDH問題 は 離散対数問題 へ帰着される.

  • DDH assumption が成り立つためには 離散対数問題 が計算量的に困難である必要がある
  • 一方で 離散対数問題 が計算量的に困難ならば DDH assumption が成り立つかは未解明
  • 「ElGamal暗号 の IND-CPA 性は 離散対数問題 の計算量的困難性に基づく」としばしば言われる

• NOTE: 問題と困難性の帰着は向きが逆なので注意

問題Aの解からBの解が得られる時

• 問題: BはAに帰着される
• 困難性: Aが成立することはBが成立することに帰着される

1.4.5 Paillier暗号

• Paillier暗号

1.5 実際の利用における安全性の評価

• 無限に大きくした時にneglになるが現実の範囲では全然neglじゃない時もあるので注意

1.5.1 「良い」安全性証明とは

• 攻撃の計算量とadv, 仮定の計算量とadvを $T,ϵ,T^{†},{ϵ}^{†}$

  • $\frac{T^{†}}{T}$, $\frac{{ϵ}^{†}}{ϵ}$ がどちらも $\kappa$ に関してpolyならneglとなり安全性が成り立つ
  • より比が小さい方がタイトな帰着と言われる

• ex. 攻撃が $T=2^{128}$ 程度のものに対する安全性を評価したいとき, 比が $2^{30}$ であれば $T^{†}=2^{148}$ の仮定を考慮すれば良いが差が大きいと要求がより厳しくなる

• これを 128ビット安全性 という.

  • 最も標準的な基準

• 最新の暗号の安全性を標準的な仮定に帰着できるとうれしい -> 標準仮定

  • ex. 素因数分解の困難性, 離散対数問題の困難性
  • 伝統的な仮定から構成できなかったけど別の仮定を導入したら構成できた事例もある(3章で紹介)
    • LWE仮定とかの話か

1.5.2 暗号の実利用に向けたパラメータ評価

• 素因数分解の高速化は安定期に入っているらしい