約 785,273 件
https://w.atwiki.jp/cryptospace/pages/20.html
公開鍵暗号とその安全性定義識別不可能性選択平文攻撃に対する識別不可能性 選択暗号文攻撃に対する識別不可能性 頑健性 安全な公開鍵暗号の構成選択平文攻撃に対し識別不可能な公開鍵暗号の構成トラップドア置換にもとづく構成 エルガマル暗号 ランダムオラクルモデルにもとづく構成 適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号の構成ジェネリックな構成 ランダムオラクルモデルにもとづく構成CCAinRO 平文検査攻撃における一方向性 REACT 双子エルガマル暗号 ランダムオラクルモデルを必要としない構成Cramer-Shoup暗号 Camenish-Shoup暗号 タグベース暗号タグ選択暗号文攻撃に対する識別不可能性 タグベース暗号から公開鍵暗号への変換 タグ選択暗号文攻撃に対し識別不可能なタグベース暗号の構成判定線形仮定 判定線形仮定にもとづくタグ選択暗号文攻撃に対し識別不可能なタグベース暗号 公開鍵暗号とその安全性定義 公開鍵暗号とは効率的な確率的アルゴリズムの3つ組(Gen, Enc, Dec)である： (pk, sk) ← Gen(1n) c ← Enc(pk, m) m ← Dec(sk, c). 完全性(completeness)条件として、メッセージ空間Mに含まれる全てのメッセージmについて Pr[ (pk, sk) ← Gen(1n), c ← Enc(pk, m), m ← Dec(sk, c) m = m ] = 1 を要求する。 識別不可能性 選択平文攻撃に対する識別不可能性 暗号文がメッセージのどのような部分情報も漏らさないとき、その暗号は識別不可能であるという。 より正確に定義するために、公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する： 試行 CPAΠ,A(n) (pk, sk) ← Gen(1n) pkを入力として攻撃者Aを起動する。 Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら（チャレンジクエリは一度のみ許される）、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： c* ← Enc(pk, mb)。 c*をチャレンジクエリに対する応答として返す。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 定義(IND-CPA) 公開鍵暗号Πが選択平文攻撃に対し識別不可能（IND-CPA）であるとは、 任意の効率的な撃者Aについて、その識別利得 ｜ Pr[ CPAΠ,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 （確率Pr[ CPAΠ,A(n) = 1 ]をAの成功確率と呼ぶ。） もしも、暗号文c*からもとのメッセージの情報が漏れていれば、それを用いて攻撃者Aはもとのメッセージがm0なのかm1なのか、 推測できるはずである。 選択暗号文攻撃に対する識別不可能性 公開鍵暗号を通信環境におけるアプリケーションで利用するためには、 「復号オラクル」を用いることができる、より強力な攻撃者を想定する必要がある。 公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する。 試行 CCAΠ,A(n) (pk, sk) ← Gen(1n) pkを入力として攻撃者Aを起動する。 Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら（チャレンジクエリは一度のみ許される）、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： c* ← Enc(pk, mb)。 c*をチャレンジクエリに対する応答として返す。 Aから復号クエリcを受け取ったら（復号クエリは何度でも許される）、 (c*がすでに定義されていて) c = c* なら⊥を応答する。 c = c* でないならば、その復号結果m ← Dec(sk, c)を応答する。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 定義(IND-CCA2) 公開鍵暗号Πが適応的選択暗号文攻撃に対し識別不可能（IND-CCA2）であるとは、 任意のPPT攻撃者Aについて、その識別利得 ｜ Pr[ CCAΠ,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 （確率Pr[ CPAΠ,A(n) = 1 ]をAの成功確率と呼ぶ。） 適応的選択暗号文攻撃では、 攻撃者Aは、チャレンジャーから受け取った暗号文c*に関連付けて、別の暗号文c を生成する。 復号オラクルを用いてその復号文m を得る。 m からもとの暗号文c*の復号文mbを推測する といった攻撃が典型的である。 上の定義で、攻撃者Aの復号クエリがチャレンジクエリ以前に限定されるとき、 公開鍵暗号Πは非適応的選択暗号文攻撃に対し識別不可能（IND-CCA1）であるという。 頑健性 定義(BR93) 公開鍵暗号Πが頑健であるとは、任意のPPT関係ρ, PPT攻撃者(F,A)に対し、あるシミュレータA*が存在し、 以下のε(k) - ε*(k)がネグリジブルであることをいう： ε(k) = Pr[ (pk,sk) ← Gen(1n), π← F(pk), x ← π, α ← Enc(pk,x), α ← A(pk,π,α) ρ(x, Dec(sk,α ))=1 ] ε*(k) = Pr[ (pk,sk) ← Gen(1n), π← F(pk), x ← π, α ← A*(pk,π) ρ(x, Dec(sk,α ))=1 ] ただし、関係ρは任意のxについて ρ(x,x) = ρ(x,⊥) = 0 であるものとする。 安全な公開鍵暗号の構成 選択平文攻撃に対し識別不可能な公開鍵暗号の構成 トラップドア置換にもとづく構成 定義 (G, {fi}i)がトラップドア置換であるとは、任意の (i, ti) ← G(1n) について、 fi {0,1}n → {0,1}n は一方向置換である。 tiを知っていたら、fi-1(・) は効率的に計算可能である。 ことをいう。tiを（fiの）トラップドアという。 RSA仮定のもとで、RSA関数 fe,N(x) = xe mod N は（dをトラップドアとする）トラップドア置換である。 構成(CPA暗号) (G, {fi}i) トラップドア置換 hci fiのハードコア述語 Gen(1n) (pk, sk) = (i, ti) ← G(1n). Enc(pk = i, m) // m∈{0,1}l r ← {0,1}n fi(r), fi2(r), ..., fil(r) を計算。 p = ( hci(fil-1(r)), hci(fil-2(r)), ..., hc(r) ) return c = (m + p, fil(r)). Dec(sk = ti, c = (m , w)) tiを用いて w=fil(r) から r を求める。 p = ( hci(fil-1(r)), hci(fil-2(r)), ..., hc(r) ) return m - p. 定理(CPA暗号) {fi}iが、ハードコア述語{hci}iをもつ、トラップドア置換ならば、 構成(CPA暗号)の公開鍵暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 エルガマル暗号 (ga,gb)が与えられて、gabを求める問題を計算DH問題と呼ぶ。 計算DH問題は困難であるとの仮定を計算DH仮定という。より正確には、 仮定(CDH仮定) 群生成アルゴリズムGenGに対して計算DH仮定が成り立つとは、 任意の効率的なアルゴリズムAについて、その成功確率 Pr[s=(q,g) ← GenG(1n), a,b ← Zq ： A(s, ga,gb) = gab] がネグリジブルであることをいう。 離散対数問題が解ければ計算DH問題も解けるので、 （すなわち、計算DH問題は離散対数問題ほどには難しくないので、） 計算DH仮定は離散対数仮定より強い仮定である。 計算DH問題は、その答えが与えられてもそれとはわからい（ほどに難しい）、という仮定を判定DH仮定という。 より正確には、 仮定(DDH仮定) 群生成アルゴリズムGenGに対して判定DH仮定が成り立つとは、 任意の効率的なアルゴリズムDについて、その識別利得 ｜ Pr[s=(q,g) ← GenG(1n), a,b ← Zq ： D(s, ga,gb,gab)) = 1] - Pr[s=(q,g) ← GenG(1n), a,b,c ← Zq ： D(s, ga,gb,gc)) = 1] ｜ がネグリジブルであることをいう。 (ga,gb,gab)の形の3つ組をDHタプルと呼ぶ。 注意 判定DH仮定のもとで、 Gg,ga(x) =def (gx, gax) は疑似乱数生成器。 構成(エルガマル暗号) GenG(1n) 群生成アルゴリズム Gen(1n) (q, g) ← GenG(1n), x ← Zq, y = gx pk=(q,g,y), sk = (q,g,x). Enc(pk=(q,g,y), m) // m∈ g r ← {0,q-1}, c1 = gr, c2 = m yr return c = (c1, c2). Dec(sk=(q,g,x), c=(c1, c2)) return c2/c1x. 定理(エルガマル暗号) 群生成アルゴリズムGenGが判定DH仮定を満たすならば、エルガマル暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 ランダムオラクルモデルにもとづく構成 ハッシュ関数G {0,1}* → {0,1}l への呼び出しをランダムオラクルOG(・)への呼び出しに 置き換えてしまう（アルゴリズムの実行）モデルを（Gについての）ランダムオラクルモデルと呼ぶ。 構成(ランダムオラクル) OG 初期化： lビット出力の関数Gをランダムに選択する。 ※ 値xごとに独立なlビット乱数G(x)を選択することと同じ。 問い合わせ x を受け取ったら、 G(x) を返す。 構成(CPAinRO) (Genf, {fi}i) トラップドア置換 Gen(1n) (i,ti) ← Genf(1n) ハッシュ関数 G {0,1}* → {0,1}l を選択 return pk=(i,G), sk = (ti,G). Enc(pk=(i,G), m) // m∈{0,1}l r ← {0,1}n return c = (fi(r), G(r)+m). Dec(sk=(ti,G), c=(y, s)) tiを用いて、r ← fi-1(y) return s - G(r). 定理(CPAinRO) ハッシュ関数Gについてのランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、構成(CPAinRO)は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号の構成 ジェネリックな構成 構成(DDN) (Gen,Enc,Dec) 選択平文攻撃に対し識別不可能な公開鍵暗号 (P, V) 言語Lに対する非対話零知識証明システム ： L = {(c1,...,cn) | ∃m,(w1,...,wn) s.t. ci = Enc(pki, m; wi)} ※ 簡単のため、pkiはciに含まれているとする。 (SigGen, Sign, Verify) ワンタイム署名 公開鍵暗号(Gen , Enc , Dec ) Gen (1n) r ← {0,1}poly(n) i ∈ [1..n] (pki,0,ski,0) ← Gen(1n), (pki,1,ski,1) ← Gen(1n) pk = (r, (pk1,0,...,pkn,0 | pk1,1,...,pkn,1)), sk = (sk1,0,...,skn,0 | sk1,1,...,skn,1). Enc (pk, m) (vk,sk) ← SigGen(1n), (v1,...,vn) = vk i ∈ [1..n] wi ← {0,1}*, ci = Enc(pki,v_i, m; wi) C = (c1,...,cn) Π ← P(r, C, (m,(w1,...,wn))), σ ← Sign(sk, (C,Π)) return (vk,C,Π,σ). Dec (sk,(vk,C,Π,σ)) Verify(vk,(C,Π),σ) =? 0 return ⊥ else V(r,C,Π) =? 0 return ⊥ else return Dec(sk1,vk_1,c1). 定理(DDN) (Gen,Enc,Dec)が選択平文攻撃に対し識別不可能な公開鍵暗号で、 (P,V)が上記の言語Lに対する適応的安全な非対話零知識証明システムで、 (SigGen, Sign, Verify)がストロングワンタイム署名ならば、 (Gen ,Enc ,Dec )は適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号である。 ランダムオラクルモデルにもとづく構成 CCAinRO 構成(CCAinRO) [BR 93] [部品] トラップドア置換 (Genf, {fi}i) ハッシュ関数 G {0,1}* → {0,1}l ハッシュ関数 H {0,1}* → {0,1}n [スキーム] Gen(1n) (i,ti) ← Genf(1n) return pk=(i,G,H), sk = (ti,G,H) Enc(pk=(i,G,H), m) ※ m∈Bl. r ← {0,1}n return c = (fi(r), G(r)+m, H(r,m)) Dec(sk=(ti,G,H), c=(a,w,b)) tiを用いて、r ← fi-1(a) m = w - G(r) H(r,m) =? b return m else return ⊥ 定理(CCAinRO) [BR 93] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、 構成(CCAinRO)は適応的選択暗号文攻撃に対し識別不可能である。 証明 定理(NMinRO) [BR 93] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、構成(CCAinRO)は(BR93の意味で)頑健である。 証明 この構成はトラップドア置換を用いているので、たとえばエルガマル暗号には適用できない。 平文検査攻撃における一方向性 平文と暗号文の対(c,m)を受け取ると、暗号文cの復号結果が平文mと一致するか否かの1ビットだけを 教えてくれるオラクルを平文検査オラクル(PCO)と呼ぶ。 平文検査オラクルを用いることができても、一方向性をたもつ公開鍵暗号を平文検査攻撃に対し一方向であるという。 より正確には： 定義(OW-PCA) 公開鍵暗号(Gen,Enc,Dec)が平文検査攻撃に対し一方向（OW-PCA）であるとは、 任意の効率的な撃者Aについて、その成功確率 Pr[ (pk,sk) ← Gen, m ← M, y ← Enc(pk,m), m ← APCO(sk,・)(y) ： m = m ] がネグリジブルであることをいう。 Gap仮定（判定DH問題を解くオラクルが与えられても、計算DH問題は難しい）のもとで、 エルガマル暗号は平文検査攻撃に対し一方向である。 REACT 構成(REACT) [OP01] (Gen,Enc,Dec) 平文検査攻撃に対し一方向である公開鍵暗号 G {0,1}* → {0,1}l ハッシュ関数 H {0,1}* → {0,1}k ハッシュ関数 REACT = (Gen , Enc , Dec ) Gen () (pk, sk) ← Gen(). Enc (pk, m) // m ∈ {0,1}l r ← M, a ← Enc(pk, r) // Mは(Gen,Enc,Dec)のメッセージ空間 b = m + G(r), c = H(r, m, a, b) return C = (a, b, c). Dec (sk, C=(a,b,c)) r ← Dec(sk, a), m = b - G(r) c =? H(r, m, a, b) return m else return ⊥. 定理(REACT) [OP 01] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 (Gen,Enc,Dec)が平文検査攻撃に対し一方向ならば、 構成(REACT)は適応的選択暗号文攻撃に対し識別不可能である。 証明 双子エルガマル暗号 G= g について、 DHタプル： (g, gx, gy, gxy) 双子DHタプル： (g, gx1, gx2, gy, gx1y, gx2y). 仮定(双子計算DH仮定) 双子DHタプルを判定してくれるオラクルが与えられても、 双子DHタプルの計算は困難であるという仮定を双子計算仮定という。 より正確には、 群生成アルゴリズムGenGに対して双子計算DH仮定が成り立つとは、 任意の効率的なアルゴリズムAについて、その成功確率 Pr[s=(q,g) ← GenG(1n), X1,X2,Y ← g ： A2dhpg(X1,X2,・,・,・)(X1,X2,Y) = 2dhg(X1, X2, Y)] がネグリジブルであることをいう。ここで、 2dhg(X1, X2, Y) =def (gx1 y, gx2 y), 2dhpg(X1, X2, Y, Z1, Z2) =def 『 2dhg(X1, X2, Y) =? (Z1, Z2) 』. 命題(双子計算DH仮定) 計算DH仮定のもとで、双子計算DH仮定は真である。 証明 構成(双子エルガマル暗号) (E, D) 鍵空間Kをもつ共通鍵暗号 H {0,1}* → K ハッシュ関数 Gen(1n) (q, g) ← GenG(1n) x1, x2 ← Zq, X1 = gx1, X2 = gx2 pk=(q,g,X1,X2), sk = (q,g,x1,x2). Enc(pk, m) y ← Zq Y = gy, Z1 = X1y, Z2 = X2y, k = H(Y,Z1,Z2) return (Y, c = E(k, m)). Enc(sk, (Y,c)) Z1 = Yx1, Z2 = Yx2, k = H(Y,Z1,Z2) return m = D(k, c). 定理(双子エルガマル暗号) ハッシュ関数Hに対するランダムオラクルモデルにおいて、 GenGが計算DH仮定を満たし、共通鍵暗号(E,D)が適応的選択暗号文攻撃に対し識別不可能であるならば、 双子エルガマル暗号は適応的選択暗号文攻撃に対し識別不可能である。 ランダムオラクルモデルを必要としない構成 Cramer-Shoup暗号 構成(CS暗号) Gen(1n) ハッシュ関数 H {0,1}* → Zq を選択。 (q, g1, g2) ← GenG(1n) x, y, a, b, a , b ← Zq h = g1x g2y, c = g1a g2b, d = g1a g2b pk = (g1,g2,h,c,d,H), sk = (x,y,a,b,a ,b ). Enc(pk, m) // m ∈ g1 r ← Zq, α = H(g1r, g2r, hrm) return C = (g1r, g2r, hrm, (cdα)r). Dec(sk, C=(u,v,w,e)) α = H(u, v, w) ua+αa vb+αb ≠ e return ⊥ else return w / (uxvy). 定理(CS暗号) ハッシュ関数Hが衝突困難で、GenGが決定DH仮定を満たすならば、 CS暗号は適応的選択暗号文攻撃に対し識別不可能である。 証明 Camenish-Shoup暗号 仮定(DCR仮定) 整数 n (=pq) を与えられて、 Zn2* のランダム要素と(Zn2*)nのランダム要素を識別できない とき、 Decision Composite Residuosity (DCR) 仮定が成り立つという。 abs Zn2* → Zn2* abs(a) = (n2 - a) mod n2 ( if a n2 / 2 ) abs(a) = a mod n2 otherwise 構成(Camenish-Shoup暗号) Gen(1l) ハッシュ関数 H {0,1}* → [2l] p , q lビットの異なる Sophie-Germain 素数 p = 2p + 1, q = 2q + 1, n = pq, n = p q x1, x2, x3 ← [n2/4], g ← Zn2* g = (g )2n, y1 = gx1, y2 = gx2, y3 = gx3 pk = (H, n, g, y1, y2, y3), sk = (H, n, x1, x2, x3). Enc(pk, m, L) // m ∈ [n], Lはラベル r ← [n/4] u = gr, e = y1r hm, v = abs( (y2y3H(u,e,L))r ) return (u, e, v). Dec(sk, (u,e,v), L) abs(v) =? v u2(x2 + H(u,e,L)x3) =? v2 t = 2-1 mod n m = (e / ux1)2t m が hm (∃m ∈ [n]) の形ならば、m を出力。 そうでないならば、reject. 定理(Camenish-Shoup暗号) ハッシュ関数Hが衝突困難で、DCR仮定が成り立つならば、 Camenish-Shoup暗号は適応的選択暗号文攻撃に対し識別不可能である。 タグベース暗号 タグベース暗号とは、 効率的な確率的アルゴリズムの3つ組(Gentbe, Enctbe, Dectbe)である： (pk, sk) ← Gentbe(1n) c ← Enctbe(pk, t, m) m ← Dectbe(sk, t, c). 完全性(completeness)条件として、 全てのメッセージm(∈M)とすべてのタグt(∈T)について Pr[ (pk, sk) ← Gentbe(1n), c ← Enctbe(pk, t, m), m ← Dectbe(sk, t, c) m = m ] = 1 を要求する。 タグ選択暗号文攻撃に対する識別不可能性 タグベース暗号TBE=(Gentbe,Enctbe,Dectbe)とそれに対する攻撃者Aについて： 試行 StagCCATBE,A(n) (t*, st0) ← A(1n) (pk, sk) ← Gentbe(1n) (M0, M1, st) ← ADectbe(・,・)(pk, st0) b ← {0,1}, c* ← Enctbe(pk, t*, Mb) b ← ADectbe(・,・)(c*, st) return b =? b . ただし、Aは復号オラクルDectbe(・,・)にタグt*について問い合わせることは許されない。 定義(IND-STAG-CCA) タグベース暗号TBEがタグ選択暗号文攻撃に対し識別不可能(IND-STAG-CCA)であるとは、 任意の効率的な攻撃者Aについて、その識別利得 ｜ Pr[ StagCCATBE,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 タグベース暗号から公開鍵暗号への変換 構成(TBE2PKE) TBE = (Gentbe, Enctbe, Dectbe) タグ空間Tのタグベース暗号 OTS = (SKG, SIGN, VFY) ワンタイム署名 (s.t. vk ∈ T) PKE = (Genpke, Encpke, Decpke) 公開鍵暗号 Genpke = Gentbe. Encpke(pk, m) (vk, sigk) ← SKG(1n) ctbe ← Enctbe(pk, vk, m) σ ← SIGN(sigk, ctbe) return c = (ctbe, vk, σ). Decpke(sk, c) (ctbe, vk, σ) = c VFY(vk, ctbe, σ) =? reject return ⊥ else return m = Dectbe(sk, vk, ctbe). 定理(TBE2PKE) [Kiltz 06] TBEがタグ選択暗号文攻撃に対し識別不可能なタグベース暗号で、 OTSがストロングワンタイム署名ならば、 PKE = TBE2PKE(TBE, OTS) は適応的選択暗号文攻撃に対し識別不可能である。 証明 タグ選択暗号文攻撃に対し識別不可能なタグベース暗号の構成 判定線形仮定 群G= g について、 線形タプル (g1, g2, z, g1r1, g2r2, zr1+r2). 定義(判定線形仮定) 群Gについて、与えられた6要素からなるタプル (g1, g2, z, g1r1, g2r2, w) が線形タプルかランダムタプルかを判定する問題を判定線形問題という： w =? zr1+r2. 判定線形問題が困難であるとの仮定を判定線形仮定という。 命題(DLinear) 判定線形仮定は判定DH仮定よりも弱い仮定である（より妥当な仮定である）。 すなわち、判定線形問題が解けるときは判定DH問題も解ける。 証明 命題(DLinear)は、判定DH問題が解けても判定線形問題は解けない、という可能性は除外しない。 実際、双線形群にはそのような可能性を期待できる。 ある群Gについて、判定DH問題は易しいのに判定線形問題はむずかしいとき、 群Gは判定線形ギャップ仮定をみたすという。 注意 (g, gx1, gx2, gy, gx1y, gx2y)：双子DHタプル ⇒ (gy-1, gy-1, g, gx1, gx2, gx1y+x2y) 線形タプル 判定線形仮定にもとづくタグ選択暗号文攻撃に対し識別不可能なタグベース暗号 構成(LinearTBE) [Kiltz 06] Gentbe(1n) G 位数q の群 g1 ← G, (x1,x2,y1,y2) ← Zq g2, z を g1x1 = g2x2 = z となるようにとる。 u1 = g1y1, u2 = g2y2 pk = (q, g1, g2, z, u1, u2), sk = (x1, x2, y1, y2). ※ (g1, g2, z, -, -, -)は判定線形問題の問題文の一部。 ※ 秘密鍵skを知っていれば、この問題文（の一部）に関する判定線形問題は容易： ※ (g1, g2, z, c1, c2, w)は線形タプル ⇔ c1x1 c2x2 = w. Enctbe(pk, t, m) r1,r2 ← Zq*, c1 = g1r1, c2 = g2r2 d1 = ztr1 u1r1, d2 = ztr2 u2r2, e = m zr1+r2 return ctbe = (c1, c2, d1, d2, e). ※ (g1, g2, z, c1, c2, zr1+r2)は線形タプル。 ※ 実際、c1x1 c2x2 = zr1+r2. ※ d1, d2はc1, c2の正当性を示す： ※ c1tx1+y1 = d1, c2tx2+y2 = d2. Dectbe(pk, t, ctbe) s1,s2 ← Zq* k = (c1x1+s1(tx1+y1) c2x2+s2(tx2+y2)) / (d1s1d2s2) ※ 正当な暗号文、すなわち citxi+yi = di (i=1,2) のときだけ、まともに復号される。 ※ k = c1x1 c2x2 = zr1+r2. return m = e / k. (パブリック検証) Pvtbe(pk, t, ctbe) 暗号文の正当性は公開情報だけで確認できる return DH(g1, zt u1, c1, d1) ∧ DH(g2, zt u2, c2, d2). ※ ⇔ di = citxi+yi (for i=1,2). 定理(LinearTBE) [Kiltz 06] 群Gに対する判定線形ギャップ仮定のもとで、 構成(LinearTBE)はタグ選択暗号文攻撃に対し識別不可能なタグベース暗号である。 証明 上へ
https://w.atwiki.jp/cryptospace/pages/19.html
はじめに 準備 一方向関数とランダムオブジェクト 公開鍵暗号 IDベース暗号 属性ベース暗号 検索可能暗号 デジタル署名 認証プロトコル ストレージ証明 鍵共有プロトコル コミットメント 汎用的結合可能性 Obfuscators 暗号的クラウドストレージ 文献 演習問題 by 有田 正剛
https://w.atwiki.jp/cryptospace/pages/156.html
セキュア・インデックスセキュア・インデックスの機能インデックス・スキーム 完全性 (completness) セキュア・インデックスの安全性ゲーム 定義 (IND-CKA) セキュア・インデックスの構成ブルーム・フィルター インデックス・スキーム Z-IDX部品 Keygen (s) Trapdoor (Kpriv, w) BuildIndex (D=(idD, (w1, ... , wt))) SearchIndex ( Tw=(x1, ... , xr), I = (idD, BF) ) スキームの観察 定理 (セキュアインデックス)証明について 検索可能公開鍵暗号検索可能公開鍵暗号スキーム完全性 (completness) 検索可能公開鍵暗号の安全性ゲーム 定義 (IND-CKA) 検索可能公開鍵暗号の構成双線形写像を用いた構成部品 KeyGen PEKS (Apub, W) Trapdoor(Apriv = α, W) Test(Apub, S=(A,B), TW) スキームの観察 定理 (PEKS) 双線形ディフィー・ヘルマン仮定 証明について 文献 セキュア・インデックス セキュア・インデックスの機能 セキュア・インデックスとは、文書Dに対して、検索キーwを隠したままでそれが文書Dに含まれるか否かを知ることができるインデックスIDを生成するスキーム。インデックスIDから文書Dの内容が知られてはならない。 インデックス・スキーム I = (Keygen, Trapdoor, BuildIndex, SearchIndex)： Kpriv ← Keygen() Tw ← Trapdoor(Kpriv, w) ID ← BuildIndex(D, Kpriv) 1/0 ← SearchIndex(Tw, ID) 文書Dと鍵Kprivは私的に保持し、そのインデックスIDは第三者に預けておく。 ユーザはワードwについて検索したいときには、そのトラップドアTwを計算し、第三者に渡して検索結果SearchIndex(Tw, ID)を受け取る。 完全性 (completness) ∀Kpriv ← Keygen(s), ∀w ワード, ∀D 文書, ∀Tw ← Trapdoor(Kpriv, w), ∀ID ← BuildIndex(D, Kpriv) SearchIndex(Tw, ID) = ( w∈? D ). セキュア・インデックスの安全性 どのような攻撃者も、いくつかのワードのトラップドアを入手したとしても、インデックスIDから文書Dの内容が全く分からないこと。 ゲーム q個のワードからなる集合Sを選択する。 攻撃者Aを起動し、集合Sを渡す。 攻撃者Aより、Sの部分集合の族S*を受け取り、 Kpriv ← Keygen() V ∈ S* IV ← BuildIndex(V, Kpriv) { (V, IV) }V∈S* をAに渡す。 以下をAが望むだけ複数回繰り返す： ※ トラップドアクエリ 攻撃者Aがワードxについてトラップドアを要求したら、 Tx ← Trapdoor(Kpriv, x) を計算し、返す。 攻撃者Aより２つの文書V0, V1 を受け取り、 ※ チャレンジクエリ V0∈S*、V1∈S*、V0 not⊆ V1、V1 not⊆ V0 を確認する。 AはまだV0とV1の対称差に含まれるワードのトラップドアを要求していないことを確認する。 b ← {0,1}、 IVb ← BuildIndex(Vb, Kpriv) IVbを返す。 以下をAが望むだけ複数回繰り返す： ※ トラップドアクエリ 攻撃者Aがワードxについてトラップドアを要求したら、 x が V0とV1の対称差に含まれないことを確認する。 Tx ← Trapdoor(Kpriv, x) を計算し、返す。 Aはb を出力して停止する。 攻撃者Aのアドバンテージ： AdvA =def | Pr[b=b ] - 1/2 | ※ トラップドアTxがワードxを隠すかどうかは考慮されていない。 定義 (IND-CKA) インデックス・スキーム I = (Keygen, Trapdoor, BuildIndex, SearchIndex)が適応的選択キーワード攻撃に対し識別不可能（IND-CKA）であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdvAが無視可能であることを云う。 セキュア・インデックスの構成 ブルーム・フィルター 機能： 与えれたaが、集合S= {s1, ・・・, sn}に属するか否かを、o(n)の計算量で、判定する。 準備： パラメータ m, r mビットのアレイ α r個の独立なハッシュ関数 h1, ・・・, hr hi {0,1}* → [1..m] (i = 1,...,r) 動作： すべてのアレイビットを0に初期化： h ∈ [1..m] α[h] = 0. s ∈ S α[h1(s)] = ・・・ = α[hr(s)] = 1 a ∈ S かどうかを判定するのに αをビット位置 h1(a), ・・・ , hr(a)でチェック それらがすべて１ならば、a ∈ Sと判定する。 ※ フォース・ポジティブの確率あり。 インデックス・スキーム Z-IDX 部品 擬似ランダム関数 f {0,1}s x {0,1}n → {0,1}s Keygen (s) return Kpriv = (k1, ... , kr) ← {0,1}sr Trapdoor (Kpriv, w) return Tw = (f(k1, w), ... , f(kr, w))). BuildIndex (D=(idD, (w1, ... , wt))) // 簡単のため、対象文書Dのワード数tは一定であるとする。 ブルーム・フィルターBFを用意 i∈[1..t] x1 = f(k1, wi), ... , xr = f(kr, wi) y1 = f(x1, idD), ... , yr = f(xr, idD) ブルーム・フィルターBFのアレイのビット位置y1, ... , yrを1にセット。 return (idD, BF) SearchIndex ( Tw=(x1, ... , xr), I = (idD, BF) ) y1 = f(x1, idD), ... , yr = f(xr, idD) BFがビット位置y1, ... , yrですべて１であるか否かをチェック。 そうならば1を、そうでないならば0を出力。 スキームの観察 ブルーム・フィルターで用いるハッシュ関数を鍵付きのハッシュ関数とし、その鍵をマスターシークレットとした。 鍵付きのハッシュ関数を擬似ランダム関数で実現すれば、インデックスはランダム値となるので、文書の内容を隠す。 ただし、トラップドアを実現するために、擬似ランダム関数の使い方に無理が生じている。 後半の使い方（yi = f(xi, idD)）に注意を要する。論文の証明は不十分と思われる。 シードが既知の乱数のときの、擬似ランダム関数の値の分布が問題となりそう。 統計的な安全性の議論が必要となるのでは？ 定理 (セキュアインデックス) 関数fが擬似ランダム関数ならば、インデックス・スキーム Z-IDXは、選択キーワード攻撃に対し識別不可能である。 証明について 上に見たように、論文の証明にはギャップがある。関数fについてもっと強い仮定が必要だろうと思われる。 検索可能公開鍵暗号 ワードWのトラップドアがあれば、暗号文SがワードWを暗号化したものか否かがわかる公開鍵暗号。 検索可能公開鍵暗号スキーム PEKS = (KeyGen, PEKS, Trapdoor, Test)： (Apub, Apriv) ← KeyGen(s) S ← PEKS(Apub, W) TW ← Trapdoor(Apriv, W) 1/0 ← Test(Apub, S, TW) 完全性 (completness) (Apub, Apriv) ← KeyGen(s), ∀W, S ← PEKS(Apub, W), TW ← Trapdoor(Kpriv, W) Test(Apub, S, TW) = ( SはWの暗号文? ). 検索可能公開鍵暗号の安全性 どのような攻撃者も、いくつかのワードのトラップドアを適応的に入手したとしても、そのほかのワードの暗号文については、どんなワードの暗号化か全く分からないこと。 ゲーム (Apub, Apriv) ← KeyGen(s) Apubを入力として攻撃者Aを起動する。 Aが望むだけ以下を複数回繰り返す： ※ トラップドアクエリ 攻撃者AがワードWについてトラップドアを要求したら、 TW ← Trapdoor(Apriv, W) を計算して返す。 攻撃者Aより２つのワードW0, W1 を受け取り、 ※ チャレンジクエリ b ← {0,1}、 S ← PEKS(Apub, Wb) Sを返す。 Aが望むだけ以下を複数回繰り返す： ※ トラップドアクエリ 攻撃者AがワードWについてトラップドアを要求したら、 W が W0やW1とは異なることを確認する。 TW ← Trapdoor(Apriv, W) を計算して返す。 Aはb を出力して停止する。 攻撃者Aのアドバンテージ： AdvA(s) =def | Pr[b=b ] - 1/2 | 定義 (IND-CKA) 検索可能公開鍵暗号 PEKS = (KeyGen, PEKS, Trapdoor, Test)が適応的選択キーワード攻撃に対し識別不可能（IND-CKA）であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdvA(s)が無視可能であることを云う。 検索可能公開鍵暗号の構成 双線形写像を用いた構成 PEKS = (KeyGen, PEKS, Trapdoor, Test) 部品 双線形写像 e G1 x G1 → G2, #G1 = #G2 = 素数p ハッシュ関数 H1 {0,1}* → G1 ハッシュ関数 H2 G2 → {0,1}log p KeyGen α ← Zp*, g ← G1の生成元 return Apub = (g, h = gα), Apriv = α. PEKS (Apub, W) r ← Zp* return (gr, H2( e(H1(W), hr) )). Trapdoor(Apriv = α, W) return TW = H1(W)α. Test(Apub, S=(A,B), TW) return H2(e(TW, A)) =? B. スキームの観察 Wの暗号文は、(gr, H2(e(H1(W), gαr))) よって、H1(W) = gβ とするとき、e(g, g)αβrが問題。 一方、トラップドアオラクルは、H1(W) = gβとするとき、gαβを返す。 定理 (PEKS) 双線形ディフィー・ヘルマン仮定が成り立つならば、ランダムオラクルモデルのもとで、PEKSは適応的選択キーワード攻撃に対し識別不可能（IND-CKA）である。 双線形ディフィー・ヘルマン仮定 g, ga, gb, gcを与えらて、e(g,g)a,b,cを計算することは困難。 証明について 上でみたようにH1オラクルのシミュレーションがポイント。 適切な確率で、 問題文gbを返答に埋め込む → チャレンジクエリへの応答 自ら生成した乱数aを用いて、gaを返答する。 → トラップドアクエリへの応答 文献 [Goh 03] [BCOP 04] [ABCKKLMNPS 05] [CGKO 06] 上へ
https://w.atwiki.jp/wiki3_angou/pages/4.html
～簡単なまとめ～ 暗号(１氏)がクラスの女子から冷たくされてる気がし、ある女子(おでん)にメール 内容は「俺嫌われてる？」とかそんな感じのこと おでんからの返信「私は いろべよう(Ｉ ＬＯＶＥ ＹＯＵ)」 気が動転しつつも暗号はおでんに告白。しかしおでんには彼氏(バレー)がいる。しかも暗号の友達であり、キューピットは暗号 暗号はバレーに話をつけようと、外で会うことにした。 そしてボコボコにされた その後おでんから散々言われて別れる。バレーと仲直りしようとまた外で会うが、おでんが嘘をつき、暗号またボコボコ しかし、おでんの嘘に気づきつつあるバレーがおでんを家から追い出す。さぁこの３角関係はいったどうなるんだ～？
https://w.atwiki.jp/cryptospace/pages/157.html
属性ベース暗号（鍵ポリシー型）の機能属性ベース暗号（鍵ポリシー型）スキーム 完全性 (completness) 属性ベース暗号（鍵ポリシー型）の安全性ゲーム 定義 属性ベース暗号の構成1アクセス構造 部品 構成Setup (n) Enc (m, γ, PK) KeyGen (T, MK, PK) Dec (E, D) スキームの観察 定理 (ABE) 構成2Setup () Encrypt (PK, (M,ρ), PT) ※ M l x n KeyGen (MSK, S) Decrypt(CT, SK) 定理 (Large Universe Construction) Bethencourt-Sahai-Waters 文献 属性ベース暗号（鍵ポリシー型）の機能 暗号文は、いくつかの属性の集合γでラベル付けされる。 復号鍵は、アクセス構造Aを表現する。 暗号文の属性集合γが復号鍵のアクセス構造Aを満たす γ∈A ときのみ、復号できる。- ただし、対象とできるアクセス構造は単調なもの。 属性ベース暗号（鍵ポリシー型）スキーム ABE = (Setup, Enc, KeyGen, Dec)： (PK, MK) ← Setup E ← Enc(PK, m, γ) D ← KeyGen(PK, A, MK) m/⊥ ← Dec(PK, D, E) 完全性 (completness) ∀(PK, MK) ← Setup ∀A アクセス構造 ∀D ← KeyGen(PK, A, MK) ∀γ：属性集合、∀m, ∀E ← Enc(PK, m, γ) について γ∈A ならば Dec(PK, D, E) = m. 属性ベース暗号（鍵ポリシー型）の安全性 ポイントは結託耐性。様々なアクセス構造Ajに対応する秘密鍵Djをかき集めてきても、γ not∈ ∪j Ajであるならば、そのようなγを属性集合とする暗号文の復号には、秘密鍵の集まり∪jDjはまったく役立たないこと。 ゲーム 攻撃者Aを起動し、ターゲットとなる属性集合γを得る。 (PK, MK) ← Setupを実行し、PKをAに渡す。 Aが望むだけ以下を複数回繰り返す： ※ 秘密鍵クエリ 攻撃者Aがアクセス構造Ajに対応する秘密鍵を要求したら、 γがAjを満たさないことを確認する。 Dj ← KeyGen(PK, Aj, MK)を実行し、DjをAに渡す。 攻撃者Aより２つの平文M0, M1 を受け取り、 ※ チャレンジクエリ b ← {0,1}、 E ← Enc(PK, Mb, γ) Eを返す。 Aが望むだけ以下を複数回繰り返す： ※ 秘密鍵クエリ 攻撃者Aがアクセス構造Ajに対応する秘密鍵を要求したら、 γがAjを満たさないことを確認する。 Dj ← KeyGen(PK, Aj, MK)を実行し、DjをAに渡す。 Aはb を出力して停止する。 攻撃者Aのアドバンテージ： AdvA(s) =def | Pr[b=b ] - 1/2 | 定義 属性ベース暗号 ABE = (Setup, Enc, KeyGen, Dec) が選択的属性集合攻撃に対し識別不可能であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdvA(s)が無視可能であることを云う。 属性ベース暗号の構成1 アクセス構造 アクセス構造は木 T で表現： 各内部ノードxは閾値ゲート numx ノードxの子ノードの数。 kx ノードxの閾値。（0 ＜ kx ≦ numx） γ∈Tの判定： すべての葉ノードを偽に初期化。 属性集合γに含まれる各属性について、対応する葉ノードを真にセット。 上位ノードに値を再帰的に伝播。 ルートノードの真偽を出力。 記号 parent(x) xの親ノード att(x) 葉ノードxについてのみ定義。属性を表す。 index(x) xの子ノードとしてのインデックス。 部品 双線形写像 e G1 x G1 → G2, #G1 = #G2 = 素数p ラグランジュ係数 {Δi,S(x)}i∈S S ⊆ Zp i ∈ S, Δi,S(x) =def Πj∈S,j≠i (x - j) / (i - j). 次数が#S-1以下の任意の多項式q(x)について、Σi∈S q(i)Δi,S(x) = q(x) となる。 構成 Setup (n) y ← Zp, g1 = gy, g2 ← G1 t1, ・・・, tn+1 ← G1 N = {1, 2, ・・・, n+1} return PK = (g1,g2,t1,・・・,tn+1), MK = y. ※ T(X) =def g2Xn Πi=1,...,n+1tiΔi,N(X) ( = g2Xn gh(X) with deg h = n+1 ) ※ T(i) = g2in ti for i ∈ N Enc (m, γ, PK) s ← Zp return E = (γ, E = m・e(g1,g2)s, E = gs, {Ei = T(i)s }i∈γ ). KeyGen (T, MK, PK) ※ Tの各ノードxに次数dxの多項式qxを配置 Tの各ノード x ： dx = kx - 1 ルートノード r ： ※ 主秘密をルートノードにセット qr(0) = y, 他の任意のdr個の点における値をランダムに選択。 その他のノード x ： ※ 親ノードparent(x)の秘密情報を子ノードxに分散 qx(0) = qparent(x)(index(x)), 他の任意のdx個の点における値をランダムに選択。 ※ Then 各葉ノード x ： ※ 各葉ノードの秘密情報qx(0)を暗号化。これにより、ルートの秘密情報である主秘密を復元できないようにする。 rx ← Zp, Dx = g2qx(0)T(i)rx, Rx = grx return D = { (Dx, Rx) }x 葉ノード. Dec (E, D) return E / DecNode(E, D, r). ※ rはルートノード DecNode (E=(γ,E ,E ,{Ei}), D= {(Dx,Rx)}, x) x 葉ノード ： i = att(x) ∈? γ： return e(Dx, E ) / e(Rx, Ei) else return ⊥ else // x 内部ノード z ：xの子ノード： Fz = DecNode(E,D,z) Sx ← Fz≠⊥である子ノードzからなる、任意の要素数kxの集合 return Πz∈SxFzΔi=index(z),index(Sx)(0) スキームの観察 暗号文 E = (γ, E = m・e(g1,g2)s, E = gs, {Ei = T(i)s }i∈γ ) において、mを直接隠しているのは、G2要素である e(g1, g2)s これは、 e(E , g2)y に等しい。 MK = y は秘密鍵Dの構成において、ルートノードにセットされ、それが再帰的に子ノードに秘密分散されて秘密鍵Dの値となった。 分散先である各葉ノードでT(i)sなどを用いて、 e(E , g2)qx(0) を得る。これらは再帰的にe(E , g2)yを構成する。 定理 (ABE) 判定双線形ディフィー・ヘルマン仮定が成り立つならば、ABEは選択的属性集合攻撃に対し識別不可能である。 構成2 Large Universe Construction [Waters 11] Setup () Choose a group G of prime order p with generator g α, a ← Zp Choose a hash function H {0,1}* → G PK = (g, e(g,g)α, ga), MSK = gα. Encrypt (PK, (M,ρ), PT) ※ M l x n s, y2,・・・, yn ← Zp i ∈ [1..l] λi = (s, y2,・・・, yn)・Mi r1,・・・, rl ← Zp CT = (C = PT・e(g,g)αs, C = gs, (Ci = gaλi H(ρ(i))-ri, Di = gri)i=1,...,l). KeyGen (MSK, S) t ← Zp SK = (K = gαgat, L = gt, (Kx = H(x)t)x∈S). Decrypt(CT, SK) I = {i ρ(i)∈S} {ωi}i∈I the set of constants for I ※ Σi∈I ωi Mi = (1,0,・・・, 0) return C・e(C , K)-1・Πi∈I { e(Ci, L)・e(Di, Kρ(i)) }ωi. 定理 (Large Universe Construction) 判定q-平行BDHE仮定が成り立つならば、Large Universe Constructionは選択的攻撃に対し識別不可能である。 Bethencourt-Sahai-Waters PK = (g, h = gβ, f = g1/β, e(g,g)α) MK = (β, gα) 暗号文 (M・e(g,g)αs, hs, (gsy, H(att(y))sy)y∈Y) 属性集合鍵 (g(α+r)/β, (grH(j)rj, grj)j∈S) 文献 [GPSW 06] [Waters 11] 上へ
https://w.atwiki.jp/cryptospace/pages/161.html
情セ大有田研究室のセミナーページです。 共有しておきたい情報、アイデア、予定など自由に書き込んでください。 （メンバー登録は上部メニュー [このウィキに参加] からお願いします。） イベント イベント情報 サイト サイト情報 コード Boneh Franklin encryption scheme トピック Flexible Attribute-Based Encryption 分離認証問題 属性ベース認証 属性ベース認証２ Resettable Argument Resettable Argument ２ 対話認証スキームIDKEA0 A Group-Key Agreement Protocol nonmalleableな鍵共有プロトコル KEAクリアコンパイラ Quasi-commitment Functionality Implicit Corrupt Another Composability 楕円曲線暗号 ゲーム理論と暗号理論 輪講発表資料 修士論文 2013年度前期 M2輪講資料 上へ
https://w.atwiki.jp/cryptospace/pages/159.html
IDベース暗号完全性 (completness) IND-ID-CPAゲーム BDH問題 CocksスキームSetup (1k) Extract (ID, master_key, params) Enc (params, ID, x) ※ x = -1 or 1 Dec (params, c = (c0, c1), skID = r) Boneh-FranklinスキームSetup (1k) Extract (ID, master_key = s, params) Enc (params, ID, M) Dec (params, C = (U,V), dID) Completeness 観察 定理 WatersスキームSetup (1k) KeyDer (msk, ID) // ID ∈ 0,1n Enc (pk, ID, M) IDベース暗号 IBE = (Setup, Extract, Enc, Dec) (params, master_key) ← Setup dID ← Extract(params, master_key, ID) C ← Enc(params, ID, M) M ← Dec(params, C, dID) 完全性 (completness) ∀(params, master_key) ← Setup ∀ID, ∀m Dec(params, Enc(params, ID, M), Extract(params, master_key, ID)) = m. IND-ID-CPA ゲーム params を入力として攻撃者Aを起動する。 Aが望むだけ以下を複数回繰り返す： ※ 秘密鍵クエリ 攻撃者AがIDiの秘密鍵を要求したら、 di ← Extract(params, master_key, IDi)をAに渡す。 攻撃者Aより２つの平文M0, M1とID を受け取り、 ※ チャレンジクエリ b ← {0,1}、 E ← Enc(params, ID, Mb) Eを返す。 Aが望むだけ以下を複数回繰り返す： ※ 秘密鍵クエリ 攻撃者AがIDiの秘密鍵を要求したら、 ID≠IDiを確認。 di ← Extract(params, master_key, IDi)をAに渡す。 Aはb を出力して停止する。 攻撃者Aのアドバンテージ： AdvA(s) =def | Pr[b=b ] - 1/2 | 注意： IDをひとつに固定してしまえば、公開鍵暗号IBEIDとなる。 IBEIDがIND-CPAであること。 問題は、各IBEIDが干渉し合わないこと。 →結託耐性。 可能なIDの個数に上限がない場合が本質的。 BDH問題 Given (q, G1, G2, e, P, aP, bP, cP), Find e(P,P)abc. BDH問題 ≦ CDH問題 Cocksスキーム Setup (1k) (N, p, q) ← GenBlumMod(1k) Choose H {0,1}* → JN* params = N, masterk_key = (p, q). Extract (ID, master_key, params) a0 = H(ID), a1 = - H(ID) return skID = a0 または a1 の平方根. Enc (params, ID, x) ※ x = -1 or 1 t0 ← ZN* s.t. (t0/N) = x a0 = H(ID) c0 = t0 + a0 / t0 t1 ← ZN* s.t. (t1/N) = x a1 = - H(ID) c1 = t1 + a1 / t1 return c = (c0, c1). Dec (params, c = (c0, c1), skID = r) a = H(ID) r2 =? a y = c0 + 2 r else y = c1 - 2 r return x = (y / N). Boneh-Franklinスキーム Setup (1k) (q, e, G1, G2) ← Grp(1k), P ← G1 s ← Zq, Ppub = sP Choose H {0,1}* → G1* params = (P, Ppub), masterk_key = s. Extract (ID, master_key = s, params) ※ DH組のパラレルワールド QID = H(ID) return dID = s QID. Enc (params, ID, M) QID = H(ID) ※ G2へワープ gID = e(QID, Ppub) r ← Zq return C = (rP, M gIDr). Dec (params, C = (U,V), dID) return M = V e(dID, U)-1. Completeness gIDr = e(QID, Ppub)r = e(QID, P)s r = e(dID, U) 観察 IDを固定した公開鍵暗号BFIDは、DBDH仮定のもとでIND-CPA。 問題は、同じsをベースにしている、IDを変数とするパラレルワールドにおいて、BFID達が干渉をおこさず、独立であること。 → 結託耐性。 定理 DBDH仮定がなりたつならば、Hについてのランダムオラクルモデルのもとで、Boneh-FranklinスキームはIND-ID-CPA。 Watersスキーム 文献 [Waters 05] H(u, I) = u0 Πi=1..n uiIi Setup (1k) mpk = (g2, A1, B2, u = (u1,...,un)) msk = A1b KeyDer (msk, ID) // ID ∈ {0,1}n skI = (msk・H(u,I)r, g2r) Enc (pk, ID, M) (M・e(A1, B2)s, g2s, H(u,I)s). 上へ
https://w.atwiki.jp/cryptospace/pages/158.html
パブリック・クラウドストレージ 仮想プライベート・クラウドストレージ 仮想プライベート・クラウドストレージのアーキテクチャ コア・コンポーネントの実現ＤＰ ＴＧ ＣＧ ＤＶ 文献 パブリック・クラウドストレージ Microsoft Azure Amazon S3 オフプレミスに位置 スケーラブル、ダイナミック、低コスト データ共有、データ連携 データはカスタマーのコントロールの範囲外 必ずしも信頼できないパーティが管理 秘匿性と一貫性の課題 → 機密データはプライベート・クラウドストレージ（、ハイブリッド・クラウドストレージ）？ 仮想プライベート・クラウドストレージ 暗号技術を活用することによって、 パブリック・クラウドストレージを仮想的なプライベート・クラウドストレージとして用いる ことを可能にしよう。（VPNのクラウドストレージ版） プライベート・クラウドストレージの安全性（秘匿性と一貫性） パブリック・クラウドストレージの機動性と低コスト性 仮想プライベート・クラウドストレージのアーキテクチャ 仮想プライベート・クラウドストレージのコア・コンポーネント： データ・プロセッサ（ＤＰ） クラウドストレージに送られる前にデータを処理する。暗号化など。 データ・ベリファイア（ＤＶ） クラウドストレージ内のデータが壊されていないかチェックする。 クレデンシャル・ジェネレータ（ＣＧ） データ共有/連携を可能とするクレデンシャルを生成。 トークン・ジェネレータ（ＴＧ） クラウドストレージ・プロバイダが暗号化データの検索をできるようにするためのトークンを生成。 imageプラグインエラー ご指定のファイルが見つかりません。ファイル名を確認して、再度指定してください。 (virtualCS.jpg) MegaCorpやPartnerCorpの従業員はＣＧより各自のクレデンシャルを入手。 MegaCorp従業員はデータをアクセスポリシーとともにＤＰに送る。 ＤＰは暗号化など必要な処理を施したのち、データをクラウドプロバイダに送る。 PartnerCorp従業員はキーワードをＴＧに送る。 ＴＧは（暗号化されたデータを検索するための）チケットを送り返す。 PartnerCorp従業員はチケットをクラウドプロバイダに送る。 クラウドプロバイダは（暗号化されたままの）検索結果をPartnerCorp従業員に返す。PartnerCorp従業員は自身のクレデンシャルを用いて復号し、検索結果を得る。 任意のタイミングで、MegaCorpのＤＶはクラウドストレージ内のデータの一貫性を確認する。 ※ これらのコンポーネントをクラウド内に配置したら意味がない！ コア・コンポーネントの実現 ＤＰ データをインデックス付けし、インデックスを検索可能暗号で暗号化。 データ本体をユニーク鍵で対称鍵暗号を用いて暗号化。 ユニーク鍵を属性ベース暗号で適切なポリシーのもとで暗号化。 ＴＧ 検索可能暗号のトラップドア生成アルゴリズムで実現。 ＣＧ 属性ベース暗号のユーザ秘密鍵生成アルゴリズムで実現。 ＤＶ ストレージ証明を用いて実現。 文献 [KL 10] 上へ
https://w.atwiki.jp/2062/pages/13.html
解読手法の引き出しとして参考にしてみてください。 各手法の詳細は自分で調べよう！ 単体で解決出来そうにないので、複合かも？ エニグマ前回の暗号がエニグマ（M-3)暗号で解読できたため。エニグマは使わないとのこと。 オレンジ暗号エニグマの親戚（M-1）。参考文献がほとんどないため歯車の順番などがわからず再現が難しい。 植木算13+4+7+5＝25 は、植木算であれば成立する。（12+3+6+4が植木算での） RSA現代で一般的に使われる手法。ちはや（ASR)や最高難度としてはアリ？公開鍵は何千bitとか厳重なものではないだろう。数字をかき混ぜることはできるが、結局数字を文字に興す変換が必要で、△や‐の扱いもあり直接は使えない 佐久暗号ゴルゴ１３で登場したらしい。別名「最終暗号」考え方としてはRSA同様に素数が関係するっぽい DES暗号RSAが一般化する前の20世紀末まで使われていた手法。ヒントのボーンに対してのデスというとらえ方もある パープル暗号2016/8/3現在最も有力 ger（ドイツ）の-8（時差）より
https://w.atwiki.jp/cryptospace/pages/21.html
定理(CPA暗号)の証明のアイデア 構成(CPA暗号)の暗号文は、 c = (m + (hci(fil-1(r)), hci(fil-2(r)), ..., hc(r)), fil(r)). (hci(fil-1(r)), hci(fil-2(r)), ..., hc(r),fil(r))は、 真の乱数(p, s) と区別がつかない。（p,sはそれぞれlビット、nビット） よって、cは c = (m + p, s) と区別がつかない。 c は完全にmを隠しているので、cも（効率的な攻撃者に対しは）mを隠す。 定理(CPA暗号)の証明 構成(CPA暗号)をΠとし、Πに対する任意の効率的な攻撃者をAとする。 Aの成功確率 ｜ Pr[CPAΠ,A(n) = 1] - 1/2 ｜ がネグリジブルであることを示したい。 まず、Game G0を定義する。Game G0は、試行 CPAΠ,A(n)をΠ=構成(CPA暗号)として具体化したものである： Game G0 (pk, sk) = (i, ti) ← G(1n) pk=iを入力としてAを起動する。 Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： r ← {0,1}n fi(r), fi2(r), ..., fil(r) を計算。 p = ( hci(fil-1(r)), hci(fil-2(r)), ..., hc(r) ) c* = (mb + p, fil(r)) c*をチャレンジクエリに対する応答として返す。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 Game G1では、Game G0で疑似乱数であるpを真の乱数に変更する： Game G1 (pk, sk) = (i, ti) ← G(1n) pk=iを入力としてAを起動する。 Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： r ← {0,1}n p ← {0,1}l c* = (mb + p, r) c*をチャレンジクエリに対する応答として返す。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 主張1 Pr[ G1 = 1] = 1/2. 証明 pが真にランダムなので、c* = (mb + p, r) は、b=0のときも b=1のときも、(l+n)ビットの乱数である。 よって、Aのview（Aが入手するすべての情報）はbと統計的に独立である。 よって、Aの出力もbと統計的に独立なので、b = b となる確率は1/2である。Q.E.D. 主張2 Pr[G1 = 1] - Pr[G0= 1] はネグリジブルである。 証明 攻撃者Aを用いて、構成(PSG3)の疑似乱数生成器Gに対する識別者Dを構成する： 識別者D 長さ(n+l)ビットの文字列(w, p)を入力として、インデックスiを補助入力として、 pk=iを入力としてAを起動する。 Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： c* = (mb + p, w) c*をチャレンジクエリに対する応答として返す。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 [識別者Dの解析] 入力(w,p)が疑似乱数(fil(r), hci(fil-1(r)), hci(fil-2(r)), ..., hc(r))のとき、 （識別者D内のAが受け取るc*） ≡ （G0におけるc*） 入力(w,p)が真のn+lビット乱数のとき、 （識別者D内のAが受け取るc*） ≡ （G1におけるc*） よって、識別者Dの識別利得は ｜ Pr[G1(1n) = 1] - Pr[G0(1n) = 1] ｜ に等しく、Gは疑似乱数生成器なので、これはネグリジブルである。Q.E.D. 主張1より、 ｜ Pr[CPAΠ,A(n) = 1] - 1/2 ｜ = ｜Pr[G0 = 1] - Pr[G1 = 1] ｜ であり、主張2よりこれはネグリジブルである。 Q.E.D. 上へ