当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。
暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。
興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。
暗号文が平文によって一意に決まる暗号形を確定的暗号系という。これに対して、平文mに対する暗号文が複数存在するような暗号系を確率的暗号系という。
例：RSA暗号、Rabin暗号、逆数暗号などの暗号は確定的暗号である。
したがって、このような欠点を持たないためには、最低限確率的暗号系でなければならない。
アタッカーの攻撃パターンと許容範囲というペアで考える。
CPA（Chosen-Plaintext Attacks：選択平文攻撃）を行うこと。
CCA（Chosen-Cipertext Attacks：選択暗号文攻撃）を行うこと。このときは秘密鍵を持っているオラクル（復号アルゴリズム）を使える。 こういう状況は実際にもありえる。例えば、秘密鍵を持っている人がいて、彼が知らずにアタッカーに利用され続けて復号を行っているシチュエーションである。
さらに、オラクルにクエリーを送るタイミングでさらにCCAとCCA2に分類できる。前者は暗号文cを受け取る前にだけオラクルに質問できる。一方、後者は暗号文cを受け取った後であってもオラクルに質問できる。ただし、問題となっているcをクエリーにはできない。
安全性の許容範囲、即ちゴールにはいくつか種類がある。ここまでが許容できる範囲の安全性ということである。
[定義]一方向性（OW）
公開鍵pkおよび暗号文cから平文m全体を求めるのが困難なとき、その暗号系は一方向性の意味で安全であるといわれる。
一般に、xからy=f(x)を計算するのは容易であるが、yからxを求めることが困難なとき、fは一方向性関数と呼ばれる。
[定義]semantic security,semantically secure（SS）
「暗号系がsemantically secure（SS）である」
⇔def「暗号文cから平文mに関するどんな部分情報も漏れない」
⇔def「任意の確率的多項式時間アルゴリズムである敵Aに対して、ある確率的多項式時間アルゴリズムA'が存在し、Aが暗号文cから求めたものと同じものを、A'はcを使うことなく求めることができる」
⇔def「∀A（p.p.a.）,∃A'（p.p.a.）,A(pk,c)=A'(pk)」
[考察1]暗号Π=(KenGen,E,D)の安全性をSSで直接証明したい場合は、帰着法を用いる。
帰着法は、暗号Πを破るalgをBを仮定して、問題Pを解く効率のよいアルゴリズムAを示す方法である。
理想的なΠの安全性とは、Bにとってベストなシナリオ（例えば、単独走行、ネットワーク化なども含む）を許しても、Πのちょっとしたほころび（部分解読など）も見つからないということである。
[考察2]SS⇔INDは証明されているので、SSを証明するときにはINDを証明することが多い。
というのは、SSは意味がわかりやすいが証明はやりにくい（A'というシミュレータを作ればよいが難しい。つまり、Aの帰着法が作りにくい）。
一方、INDは確率分布の識別になるので意味はちょっとわかりにくいかもしれないが証明はやりやすい。
SS-advantageは次の通りである。
SSとは次が成り立つことである。
[定義]IND（indistinguishability）
「公開鍵暗号系が識別不可能性（indistinguishability）の意味で安全」
⇔def「平文m0が入った封筒c0と平文m1が入った封筒c1があったときに、2つの封筒はまったく見分けがつかない」
⇔def「平文mの暗号文の集合をE(m)で表すことにする。どのような2つの平文m0,m1に対しても、E(m0)とE(m1)が多項式時間では識別不可能」
⇔def「敵が上記のようなm0,m1を効率よく求めることができないことが不可能であればよい」
⇔def「敵がオラクルπに（m0,m1）ペアを送りつけて、オラクルπはランダムに1ビットを選びそれをbとし、c=E(mb)を求め、cをAに返す。Aはcからbの値を推測し、^bとする。b=^bなら推測に成功したということである。
このとき、|Pr(敵が推測に成功）-1/2|≦εが成り立つ。ただし、∃ε：neg」
[定理]SS⇔IND
「公開鍵暗号系がSSである」⇔「公開鍵暗号系が識別不可能性の意味で安全」
[証明]
[1]SS⇒IND
どんな敵にもアドバンテージがないことを示す。
A(pk,cb)＝∃A'(pk) ←右辺はcbを使わずに計算できること。
∴Pr[^b=b]=1/2
[2]IND⇒SS
∀A：PPA
「∃A',A(pk,c)=A'(pk)」がいえればよい。
Aの出力とA'の出力が同じでないと仮定して、矛盾を示す。
「A(pk,c)≠A'(pk)」
⇒「A(pk,c)≠A(pk,c0」 （∵AはINDだからc0の代わりにcを入れても出力は同じ）
⇒以下のA''はINDを破っている。
よって、区別して出力できている。矛盾が生じた。
したがって、（Aの出力）＝（A'の出力）となる。 (Q.E.D.)
SSというのは、(N,e,c)から敵が平文Mの部分情報を求めることに対する安全性である。一方、OWは(N,e,c)から敵が平文全体Mを求めることに対する安全性である。
当然、OWよりSSの安全性がのほうがきつい条件であるので、もしSSが成り立つなら、自動的にOWも成り立つ。よって、次が成り立つ。
SS⇒OW
ちなみに、完全鍵解読というのは、(N,e)から敵が秘密鍵dを求めること。これはRSA仮定、素因数分解困難性を破る敵なら解読成功する。
OWと鍵完全解読の安全性を比較すると、OWのほうが条件がきつい。よって、次が成り立つ。
OW⇒鍵完全解読に対して安全
[定義]NM
暗号文から別の暗号文を作るのが難しいということ。
平文空間が総当りで調べられないほど大きい場合という前提の上でこの強弱関係が成り立つ。なぜならば、平文空間が総当りで攻撃できれば、一方向性（OW）自体が安全性として妥当ではないからである。よって、平文空間にこうした制限がある場合は、OWの列を削ったバージョンの表になる。
例：IND-CCA2の定義
山勘でもアドバーサリーは1/2で当たるので、1/2を基準にしてどのくらい離れているか調べているのである。
