08 年 度 特 別 講 義 X 暗 号 技 術 の 発 展 古 典 暗 号 からIDベース 暗 号 まで 08.09.01 有 田 正 剛 1
k 1,k 2 : 鍵 E : 暗 号 化 アルゴリズム D : 復 号 アルゴリズム 暗 号 k 1 m k 2 送 信 者 c 受 信 者 c E k1 (m) m D k2 (c) m Eve? 2
目 次 1. 古 典 暗 号 2. ブロック 暗 号 3. 公 開 鍵 暗 号 4. IDベース 暗 号 3
1. 古 典 暗 号 コンピュータのない 時 代 の 暗 号 4
換 字 暗 号 方 式 鍵 π : アルファベット{A, B, C,, Z}の 並 べ 替 え 例 えば π(a) = V, π(b) = S, π(c) = G,,, π(z)=u U 暗 号 化 // x {A, B, C,, Z} E π (x) = π(x) 復 号 // y {A, B, C,, Z} D π (y) = π 1 (y) 5
シフト 暗 号 鍵 K {0, 1, 2,, 25} 暗 号 化 // x {0,1, 25} E K (x) = (x + K) mod 26 復 号 // y {0,1, 25} D K (y) = (y K) mod 26 cryptography p y K=3 FUBWRJUDSKB 6
転 置 暗 号 方 式 鍵 m : 正 の 整 数 π : {1, 2,,m}の 並 べ 替 え( 転 置 ) 暗 号 化 E π (x 1,, x m ) = (x π(1),, x π(m) ) 復 号 D π (y 1,, y m ) = (y π^{ 1}(1),, y π^{ 1}(m) ) 7
転 置 暗 号 の 例 鍵 cryptography C R Y P T O G R A P H Y CTAROPYGHPRY 8
2. ブロック 暗 号 コンピュータを 駆 使 して 換 字 に 転 置 9
ブロック 暗 号 ブロック 暗 号 = 効 率 的 に 計 算 可 能 な E : {0,1} l x {0,1} n {0,1} n ただし 各 第 一 引 数 kについて E k ( )は 置 換 ( 全 単 射 ) 鍵 : k $ {0,1} l 暗 号 化 : c E k (m) (m {0,1} n ) 復 号 : m E 1 1 k (c) (c {0,1} n ) 理 想 は 各 E k k( ( )がランダム 置 換 入 力 が1ビットでも 変 化 すると その 影 響 は 全 ての 出 力 ビットに 及 ぶ ランダム 置 換 と 区 別 がつかないような 効 率 的 な 疑 似 ランダム 置 換 を どのように 作 ればよいか? 換 字 と 転 置 を 繰 り 返 す 10
DES E: {0, 1} 56 x {0,1} 64 {0,1} 64 E k (m): // m {0,1} 64 (k 48 1,,k 16 ) KeySchedule(k) // k i {0,1} m IP(m) L 0 R 0 m // L 0 = R 0 =32 for r = 1 to 16 do L r R r 1 ; R r f(k r, R r 1 ) + L r 1 c IP 11 (L 16 R 16 ) return c f がどんな 関 数 であっても E k ( ) は 必 ず 置 換 となる 11
k 1 L 0 R 0 f k 2 L 1 R 1 f k 3 L 2 R 2 f L 3 R 3 12
攪 拌 関 数 f f(j, R): // J = 48, R = 32 R E(R); R R + J R 1 R 2 R 8 R R J for r = 1 to 8 do R i S i (R i ) R R 1 R 2 R 8 32ビット 入 力 E R P(R) return R 48ビット 48ビット 部 分 鍵 48ビット 中 間 データ S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 32ビット P 32ビット 出 力 13
SBox S i : {0,1} 6 {0,1} 4 ; 一 種 の 換 字 暗 号 (i=1, 6) b 1 b 6 b 2 b 3 b 4 b 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 S 1 00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 01 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 10 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 1. 各 Sボックスは4 対 1 関 数 2. 各 行 は0から15を1 回 ずつとる 3. 入 力 の1ビットを 変 えると 出 力 の 少 なくとも2ビットが 変 わる R 0 の1ビットが 変 化 R 1 の2ビットが 変 化 R 2 の4ビットが 変 化 アバランシュ 効 果 14
[Vaudenay05] Figure2.4 より P S 1 E S 2 S 3 S 4 f(j,r) S 5 R S 6 S 7 S 8 15
DESの 問 題 点 鍵 長 l = 56 は 小 さすぎる ブロック 長 n = 64 も 短 すぎる Sボックスの ボ 実 装 はソフトウェアに 不 向 き 16
AES E: {0, 1} 128 x {0,1} 128 {0,1} 128 E k (m): // m {0,1} 128 (k 0,,k 10 ) expand(k) // k i {0,1} 128 s m + k 0 for r = 1 to 10 do s S(s) s shift rows(s) if r 9 then s mix cols(s) s s + k r return s s: 128ビット = 16バイト ソフトウェアでも 高 速 処 理 可 能 s 0 s 4 s 8 s 12 s 1 s 5 s 9 s 13 s 2 s 6 s 10 s 14 s 3 s 7 s 11 s 15 17
GF(2 8 ) バイトは 加 減 乗 除 が 有 限 体 GF(2 8 ) できる 集 合 として G(2 8 ) = {0,1} 8 (a 7,a 6,a 5,a 4,a 3,a 2,a 1,a 0 ) + (b 7,b 6,b 5,b 4,b 3,b 2,b 1,b 0 ) = (a 7 +b 7,a 6 +b 6,a 5 +b 5,a 4 +b 4,a 3 +b 3,a 2 +b 2,a 1 +b 1,a 0 +b 0 ) ( + は XOR ) (a 7,a 6,a 5,a 4,a 3,a 2,a 1,a 0 ) (b 7,b 6,b 5,b 4,b 3,b 2,b 1,b 0 ) = (c 7,c 6,c 5,c 4,c 3,c 2,c 1,c 0 ) ここで c 7 x 7 +c 6 x 6 +c 5 x 5 +c 4 x 4 +c 3 x 3 +c 2 x 2 +c 1 x+c 0 = (a 7 x 7 +a 6 x 6 +a 5 x 5 +a 4 x 4 +a 3 x 3 +a 2 x 2 +a 1 x+a 0 ) (b 7 x 7 +b 6 x 6 +b 5 x 5 +b 4 x 4 +b 3 x 3 +b 2 x 2 +b 1 x+b 0 ) mod (x 8 =x 4 +x 3 +x+1) 例 えば (10000000)+(00000101) = (100000101) x 7 (x 2 + 1) = x 9 + x 7 = x (x 4 +x 3 +x+1) + x 7 = x 7 + x 5 + x 4 + x 2 + x (10000000) (00000101) = (101110110) 18
1. 各 s i の GF(2 8 )の 要 素 としての 逆 数 s i 1 をとる (ただし 0 1 =0とおく ) 2. 各 s i 1 に(ある)アファイン 変 換 を 施 す S s 0 s 4 s 8 s 12 s 1 0 s 1 4 s 1 8 s 1 12 1 1 1 1 s 1 s 5 s 9 s s 1 13 1 s 1 5 s 1 9 s 1 逆 数 13 s 2 s 6 s 10 s 14 s 1 2 s 1 6 s 1 10 s 1 14 s 3 s 7 s 11 s 15 s 1 3 s 1 7 s 1 11 s 1 15 アファイン 変 換 s 0 s 4 s 8 s 12 s 1 s 5 s 9 s 13 s 2 s 6 s 10 s 14 s 3 s 7 s 11 s 15 19
shift rows : 横 方 向 に 転 置 shift rows と mix cols s 0 s 4 s 8 s 12 s 5 s 9 s 13 s 1 s 10 s 14 s 2 s 6 0 1 2 s 0 s 4 s 8 s 12 s 1 s 5 s 9 s 13 s 2 s 6 s 10 s 14 s 15 s 3 s 7 s 11 3 s 3 s 7 s 11 s 15 mix cols: 縦 方 向 に( 換 字 しながら) 転 置 s 0 s 4 s 8 s 12 02 03 01 01 s 0 s 4 s 8 s 12 s 1 s 5 s 9 s 13 s 2 s 6 s 10 s 14 01 02 03 01 01 02 02 03 x s 1 s 5 s 9 s 13 s 2 s 6 s 10 s 14 s 3 s 7 s 11 s 15 03 01 01 02 s 3 s 7 s 11 s 15 20
擬 似 ランダム 置 換 の 安 全 性 定 義 E = {E k } k K : 置 換 族 E k : {0,1} n {0,1} n ; 効 率 的 に 計 算 可 能 オラクル System 0 ( 理 想 ) : [ 初 期 化 ] H 真 のランダム 置 換 [u に 対 して] v H(u) u v System 1 ( 現 実 ) : [ 初 期 化 ] k K [u に 対 して] v E k (u) 定 義 識 別 者 Eが 安 全 な 擬 似 ランダム 置 換 ( 族 ) どのような 現 実 的 な 識 別 者 Dに 対 しても Pr[D=1 System0] Pr[D=1 System1] 0 or 1 が 無 視 できるほど 小 さい 21
DESやAESは 疑 似 ランダム 置 換 か? AESも 擬 似 ランダム 置 換 であると 証 明 されているわけではな い 識 別 者 のクラスを 限 定 すると: DESには 線 形 解 読 が( 理 論 的 には) 有 効 AESは 差 分 解 読 や 線 形 解 読 に 対 して( 証 明 可 能 ) 安 全 22
識 別 者 のクラスを 差 分 識 別 者 に 限 定 差 分 識 別 者 a,b パラメータ: a,b {0,1} n 差 分 解 読 u v オラクル System 0: H( ) System 1: E k ( ) 以 下 を(ある 回 数 ) 繰 り 返 す: u $ {0,1} n オラクルに u を 尋 ねて v 1 を 得 る オラクルに u+a を 尋 ねて v 2 を 得 る if v 2 = v 1 + b output 1 and halt else continue ブ output 0 0 or 1 よいa,bをみつけることが 暗 号 解 析 者 の 腕 の 見 せどころ ブロック 暗 号 E = {E k } が 差 分 解 読 に 対 して 安 全 どのようなa,bに 対 する 差 分 識 別 者 a,bに 対 しても Pr[ 差 分 識 別 者 ab=1 a,b System0] Pr[ 差 分 識 別 者 a,b =1 System1] が 無 視 できるほど 小 さい 23
識 別 者 のクラスを 線 形 識 別 者 に 限 定 線 形 識 別 者 a,b,a パラメータ: a,b {0,1} n A {0, 1, 2, } c 0 以 下 を(ある 回 数 ) 繰 り 返 す: u $ {0,1} n オラクルに u を 尋 ねて v を 得 る if u a = v b c c + 1 線 形 解 読 u v オラクル System 0: H( ) System 1: E k ( ) よいa,b,Aをみつけることが 暗 号 解 析 者 の 腕 の 見 せどころ if c A, output 1 else output 0 ブロック 暗 号 E = {E k } が 線 形 解 読 に 対 して 安 全 どのようなa,b,Aに 対 する 線 形 識 別 者 a,b,aに 対 しても Pr[ 線 形 識 別 者 a,b,a ba=1 System0] Pr[ 線 形 識 別 者 0 or 1 a,b,a =1 System1] が 無 視 できるほど 小 さい 24
識 別 利 得 鍵 の 情 報 E = {E k } k {0,1}^l : ラウンド 数 rのブロック 暗 号 E = {E k} k {0,1}^l : Eから 最 終 ラウンドを 除 いたブロック 暗 号 ラウンド 数 r 1 ある a,bがあって E に 対 する 識 別 者 a,bの 識 別 利 得 が 大 きいとする 次 のようにして 最 終 ラウンド 鍵 k r を 求 めることができる r 1. E k の( 平 文 暗 号 文 ) 対 を 集 める: (X i, (Y il i,l, Y ir i,r )) 2. K k r のランダムな 推 測 値 Z il i,l = f(k, Y il i,l ) + Y ir i,r Z i,r = Y i,l /* Kが 正 しければ (X i, Z i )はE の( 平 文 暗 号 文 ) 対 */ Z i = (Z il, Z ir ) を X i に 対 する 応 答 として 識 別 者 abを 実 行 し i ( i,l, i,r) i a,b その 識 別 利 得 K を 求 める 3. 識 別 利 得 Kの 大 きな K を k r の 推 測 値 として 出 力 25
X L X R E f k 1 k 2 L 1 R 1 f L 2 R 2 f K Y L Y R 26
3. 公 開 鍵 暗 号 計 算 の 非 対 称 性 の 発 見 27
アルゴリズムの3つ 組 (G,E,D) 公 開 鍵 暗 号 鍵 生 成 アルゴリズムG: (pk, sk) G(k) 暗 号 化 アルゴリズムE: c E pk (m) 復 号 アルゴリズムD: m D sk (c) m pk ただし m = D sk (E pk (m))). pk, c から mを 求 めることは 困 難 ( 一 方 向 性 ) sk S c E pk (m) c R m D sk (c) m 28
たとえば N = pq : 大 きな2つの 素 数 の 積 e: φ(n)=(p 1)(q 1)と 互 いに 素 な 整 数 y = RSA e,n () (x) = x e mod N (x {0,1,,N 1}) は 一 方 向 関 数 と 信 じられている(RSA 仮 定 ) すなわち y,e,n を 与 えられても y = RSA e,n (x) となる x は 求 められない a mod N: 整 数 aを を 整 数 Nでわった た 余 り 29
N=0 RSA 関 数 とRSA 仮 定 N 1 1 N = pq y = RSA e,n (x) = x e mod N x から y = x e mod N となるyを 求 めるのは 容 易 y から y = x e mod N となる x を 求 めるのは 困 難 y (=x e mod N) x x から 出 発 して 何 周 してy になったのか? 偶 数 回 それとも 奇 数 回? 30
y = RSA e,n () (x) = x e mod N Nが 素 数 のときは Nが 素 数 pのときは y から y = RSA e,p (x) となる x を 求 めるのは 容 易 φ(p) = p 1, d = e 1 mod (p 1) RSA dp = RSA ep 1 RSA d,p RSA e,p N = pq のときもRSA dn = 1 en = 1 d,n RSA e,n ( d e mod φ(n) ) ところが φ(n) =? が 分 からない (p, qを 知 っていれば 分 かる ) 31
RSA 暗 号 多 項 式 時 間 アルゴリズムの3つ 組 (G,E,D) 鍵 生 成 アルゴリズム G: p, q 異 なるランダムな 素 数 ; N = p q; e: φ(n)=(p 1)(q 1)と (p 1)と 互 いに 素 な 整 数 ; d e 1 mod φ(n) pk = {N,e}, sk = {N,d} 暗 号 化 アルゴリズム E: E pk (m) = m e mod N // = RSA e,n (m) p, 復 号 アルゴリズム D: D sk( (c) = c d mod N // = RSA dn d,n( (c) RSA dn = RSA 1 d,n en e,n [ オイラーの 定 理 ] RSA 仮 定 : RSA e,n は 一 方 向 関 数 32
素 数 を 法 としたべき 乗 数 p: 素 数 q: p 1 を 割 る 素 数 g : mod p で 位 数 がqの 整 数 <p, q, g> 指 定 {1, g mod p, g 2 mod p,., g q 1 mod p} 例 <p=43, q=7, g=4> g 0 mod p = 1, g mod p = 4 g 2 mod p = 16, g 3 mod p = 21 g 4 mod p = 41, g 5 mod p = 35 g 6 mod p = 11 全 て 異 なる 巨 大 な 数 の( 算 法 つき) 集 合 (g q mod p = 1) <p=43, q=7, g=4> {1,4,16,21,41,35,11} 33
CDH 仮 定 p: 素 数 q: p 1 を 割 る 素 数 g : mod p で 位 数 がq <p, q, g>に に 対 して CDH 仮 定 a, b $ {1,2,,q} どんな 効 率 的 なアルゴリズムも g a mod p と g b mod p を 与 えられて g ab mod p を 求 めることはできない <p=43, q=7, g=4>? g 3 mod p = 21, g 5 mod p = 35 g 15 mod p = 4 34
DDH 仮 定 <p, q, g>に 対 して DDH 仮 定 a, b, c $ {1,2,,q} どんな 効 率 的 なアルゴリズムも g a mod p と g b mod p を 与 えられても g ab mod p と g c mod p を 区 別 できない すなわち g a mod p と g b mod p を 教 わっても g ab mod p はまったく 分 からない ( 情 けない 話 ではある) <p=43, q=7, g=4> (21, 35, 4) OR (21, 35, 11) どちらが 正 しい? 35
エルガマル 暗 号 多 項 式 時 間 アルゴリズムの3つ 組 (G,E,D) 鍵 生 成 アルゴリズム G: p, q, g 素 数 p,qと 整 数 g ただし q p 1, g q = 1 mod p x $ {1,,q 1}, y g x mod p pk= {pgqy} {p,g,q,y}, sk = {pgqx} {p,g,q,x} 暗 号 化 アルゴリズム E pk (m): r $ {1,,q 1}} c = (g r mod p, my r mod p) 復 号 アルゴリズム D sk (c 1,c 2 ): c 2 / c x 1 mod p DDH 仮 定 のもとでIND CPA 安 全 36
c = (g r, my r ) y = g x エルガマル 暗 号 のからくり y r = g xr Enc Dec r g x CDH 仮 定 g r x g r g x 37
RSA 暗 号 に 対 する 攻 撃 m { 賛 成, 反 対 } 賛 成 pk={n,e} sk={n,d} S c = 賛 成 e mod n R c pk={n,e} A c 1 = 賛 成 e mod n c 2 = 反 対 e mod n c = c 1 ならば 賛 成 else 反 対 賛 成 c d mod n 賛 成 RSA 暗 号 は IND CPAでない な 賛 成 38
(G, E, D): 公 開 鍵 暗 号 識 別 不 可 能 性 (IND CPA) オラクル System 0 : [ 初 期 化 ] (pk,sk) G [(m 0,m 1 ) に 対 して] c* E pk (m 0 ) pk m 0,m 1 c* System 1 : [ 初 期 化 ] (pk,sk) G [(m 0,m 1 ) に 対 して] c* E pk (m 1 ) 定 義 識 別 者 EがIND CPA が C 安 全 どのような 現 実 的 な 識 別 者 Dに 対 しても 0 or 1 Pr[D=1 System0] Pr[D=1 System1] ] が 無 視 できるほど 小 さい 39
エルガマル 暗 号 に 対 する 攻 撃 m {(ある 商 品 に 対 する) 注 文 個 数 } m=10 pk={p,g,q,y} sk={p,g,q,x} S c = (g r, 10y r ) R c=(c 1,c 2 ) pk={p,g,q,y} gqy} A c 2 = c 2 x 100 c =(c 1,c 2 ) m = 1000/100 = 10 1000 c 2 /c 1x mod n 本 当 に1000 個 も 注 文 するの? エルガマル 暗 号 は IND CCAでない (DDH 仮 定 のもとでIND CPA) 40
(G, E, D): 公 開 鍵 暗 号 識 別 不 可 能 性 (IND CCA) オラクル pk c m m 0, m c* 1 c m System 0 : [ 初 期 化 ] (pk,sk) G [(m 0,m 1 ) に 対 して] c* E pk (m 0 ) [c に 対 して] m D sk (c) (c c*) System 1 : [ 初 期 化 ] (pk,sk) G [(m 0,m 1 ) に 対 して] c* E pk (m 1 ) [c に 対 して] m D sk (c) (c c*) (*) (*) 定 義 識 別 者 EがIND CCA が 安 全 どのような 現 実 的 な 識 別 者 Dに 対 しても 0 or 1 Pr[D=1 System0] Pr[D=1 System1] ] が 無 視 できるほど 小 さい 41
ハッシュ 関 数 効 率 的 な( 圧 縮 ) 関 数 H: {0,1}* {0,1} h Hが 衝 突 困 難 : どのような 現 実 的 なアルゴリズムも H(x)=H(y)となるx, y (x y) を 見 つけることはできない ランダムオラクルモデル: プログラム 中 のすべてのz H(x) を ランダムオラクルへの 問 い 合 わせに 置 き 換 える プログラム... z H(x)... x z H $ { H: {0,1} 1}* {0,1} h } z = H(x) () 42
OAEP+ f : {0,1} k {0,1} k : 置 換, g = f 1 k 0 +k 1 <k, 2 k0,2 k1 : negligible, n = k k 0 k 1 G : {0,1} k0 {0,1} n, H : {0,1} n+k0 nk0 {0,1} k1, H : {0,1} n+k1 nk1 {0,1} k0 x {0,1} n f y g Enc r $ {0,1} k0 s = (G(r) + x) H (r x) t = H(s) + r w = s t y = f(w) Dec w = g(y) s t = w r = H(s) + t x = G(r) + s[0..(n 1)] c = s[n..(n+k 1 1)]? c = H (r x): x else reject f がone wayならばoaep+(f)はランダムオラクルモデルのもとでind CCA 43
OAEP+の 暗 号 文 x r 暗 号 文 の 正 当 性 をチェックするための 冗 長 な 情 報 x + G(r) () H (r x) H(s) () + r s f y r やsを 知 らずに 正 当 な 暗 号 文 を 作 ることはできない 44
FO 変 換 π = (K, E, D), H = {H n } n π = (K, E, D ) = FO H (π): K (1 k ) : (pk, sk) K(1 k ), H $ H k pk = (pk, H), sk = sk E (pk,m): r $ R m ~ = m r c = E pk (m ~ ; H(m ~ )) D (sk,c): m ~ = D sk (c) m r = m ~ c =? E pk (m ~ ; H(m ~ )) : m else ランダムオラクルモデルのもとで π: IND CPA γ uniform π : IND CCA γ(x,y) = def Pr[ γ $ R : y = E pk (x;r)] π is γ uniform if x,y, γ(x,y) γ 45
4. IDベース ス 暗 号 46
IDベース 暗 号 E = (Setup, Extract, Enc, Dec) (params, master key) Setup(k) d ID Extract params (master key, ID) c Enc params (ID, m) m Dec params (d ID, c) 鍵 配 布 センター (params, master key) Setup(k) ID d ID Extract params (master key, ID) ID params params ID m params d ID 送 信 者 c Enc params (ID, m) c 受 信 者 (ID) m Dec params (d ID, c) m 47
識 別 不 可 能 性 (IND ID CPA) (Setup, Extract, Enc, Dec): IDベース 暗 号 オラクル System 0 : [ 初 期 化 ] (params,master key) Setup [(m 0,m 1, ID*):] c* Enc params (ID*, m 0 ) [ID:] d Et Extractt params (master key, ID) (ID ID*) params ID d m 0, m 1, ID* c* ID d System 1 : [ 初 期 化 ] (params,master key) ) St Setup [(m 0,m 1, ID*):] c* Enc params (ID*, m 1 ) [ID:] d Extract params (master key, ID) (ID ID*) (*) (*) 定 義 識 別 者 EがIND ID CPA が C 安 全 どのような 現 実 的 な 識 別 者 Dに 対 しても 0 or 1 Pr[D=1 System0] Pr[D=1 System1] ] が 無 視 できるほど 小 さい 48
Bilinear maps G 1, G 2 : 素 数 位 数 q の 群 e : G 1 x G 1 G 2 が bilinear map とは 1. (Bilinear) e(ap, bq) = e(p,q) ab ( PQ G ( P,Q G 1, a,b Z) 2. ( 非 退 化 ) e(p,p) 1 ( P( 0) G 1 ) 3. ( 計 算 可 能 ) e(p,q)は 効 率 的 に 計 算 可 能 ( P,Q G) 楕 円 曲 線 上 の Weil paring を 用 いて 実 現 49
BF 暗 号 [BF01] bilinear map 版 のエルガマル 暗 号 BF = (Setup, Extract, Encrypt, Decrypt): Setup(k): Encrypt(params, ID, m): <q, G 1 1, G 2 2, e> G(k) ) Q ID = H 1 (ID) P $ G r $ 1, s $ Z q *, P pub = s P Z q * Choose g ID = e(q ID, P pub ) H 1 : {0,1} 1}* G 1 * c = < rp, m + H 2 (g IDr )> H 2 : G 2 {0,1} n params = <q,g Decrypt(params, c=<u,v>, d ID ): 1,G 2,e,n,P,P pub,h 1,H 2 > m = V + H 2 (e(d, U)) 2( ( ID master key = s Extract(ID, params, s): Q ID = H 1 (ID) ( G 1 *) d ID = s Q ID ランダムオラクルモデルにおいて BF 暗 号 はGに G 対 するBDH 仮 定 のもとで IND ID CPA 安 全 50
BDH 仮 定 G 1, G 2 : 素 数 位 数 q e : G 1 x G 1 G 2 ; bilinear map P G 1 * <e, q, P>に に 対 して BDH 仮 定 a, b, c $ {1,2,,q} どんな 効 率 的 なアルゴリズムも ap, bp, cpを 与 えられて e(p,p) abc を 求 めることはできない 51
c = < U, m + H 2 2(g IDr )> P pub = sp U = rp Q ID = kp Enc BF 暗 号 のからくり g IDr = e(p,p) ksr Dec r kp sp BDH 仮 定 kp( ksp (=d ID ) rp rp kp sp 自 由 度 k ユーザID 52
今 後 の 暗 号 について ランダムオラクルモデルからの 脱 却 bl bilinear map の 意 味 各 種 多 機 能 暗 号 閾 値 復 号 放 送 暗 号 属 性 ベース 暗 号 など 暗 号 プロトコルの 構 成 部 品 としての 機 能 より 高 度 または 繊 細 な 安 全 性 フォワードセキュリティ アダプティブセキュリティ 量 子 計 算 機 への 対 応 53
記 号 {0,1} n : nビットの 文 字 列 全 体 {0,1}* : 全 ての 有 限 長 の 文 字 列 全 体 k $ {0,1} n : nビットの 文 字 列 kをランダムに 選 択 z = x + y : z は x と y との 桁 ごとの 排 他 的 論 理 和 0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1 y A(x) : 入 力 xでアルゴリズムaを 実 行 し 出 力 y を 得 た Pr[E] : Eがおきる 確 率 Pr[E C] : 条 件 Cのもとで Eがおきる 確 率 a mod N: 整 数 aを 整 数 Nでわった 余 り 54
参 考 文 献 主 なもの At Arto Sl Salomma, Public Key Cryptography, Second dedition, Springer, 1996 [Vaudenay05] Serge Vaudenay, A Classical Introduction to Cryptography: Applications for Communications Security, Springer, 2005 J. Katz, Y. Lindell, "Introduction to Modern Cryptography: Principles And Protocols", Chapman & Hall/Crc, 2007. [BF01] D.Boneh, M.Franklin, Identity Based Encryption fromthe Weil Pairing, CRYPTO 01, LNCS 2139, pp. 213 229. 55