数理解析研究所講究録 1420 巻 2005 年 117-127117双線型写像の公開鍵暗号への応用に関してApplication of bilinear map to public-key encryption
北陸先端科学技術大学院大学
Japan Advanced Institute of Science and Technology
宮地充子

Atsuko Miyaji
概婁
本報告書は, 双線型写像により可能になる公開鍵暗号の様々な応用,
する.

1

さらに残る課題について報告

はじめに

ネットワークの普及により各種サービスがネットワークを介して実現できる基盤が確立しっっある. 電子医療, 電子政府などでは, 物理的な文書に代わり電子的なデータがネットワーク上流通するようになる.
こうして情報セキュリティの技術である公開鍵暗号系によるデータの秘匿及び完全性の技術が不可欠になっ公開鍵暗号とディジタル署名という二つの技術の総称で, ユーザは秘密鍵及び公開鍵と呼ばれる異なる鍵ペアを生成し, 公開鍵は公開し, 該当ユーザへのデータの暗号化や該当ユーザの作成したデータに対する署名の検証に用い, 秘密鍵は秘密に管理し, 自分宛の暗号文の復号や作成したデー
タに対する署名の生成に用いる. このような公開鍵暗号系を実現するのが, 素因数分解闘題 楕円曲線上の離散対数問題 (ECDLP), 有限体上の離散対数問題である. これらはすべて数論の分野で良く知られてた. 公開鍵暗号系とは,$\uparrow_{\sqrt}\backslash$

る事実を応用したものである.
近年,

このような従来の聞題では解決できない技術が脚光をあびるようになってきた. 一つは, 二進化

公開鍵暗号系と呼ばれる起しい公開鍵暗号のパラダイムであり, もう一つはブロードキャスト暗号と呼ばの動的に受信者が変わる秘匿通信である. これらを解決する新しい数論の応用が双線型写像でれる 1 対である.
ある. なお, 双線型写像のうち実際に暗号への応用が期待されているのは, Weil 対 [7]
従来公開鍵暗暑系では, ユーザがもつ秘密鍵は露呈しない, あるいは, 秘密鍵は紙冠ンパ機器に格納さ$n$

攻撃に対する安全性をれ流出しないとい. B84J 提のもと, その方式への)実的である. \not\equiv 際
鍵が露呈しないとい.:.) BRfJ 提は, $8fl$ らかに$\ovalbox{\tt\small REJECT}--\frac{\wedge}{\mathrm{w}}\mathrm{A}_{\mathbb{I}l}$$\text{理_{}\vec{\mathrm{w}1\mathbb{R}}}\wedge$$\check{\mathit{2}}$$\mathrm{f}\mathrm{f}\mathrm{l}^{\backslash }\backslash ^{\mathrm{J}\backslash }\mathrm{f}\mathrm{f}\mathrm{i}\backslash \text{鍵}\sigma$

攻撃は,$\mathrm{a}_{\yen}^{\mathrm{D}}$$\ni\not\in \text{現}$した.

しかしながら, 秘密.
,$/\backslash \text{開}\Delta \text{鍵}$そのものに対する理論攻撃より容易であり, 秘密鍵の露呈を考慮した安全性の議論は必須と

pg 号系の方式$1_{\sqrt}\backslash$

える.

こう

して鍵進化ディジタル署名及び鍵進化公開鍵暗号という鍵進化公開鍵暗号系の概念が提案された [?]. 鍵進

化公開鍵暗号系とは, 公開鍵と秘密鍵という 2 つの鍵ペアのうち, 公開鍵は不変で対応する秘密鍵のみ定進化暗号は, その形態からである.
期的に進化 (変化) することで, 秘密鍵の露呈攻撃に強化した
もう一つは 2 エン
大きく 2 つに分けられる. 1 つはユーザのみの 1 エンティティで実現される方式であり,
エンティティからな
ティティ, ユーザとベース 1 により実現される方式である. 鍵進化公開鍵暗号系は, 1
エンティティからなる Key-insulated 暗号系, Intrusion-resilient 暗号系の 3
暗号系,$\mathrm{f}\mathrm{f}\mathrm{l}\hat{- \mathrm{p}_{\backslash }.},$る Forward

secure2

鍵進化ディジタル署
つに分けられる. なお, 最強の安全性を有するのが Intrusion-resilient 暗号系である.
分解に基づく効率的な Intrusion-resilient 署名が提案され, さらにそのモ名に関しては, 2002 年に素$\mathbb{E}\backslash \ovalbox{\tt\small REJECT}’$$1\text{ュ}$–ザは PDA などの携帯端宋,ベ–

スは自宅の\acute くーソナルコンピュータに対志する

118
デル化の提案により, 任意の一方向性関数を利用した Intrusion-resilient 署名が可能となった. 一方, 鍵進化公開鍵暗号は従来の素因数分解闇題 ECDLP, DLP などでは実現ができず, 双線型ディッフィヘルマン
問題を利用して Intrusion-resilient 暗号が 2003 年に初めて実現された [4].
-方, ブロードキャスト暗号とは, デジタルコンテンツの著作権管理・保護を実現する電子配信の方法である [?, ?]. ブロードキャスト暗号は, コンテンツを得ることが許可されたユーザの集合に対し, 公衆放送網を通しての安全で効率的な情報配信を冒的とした暗号で, 以下のフェーズからなる. (1) 秘密情報を各ユーザに秘密通信で配布, (2) 配信者は復号を許可するユーザの部分集合 を決定, (3) コンテンツを暗号化し, 暗号化の鍵 (session 鍵) を に属するユーザのみが復号できる鍵 (subset 鍵) で暗号化, (4) 暗号化コンテンツ +{暗号化 session 鍵} を公衆放送網を通して全ユーザに送信, ( $5,1S$ に含まれるユーザは, 初期に配布された秘密情報から subset 鍵を生成し, session 鍵を復号し暗号化コンテンツを復号する. 既存の方法[6] は, コンテンツ配信者がユーザの秘密情報を管理することで実現する. つまり, ブロードキャスト暗号
$S$

$S$

の安全性は, コンテンツ配信者自身の鍵管理に依存し, 同じ配送網及びユーザ復号機を利用して他のコンテンツ配信者が利用できない. つまりフレキシブルなサービスの管理という観点では, ユーザの秘密情報を利用した鍵配信より, ユーザの公開鍵などの公開情報を用いた鍵配信が好ましいといえる. これが公開鍵に基づくブロードキャスト暗号である, しかしながら, 公開鍵暗号を用いたブロードキャスト暗号の実現は難しく, 従来の素因数分解問題, ECDLP, DLP などでは実理ができず, 双線型ディッフィヘルマン問題を利用して公開鍵暗号を利用した現実的なブロードキャスト暗号は, 初めて [2] により実現された.
問題について記述するとともに, 鍵進化公本報告書では, このように新しい問題を解決する双線型$\mathrm{D}\mathrm{H}$

開鍵暗号系, ブロードキャスト暗号について述べる,

2

準備

2.1

双線型 Diffie-Hellman 問題$\mathrm{G}_{1}$は加法的に, G2 は乗法的に表現する. また \^e :を位数とする巡回群とし,を多項式時間で計算可能な非退化な双線型写像 \^e が定義されているとする. すなわち,
かつ \^e(G, $G$ )をみた引 この双線型写像を用いて, 双線型 Diffie-Hellman, G2 を大きな素数$\mathrm{G}_{1}\mathrm{x}\mathrm{G}_{1}arrow \mathrm{G}_{2}$\^e(aQ, $bR$)$\mathrm{G}_{1}$$q$$=\hat{\epsilon}(Q, R)^{ab}$$\neq 1\in \mathbb{Z}_{l}^{*}$

問題 (BDHP) が以下のように定義できる.
定義 1

を素数位数
の群 $\mathrm{G}=<G>$ とし, 多項式晴聞で計算可能な非退化な双線型写像 \^e が定義されているとする. すなわち, \^e(aQ, bR)=\^e $(Q, R)^{ab}$ かつ \^e(G, $G$ )をみたす この時, 双線型$\mathrm{G}$$q$$\neq 1\in\wedge \mathbb{Z}_{\mathit{1}}^{*}$

Dffie-He $llma7b$ Pr0blem(BDH 功とは, $<G,$ $aG,$$2\prime 2$$bG,$ $cG>$に対して \^e $(G, G)^{abc}$ を求める問題である.

ID ベース暗号

ベース暗号は, ユーザの公開
ベース暗号の概念について説明する $[?]$ .
鍵にユーザの名前や住所, 電話番号, メールアドレスという任意のビット列を利用する方式で, 公開鍵暗号に必要となる公開鍵証明書が不要になる. なお具体的な方式は, 前述の BDHP を用いて実現される.
ここでは,

BDHP を用いた$\mathrm{I}\mathrm{D}$$\mathrm{I}\mathrm{D}$定義 2 $ID$ ベース暗号とは, 以 . の性質を満たす 4 つの確率的多項式時問アルゴリズム (IBE-KGen, IBE-KDer,$\mathrm{I}\mathrm{B}\mathrm{E}^{-}\mathrm{E}\mathrm{n}\mathrm{c}$, IBE-Dec) の組である,

119
1. IBE-KGen は, 入力のセキュリティパラメータ$1^{k}$

に対して, センタ公開鍵と秘密鍵の対, $(PK, s)$ をである.
出力する確率的多項式時間アルゴリズム,
2. IBE-KDer は, センタの公開鍵 $PK$ と秘密鍵 , ユーザ $IDt$ に対して, ユーザ $IDt$ t ご対応する秘密である.
を出力する確率的多項式時問アルゴリズム
鍵$(PK, s)arrow \mathrm{I}\mathrm{B}\mathrm{E}^{-}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(1^{k})$$s$$Starrow \mathrm{I}\mathrm{B}\mathrm{E}^{-}\mathrm{K}\mathrm{D}\mathrm{e}\mathrm{r}(PK, s,t)$

$St$

3.

$\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{h}\mathrm{c}$は, センタの公開鍵 $PK$ , ユーザ $IDt$ , 平文 $m\in\{0,1\}^{k}$ に対して, 暗号文 $c\in\{0,1\}^{*}$ を出-翼 c(PK,
力する確率的多項式時間アルゴリズム
に対して,
$IDt$
の秘密鍵
は
,
ユーザ
暗号文
,
4
$\mathrm{c}arrow \mathrm{I}\mathrm{B}\mathrm{E}$$\cdot$アルゴリズム2.2.1

階層的$marrow \mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{D}\mathrm{e}\mathrm{c}(St, C)$$\mathrm{I}\mathrm{D}$) である.

$m\in\{0,1\}^{*}$

$St$

$C$

$\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{D}\mathrm{e}\mathrm{c}$$t_{\mathrm{J}}m$を出力する確率的多項式時聞

である.

ベース暗号

ベース暗号で, 各ノードは子
ベース暗号 ([3]) は、ユーザを木構造の各ノードに対応させた
階層的はルートノードまでのノード列となる. ユーザ を $v=v0v_{1}\cdots v_{t}$ノードの秘密鍵を生成し, ノードのの子ノードは $vv_{t+1}=v_{0}\cdots v_{t}v_{t+1}$ と表記する. また, $v|_{k}=v0\ldots vk$ でと表記し, 木のルートを )ある. 以下の 4 つの確率的アルゴリズムで構成される. なお具体的な方式は, 前述の BDHP を用いて実現$\mathrm{I}\mathrm{D}$$\mathrm{I}\mathrm{D}$$v$$\mathrm{I}\mathrm{D}$$v\mathrm{r}$される$=\epsilon,$

$v$

[3],

HIBE-KGen
セキュリティ. パラメータ$1^{k}$の入力に対し, システムの公開鍵 $PK$ とルートの秘密鍵

る確率的多項式時間アルゴリズム,$(PK, SK_{\epsilon})arrow \mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}^{-}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(1^{k})$を生成す$SK_{\epsilon}$

である.

HIBE-KDer
システムの公開鍵 $PK$ とノード $v=v_{1}\cdots v_{l}$ とその秘密鍵 $SK_{v}$ の入力に対し,
鍵 SKvv’+、を生成する確率的多項式時間アルゴリズム,$v$の子 $vvt+1$ の秘密$SK_{vv_{t+1}}arrow \mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(PK,$$v,$ $vt+1$, SK のである、$\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{E}\mathrm{n}c$

システムの公開鍵 $PK$ , 送信先ノード $v=v_{0}\cdots v_{t}$ とメッセージ $m$ の入力に対し, 暗号文
る確率的多項式時間アルゴリズム c\leftarrow H 工 BE-恥 c(PK, $v,m$ ) である.

HIBE-Decシステムの公開鍵 $PK,$$\text{ノ}-\text{ト^{}\backslash ^{\backslash }}v$率的多項式時間アルゴリズム,

3の秘密鍵 $SK_{v}$ と暗号文

$marrow \mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{D}\mathrm{e}\mathrm{c}(S\mathrm{A}_{v}’, c)$

$c$

$c$

を出力す

の入力に対し, メッセージ $m$ を出力する確である.

鍵進化公開鍵暗号系
本章では,

3.1

鍵進化暗号の基本的な概念及び安全性のレベルにつ ‘て述べる.
$\mathrm{t}_{\mathit{1}}$

鍵露呈に対する安全性
どの一定の期間毎に更新し, ある期間の \Phi ‘鍵の露呈が出の露呈を意味しないように公開鍵暗号を構築する. ここで, *‘fr,,」^‘する公開鍵は変化せずに

鍵進化暗号では, ユーザの

全期間の

,

$\text{秘^{}\backslash }\text{密}$$\mathrm{f}\mathrm{f}\mathrm{i}^{\backslash }\backslash \text{密^{}\tau}\mathrm{f}\mathrm{f}\mathrm{l}$

$s.k$

を一

$\mathrm{f}\mathrm{f}\mathrm{i}^{\backslash }$$pfi\exists f_{\grave{\mathrm{A}}}$

120
そのままであることに注意したい. 通常の公開鍵暗号における暗号化が, 平文と公開鍵の入力でなされるのに対し, 鍵進化暗号の暗号化は, 平文と公開鍵, 期間 の 3 つの入力でなされる. 鍵進化暗号において$t$考慮する安全性は次の二つになる.

Forward security:

ある期間$t_{0}$の秘密鍵$sk_{t0}$が露呈しても, その期問より前の秘密鍵 $sk_{t}(t<t0)$ は露呈しない.

Future security:

ある期間 to の秘密鍵

$sk_{t0}$が露呈しても, その期間より後の秘密鍵 $sk_{t}(t>t0)$ は露呈しない,
鍵進化暗号は, その形態から大きく 2 つに分けられる.

1 つはユーザのみの 1 エンティティで実現される

もう一つは 2 エンティティ, ユーザとベースにより実現される方式である. ユーザの秘密鍵
を 2 つに分離しない限り, future security は実現できないことに注意したい, 耐鍵侵入暗号は, その機能方式であり,

forward-security を実現する forw ば secure 暗号, ユーザ秘密鍵を 2 つにわけ, ffiture-security も考慮した Key-insulated 暗号, Intrusion-resilient 暗号の 3 つに分けられる. 以降, Forward secure 暗号とIntrusion-resilient 暗号のそれぞれの原理及び安全性の定義を述べる,
により,

3.2

$\mathrm{d}$Forward-secure 暗号

Forward-secure 暗号は, 1 エンティティで案現される鍵進化暗号であり, Forward security を実現する.
つまり, ある期閤
の秘密鍵轟 0 の露呈は, その期間より前の $t<t_{0}$ の秘密鍵の轟の安全性に影響し$t_{0}$ない,

定義 3([1]) Forward-secure 暗号とは, 以下の性質を満たす 4 つの確率的多項式時問アルゴリズム(FSKG, FSUpd, FSEnc, FSDe c) の組である,

1. FSKG は, 入力のセキュリティパラメータ$1^{k}$

を出力する確率的多項式時間アルゴリズム

2. FSUpd は, 時間に対して, ユーザ公開鍵, ユーザの秘密鍵の初期値 $(P, sh))$$(P, sk_{0})arrow \mathrm{F}\mathrm{S}\mathrm{K}\mathrm{G}(1^{k})$である.

のユーザの秘密鍵に対して時間 $t+1$ のユーザ秘密鍵を出力する確率的
多項式時間アルゴリズム
である.
3\sim S 血 c は, ユーザ公開鍵 $P$ , 期間 , 平文 $m\in\{0,1\}^{k}$ に対して, 暗号文 $c\in\{0,1\}^{*}$ を出力する確率的多項式時間アルゴリズム
である.
4. FSDec は, 暗号文 , 期間 のユーザの秘密鍵 s 傷に対して, $m\in\{0,1\}^{*}$ を出力する確率的多項式時
間アルゴリズム
である.
$skt$

$t$

$sk\mathfrak{x}+1$$sk_{t+1}arrow \mathrm{F}\mathrm{S}\mathrm{U}\mathrm{p}\mathrm{d}(sk_{l}, t)$$t$$carrow \mathrm{F}\mathrm{S}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{c}(P, t, m)$

$c$

$t$

$marrow \mathrm{F}\mathrm{S}\mathrm{D}\mathrm{e}\mathrm{c}(skt, \mathrm{c})$次に安全性の定義を与える. Forward-secure 暗号の安全性の定義は公開鍵暗号の定義とほぼ同様に与えられる. 公開鍵暗号との違いは, Forward-secure 暗号では, 各奇聞 に対応する秘密鍵も攻撃者が入手 (鍵オラクル) できることである. つまり, 攻撃者には復号オラクルと鍵オラクルが与えられ, 適応的に対応する平文や鍵が入手できる. 以下で, 復号オラクルも与えられるより強い安全性に関する定義のみを与える.
$t$$(\mathrm{O}_{\mathrm{F}\mathrm{S}\mathrm{D}\mathrm{e}\mathrm{c}})$定義 4$(\mathrm{F}\mathrm{S}-\mathrm{I}\mathrm{N}\mathrm{D}-\mathrm{C}\mathrm{C}\mathrm{A})$$(O_{\mathrm{F}\mathrm{S}\sec})$

Forward-secure 暗号 (FSKG, FSUpd, FSEnc, FSDec) に対して, アルゴリズム$A$は, 3 っのオラクルが与えられる,$\circ$

復号オラクル$O_{\mathrm{f}\approx \mathrm{D}\epsilon \mathrm{c}}$: 任意の暗号文と期聞$t$の入力に対し, 期問$t$でのユーザ秘密鍵の復号結果を出力

121
する.
鍵オラクル
$o$

$o$

: 任意の期間 l こ対し, 期間 のユーザ秘密鍵を出力する.
の入力に対しそのどちらかの暗号文と: 長さの等しい 2 つの平文
チャレンジオラクル$t$$t$$O_{\mathrm{f}\mathrm{s}\mathrm{S}\epsilon \mathrm{c}}$$O_{\mathrm{L}\mathrm{R}}$$m\mathit{0}$$m_{1}$

を出力する.
は 3 つのオラクルが与えられ, 次の過程を実行する多項式時問アルゴリズムである$c^{*}=\mathrm{F}\mathrm{S}\mathrm{E}\mathrm{n}\mathrm{c}(P, t, m_{b})(b=0,1)$$A$

初期設定 : 鍵生成アルゴリズム FSKG を実行させて, ( $P$, s 恥) を出力させ,攻撃 :は, 復号オラクル$A$$O_{\mathrm{f}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{c}}$, 鍵オラクル$O_{\mathrm{f}\mathrm{s}\mathrm{S}\mathrm{e}\mathrm{c}}$$A$に $P$ を入力する,, チャレンジオラクル O よに適応的に質問を繰り返しその回答を入手する. 但し, 以下の制限事項をまもる.
には一度しか質問しない.
には質問しない.
をの出力には質問しない,なる . をに対しての入力$\circ \mathrm{O}_{\mathrm{L}\mathrm{R}}$$c^{*}$$\circ O_{\mathrm{L}R}$$\circ O_{\mathrm{I}\mathrm{R}}$

出力 :

$A$

$Fo\mathrm{r}wa7d$$O_{\mathrm{f}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{c}}$$t^{*}\geq t$$t^{*}$$t$$O_{\mathrm{f}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{c}}$は, $b’=\{0,1\}$ を出力し, $b=b’$ であれば $A$ は攻撃に成功したとする.

-secure 暗号が適応的選択暗号文攻撃に対して識別不可能性を満たす (IND-FS-CCA)で定義された任意の多項式詳聞アルゴリズムとは, 上記の成功確率がセキュリティパラメータに対して無視できる$A$

ぐらい小さいことをいう.

3.3

Intrusion-resilient 暗号

Intrusion-resilient 暗号は, Key-isulated 暗号の安全性を強化した概念であり, ユーザとベースの両方を攻撃されても, 同じ期間が攻撃されない限り, ユーザの秘密鍵の安全姓は保たれる. つまり, ある期間
(future(forward-security), そしてその期間より後の秘密鍵 $sk0$ の露呈は, その期間より前
て攻撃され
にお化
security) の秘密鍵の安全性に影響しない. さらに, ユーザとベースの両方が同じ期間 toの安全性に影響しない.
ても, その期間より前 $t<t_{0}$ (forward-security) の秘密鍵
Intrusion-resielient 暗号では, ベースとユーザの同時期の鍵露呈攻撃に対する安全性強化のために リフというパラメータが追加される. リフレッシュ はベースとユーザの鍵を更新するためのパラメー
レッシュ
タであるが, 1 つの期間 内を分割するパラメータとなり, 暗号化には関与しない. つまり, データの暗号化$f,0$$t>t\mathit{0}$$t<t\mathit{0}$$\mathrm{a}$$sk_{t}$

$r$

$r$

$t$

は必要だがリフレッシュ情報 I ま不要である. 例えば, 期問 が 1 日に対応しリフレッシュが 1 時間に対応するとすると, 攻撃者が同じ月日かつ同じ時間のユーザとベースの鍵を入手しない限り,$m$future security も forward security が満たされることになる. 一方, 暗号化は, IREnc(P, 1900/12/31, )というように日単位までの情報だけで実現できる. 端的にいえば, 簡単な負荷で安全性を強化するパラメーには, 期間情報

$t$

$t$

$r$

タといえる.
ここでは,

定義 5([5])($\mathrm{I}\mathrm{R}\mathrm{K}\mathrm{G}_{j}$Intrusion-resilient 暗号の厳密な定義を与える.
$Intms\mathrm{i}on- res\dot{\epsilon}lient$

暗号とは, 以下の性質を満たす

7 つの確率的多項式時間アルゴリズム

IRUserUpd, IRBaseUpd, IRUserRef, I 瑠 aseRef, IREnc, IRDec) の組である.

1. U 区l ま, 入力のセキュリティパラメータ式] する確率的$(P, skb_{0.0}, sk_{0.0})$ を$\mathrm{G}$$|^{1}\mathrm{t}_{1}^{\mathrm{J}}f$$\text{多}\prime \mathrm{E}$$1^{k}$

に対して, 公開鍵, ベース鍵,$\text{時}5_{\mathrm{S}}5\text{ア^{}\mathrm{K}}$

レゴリズム (P, ’k 煽 ,8 都 )
$.0$

$.0$

ユーザの秘密鍵の初期値$arrow \mathrm{I}\mathrm{R}\mathrm{K}\mathrm{G}(1^{k})$

である.

122
2. IRBaseUpd は, 時間$t$, リフレッシュのベース秘密鍵 $skb_{t.r}$ に対して, 時間 $l+1$ のベース鍵 $skbt+1.0$ ,$r$

ユーザ秘密鍵の更新データ skut を出力する確率的多項式時間アルゴリズム$(skb_{t+1.0}, sku_{t})arrow \mathrm{I}\mathrm{R}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}(skb_{t.r})$

3. 工 RUserUpd は,

時間

$t$

,

である.

リフレッシュ

$r$のユーザの秘密鍵$sk_{t.r}$skutとベースからの更新データに対して時間 $t+1$ のユーザ秘密鍵 $sk_{t+1.0}$ を出力する確率的多項式時間アルゴリズム
である.
4. IRBaseRef は, 時間 , リフレッシュ のベース鍵 $skb_{t.r}$ に対して, 時間 , リフレッシュ $r+1$ の$sk_{t+1.0}arrow$$\mathrm{I}\mathrm{R}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{U}\mathrm{p}\mathrm{d}(sk_{t.r}, sku_{t})$

$t$

$t$

$r$

ベース鍵 $skb_{t.r+1}$ , 鍵リフレッシュデータ $skr_{t.r}$ を出力する確率的多項式時間アルゴリズム$(skb_{t.r+1}, , skr_{t.r})arrow \mathrm{I}\mathrm{R}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{d}(skb_{t.r})$

5. 工 RUserRef は,時間 ,タ $skr_{t.r}$ に対して, 時間

アルゴリズムである.

リフレッシュデのユーザの秘密鍵

$t$

$t$

,

とベースからの鍵リフレッシュデー$sk_{t.r}$

リフレッシュ $r+1$ のユーザ秘密鍵 $sk_{t+1.0}$ を出力する確率的多項式時法
である,$sk_{t.r+1}arrow \mathrm{K}\mathrm{I}\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{U}\mathrm{p}\mathrm{d}(sk_{t.r}, skr_{t.r})$

6. IREnc は, ユーザの公開鍵 $P$, 期間率的多項式時間アルゴリズム

7. IRDec は, 暗号文$c$, 期間 ,$t$$t_{s}$

平文 $m\in\{0,1\}^{k}$ に対して, 暗号文 $c\in\{0,1\}^{*}$ を出力する確である.

$carrow \mathrm{I}\mathrm{R}\mathrm{E}_{1}\mathrm{c}(P,t, m)$

リフレッシュ

る確率的多項式時間アルゴリズム$r$のユーザの秘密鍵 skt.r に対して,
である.

$m\in\{0, [perp]\}^{*}$を出力す$marrow \mathrm{I}\mathrm{R}\mathrm{D}\mathrm{e}\mathrm{c}(sk_{t}^{\wedge}., {}_{T}\mathrm{C})$Intrusion-resilient 暗号の安全性の定義は, 他の鍵進化暗号の定義とほぼ同様に与えられる.

つまり, 攻が与えられ, 適応的に対応する平文や鍵が入手でき撃者には復号オラクルと馬跳ラクルる, 鍵田ラクルでは, ユーザ秘密鍵, ベース鍵, 更新データ, リフレッシュデータのすべてにアクセスできるので, 期間 , リフレッシュ H こ加えてオラクル情報 (ユーザ秘密鍵, ベース鍵, 更新データ , リ
フレッシュデータ r) も記述する. 鍵オラクルーの質問は,暗号での鍵保管条件と照らし合わせて以下を仮定する,$(O_{\mathrm{I}\mathrm{R}\sec})$$(O_{\mathrm{I}\mathrm{R}\mathrm{D}\mathrm{e}\mathrm{c}})$$t$$\mathrm{s}\mathrm{k}$$\mathrm{b}\mathrm{k}$$\mathrm{u}$$\mathrm{I}\mathrm{r}1\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{s}^{1}\mathrm{i}\mathrm{o}\mathrm{n}- \mathrm{e}.\mathrm{e}\mathrm{s}’ \mathrm{i}1\mathrm{i}\mathrm{e}\mathrm{r}1\mathrm{t}$鍵オラクルの質問順序を質問した後に($t’>t$ ある ‘は $t’=t$ かつ $r’>r$ ) を質問しない (ユーザ秘密鍵の更新 (リフレッシュ) 後, 更新 (リフレッシュ) 前のユーザ秘密鍵は消去).

$\theta(\mathrm{s}\mathrm{k}, t’.r’)$$(\mathrm{s}\mathrm{k}, t.r)$を質問した後に( $t>t$ あるいは $=t$ かつ $r’>r$ ) を質問しない (ベース鍵更新 (リフレッシュ) 後, 更新 (リフレッシュ) 前のベース鍵は消玄).

$\theta(\mathrm{b}\mathrm{k}, t’.r’)$$\theta(\mathrm{r}, t’.r’)$

タ送信後,

$f,$

$(\mathrm{b}\mathrm{k}, t,r)$を質問した後に$(\mathrm{b}\mathrm{k}, t.r)$

け $>t$ あるいは $t^{J}=t$ かつ$r^{J}\geq r$) を質問しない (リフレッシュデー

リフレッシュ前のベース鍵は消去).

を質問した後にを質問しない (更新データ送信後 更新前のベース鍵は消去).
また鍵オラクルへの質問により, 明らかにユーザ秘密鍵が露呈する場合がある. 例えば, ユーザ秘密鍵 $sk_{t.r-1}$ とリフレッシュデータ $skr_{t.r-1}$ を入手すれば明らかに $sh_{T}$. は計算できる, このような質問に$<>(\mathrm{u}, d)$$(\mathrm{b}\mathrm{k}, t.r)(t’\geq t)$$sk_{t.r}$

より鍵が露呈することが自明な揚合を以下に記述する.
鍵露呈質問

Que を

$O_{\mathrm{I}\mathrm{R}\mathrm{S}\mathrm{e}\mathrm{c}}$への質問の集合とする. このとき$\bullet(\mathrm{s}\mathrm{k}, t.r)\in Que$$\bullet$$\bullet$$sk_{t.r}$が露呈する自明な質問は以下で定義される,.

$r>1$ のとき $(\mathrm{r}, t.(r-1))\in Que$ かっ$sk_{t.(r-1)}^{\wedge}$は鍵露呈.

$r=1$ のとき $(\mathrm{u}, t-1)\in Que$ かっ $sk_{(t-1).R}$ が鍵露呈.

123$\bullet$$r<R$ のとき $(\mathrm{r}, t.r)\in Que$ , かつ $sk_{t.r+1}$ は鍵露呈.

定義 6IntrlXSion-resilient 暗号 (IRKG, IRUserUpd, IRBaseUpd, IRUserRef, IRBaseRef,
IREnc, IRDec) に対して, アルゴリズム $A$ は 3 つのオラクルが与えられる.
復号オラクル: 任意の暗号文ど期間 の入力に対し, 期間 , リフレッシュ のユーザ秘密鍵での$(\mathrm{I}\mathrm{R}-\mathrm{I}\mathrm{N}\mathrm{D}-\mathrm{C}\mathrm{C}\mathrm{A})$

$t$

$t$

$O_{\mathrm{I}\mathrm{R}\mathrm{D}\mathrm{e}\mathrm{c}}$$\mathrm{o}$$r$

復号結果を出力する.
鍵オラクル OI お。 : 任意の期間 , リフレッシュ , オラクル情報 (ユーザ秘密鍵 $sk$, ベース鍵 $bk$, 更新
データ , リフレッシュデータ ) の入力に対し, それぞれ対応するユーザ秘密鍵, ベース鍵, 更新データ,
リフレッシュデータを出力する.
の入力に対し, そのどちらかの暗号文: 長さの等しい 2 つの平文 $m0$ とチャレンジオラクル$r$$t$$\circ$

$c$

$r$

$u$

$m_{1}$$O_{\mathrm{L}\mathrm{R}}$$\mathrm{o}$$c^{*}=\mathrm{I}\mathrm{R}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{c}(^{l}P, t, mb)(b=0,1)$を出力する,

初期設定 : 鍵生成アルゴリズム IRKG を実行させて, ( $P$, sk 煽,
攻撃 :

$A$

$sk_{0}$) を出力させ,$A$に $P$ を入力する.

は, 復号オラクル OI ゆ e。と, 鍵オラクル OI お e。チャレンジオラクル O よに適応的に質問を繰り返しその回答を入手する. 但し, 以下の制限事項をまもる.
には一度しか質問しない.
には質問しない,をの出力の入力 tゝと任意のリフレッシュ l こ対して, $sk_{t*.r}$ の鍵露呈質問をしない.
$\circ O_{\mathrm{L}\mathrm{R}}$$c^{*}$$\circ O_{\mathrm{I}A}$$O_{\mathrm{I}\mathrm{R}\mathrm{D}\mathrm{e}\mathrm{c}}$$r$$\circ O_{\mathrm{I}B}$$\circ$

出力 :OIRS。。に対する質問は順序を遵守.
$A$は, $b’=\{0,1\}$ を出力し, $b=b’$ であれば $A$ は攻撃に成功したとする,

Intrusion-resihent 暗号が適応的選択暗号文攻撃に対して識別不可能性を満たす (IND-IR-CCA) とは, 上記で定義された任意の多項式時間アルゴリズム の成功確率がセキュリティパラメータに対して無視でき$A$るぐらい小さいことをいう.

3.4

残される課題Intrusion-resilient 暗号において, 現在残される課題について述べる. 鍵進化暗号系の効率は,のオーダで計る. 表は, 既存の Forward secure 暗号と Intrusion resilient 暗号の効率を表す.
鍵更新期闇
本章では,

$T$

124
Fbrward secure 暗号には, 多項式時間オーダで可能な効率の良い方法があるのに対し, Intrusionresitlient 暗号には存在しない. このため, 効率的かつ安全な Intrusion-resitlient 暗号の構築は残る課題と
表より,

いえる.

4

–

ブロードキャスト暗号
本章では, ブロードキャスト暗号の概念と公開鍵ブロードキャスト暗号について述べる,

4.1

ブロードキャスト暗号の枠組み

ブロードキャスト暗号の基本的な仕組みについて述べる. システム内の全ユーザの集合を , 復号を許可とする. センターは, メッセージ $rn$ をしない n– . の集合を , それぞれのユーザ数を $|N|=n,$に属するユーザ (revoked receiver) が結に属するユーザ (privileged receiver) が正しく復号でき,
託しても復号できないように配信するために, 以下の手順を行う.
$\Lambda^{t}’$$\theta^{*}$$|\mathcal{R}|=r$$\mathcal{R}$$\prime R$$N\backslash \mathcal{R}$Initialization センターは各ユーザ$\bullet$Covering$\bullet$$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\dot{|}\mathrm{t}\mathrm{h}\mathrm{n}\rceil$に分割し, 各集合$u$に復号に必要な秘密鍵 $SK_{u}$ を配布する.

センターは privilcgcd rcccivcrs からなる集合を独立な部分集合,$S_{i_{j}}$に対応する秘密鍵$\langle$$\{\mathrm{S}_{\acute{i}_{j}}\},$$Ks_{i_{j}}$$N\backslash \mathcal{R}=\cup S_{\dot{\mathrm{z}}_{j}}$を用いて, セッション鍵 $K$ を暗号化し,$\{E1(Ks_{i_{j}},$ $K)\}$, E2 $(K,$$M)\rangle$

を全ユーザに送信する. ここで, $E_{i}(K, M)(\mathrm{i}=1,2)$ は鍵 $K$ による $M$ の暗号化を意味し, $\{E(Ks_{i_{j}}, K)\}$のサイズが transmission rate を決定する.

Decryption algorithm$\bullet$

鍵$Ks_{i_{j}}$に含まれる任意のユーザを導出し, $M$ を復号する.
$N\backslash \mathcal{R}$

$u$

は,

$SK_{u}$より自分のカバー集合 8 らの秘密

なお, カバー集合全体を $S=\{Si\}$ と表す. (秘密鍵に基づく) ブロードキャスト暗号のスキームは,trans-

mission rate, ユーザの秘密鍵サイズ, ユーザの subset 鍵の導出にかかる計算量の観点で評価する.

なお,

公開鍵に基づく場合, これに加えて公開鍵のサイズでも評価する、

4.2

既存方法

既存のブロードキャスト暗号は, ユーザを完全二分木の葉に配置し, 完全木の各ノードに秘密鍵を設定
し, 各ユーザが自分を含む全ての部分集合に対応する秘密鍵が導出できるように, ノードの秘密鍵を配布する.

言うまでもなく, ユーザに配布する鍵の方法は, 正規ユーザのカバーリングに依存する. これまで最もよ , 利用される方法は, Complete Sub も法法) [6] である.
法) と Subset Differenoe 法 (は, 正規ユーザのみを葉にもつ最大部分完全 2 分木により正規ユーザをカバーする 4 この結果, 正規ユーザ
は自分をカバーする任意の部分完全 2 分木の頂点に対応する秘密鍵を保持すれば, どのようなユーザが削除されても任意の暗号文を復号できる. つまり, 各ユーザは自分が配置された葉から根までの経路上の節点に対応する鍵を秘密鍵として保持すれば復号可能となる,$\langle$$\mathrm{r}\mathrm{e}\mathrm{e}$法($\mathrm{C}\mathrm{S}$$\mathrm{S}\mathrm{D}$$\mathrm{C}\mathrm{S}$125
表 2: 既存方法の性能

transmission rate$r \log\frac{N}{r}$$2r-1$$(2r-1)|C_{\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}}|\dagger$$r \log\frac{N}{r}$$\mathrm{n}-\psi^{\underline{\theta}}\sigma.)ffi^{\backslash }ffi^{4}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$O(\log N)$$O(^{\underline{1}}\log^{2} N)$$O(|SK_{\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}}|\log^{N})\dagger$$O(\log N)$$2N-1$

Nlog $N$$N$ $\log$ $N$$2N-1$$\log$ $N$$O(2N)$$O(2N)$$\log$ $N$––$O(1)$$O(1)$$|\mathrm{S}|$$\mathrm{z}-\theta^{\underline{\mathrm{p}}}\mathrm{g}$$\gamma_{-}\sim$$9$$\mathit{0}*\nearrow\backslash ^{\backslash }-\backslash \ovalbox{\tt\small REJECT}^{\mathrm{A}_{\mathrm{J}}}\subset$$J,\backslash arrow 7\ae\ovalbox{\tt\small REJECT}\theta.\mathit{4}$$\dagger_{\mathrm{I}}|C\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}|,$$\grave{\grave{x}}$は階層的$|SK\mathrm{H}\ovalbox{\tt\small REJECT} \mathrm{B}\mathrm{E}\mathrm{I}$$\mathrm{I}\mathrm{D}$

ベース暗号の暗号文のサイズとノード鍵のサイズである.

法の正規ユーザの隣接するカバリングを一つに統合し, ヘッダ数を抑える方法である. つまり, 正規ユーザは二つの部分完全 2 分木の差集合で覆われることになる, つまり, 二を根とすの祖先) とするとき, v。を根とする部分完全 2 分木の葉から
(
は
と
つの飾点を
に
る部分完全 2 分本の葉を除いたものを一つの部分集合 S 峨 とし, 正規ユーザはこの差集合
一方,$\mathrm{S}\mathrm{D}$法は直感的には,$v^{a}$$v^{b}$$\mathrm{C}\mathrm{S}$$v^{b}$$v^{\alpha}$$v_{b}$$S_{v}\circ-S_{v^{b}}$$v^{b}$

よってカバーされる. なお二つの箇点のうち祖先である
node と呼ぶ. この結果, 正規ユーザ は二つの頂点情報$v^{a}$$u$

もつ必要がある. なお$u$から root までの path を禽,を primary root, 子孫であるを secondary$v^{b}$

から一意的に導ける秘密情報 Kv。融をと記述にぶら下がる兄弟 node の集合を

$v^{a}$と$v^{b}$$\{v^{\rho_{u}}\}$$\rho_{u}$するとき,$S_{v^{a},v^{b}}\ni u$$\prime \mathit{0}_{u}\ni v^{a}$$\Leftrightarrow$$\{v^{\rho_{u}}\}$.

$v_{a}$$v^{b}$の祖先を設定し, 鍵生成関数
に対して秘密鍵を生成する.
に対応する秘密鍵
を primary root とする全ての差集合になる. そこでいてのある元が$\mathrm{S}\mathrm{D}$法では primary root$v^{a}$$SK_{v_{}^{a}v^{a}}$$\mathrm{B}\mathrm{E}-\mathrm{K}\mathrm{D}\mathrm{e}\mathrm{r}$を用$K_{v^{a}.v^{b}}$$S_{v^{a},v^{b}}$$\mathrm{B}\mathrm{E}-\mathrm{K}\mathrm{D}\mathrm{e}\mathrm{r}(v^{a}, v^{b}, SK_{v^{a},v}, {}_{b}PK)=(SK_{v^{a}.v^{b}0}, SK_{\tau \mathit{4}^{a}.v^{b}1}, K_{v^{a}.v^{b}})$( $b=a$ の場合も含む),の子孫のノードの鍵との子供のノード$PK$ の入力に対して,primary node$v^{a},$$v^{b}$$v^{a}$$v^{b}0$$v^{b}$

鍵$K_{v^{a},v^{b}}$この結果,の path$v^{b}1$$v^{b}$$SK_{v^{\mathrm{Q}},v^{b}0}$の秘密鍵$SK_{v^{a},v^{b}}$, 及び公開鍵と $SK_{v^{a}.v^{b}1}$ 及び差集合 5S。, 一のを出力する.

$S_{v^{a},v^{b}}\ni u$が$\text{自^{}J}\mathrm{A}$をカバーするすべての$\text{部_{}\mathrm{J}}’\#\text{集_{}\mathrm{D}}^{\mathrm{A}}$の鍵を ’\pi -するには,$\text{復}$$S_{v^{\text{。}},v^{b}}$\rho 。上の任意の node を primary node とする差集合の鍵が生成できるとよ .
$1_{\sqrt}\mathrm{a}$$u$から root まで

つまり,$\rho_{u}$の任意のと記述するとき,との path \rho 5, 一にぶら下がる兄弟 node の集合を
llode . とを秘密鍵として保持すればよ . このとき, 各ユーザが保管を secondary node とする node 鍵$v^{o}$$\{v^{\rho_{u,v^{\Omega}}}\}\ni\forall v^{b}$$\{v^{\rho_{u,v^{\Omega}}}.\}$$u$$\mathrm{V}^{\mathrm{a}}$$\{K_{v^{a}.v^{b}}\}$

なお実際にユーザがカバーされる可能性のある集合はこの鍵生成関数の存在がデータの削減に大きい影響を与える.

する鍵の大きさは,り,$o(\log^{2}(N))$

各方法の性能を表 2 に示す.

となる.

$O(N\grave{)}$

よ

128
4.3

公開鍵ブロードキャスト暗号法,
ブロードキャスト暗号に公開鍵を導入する際の問題点は, 公開鍵の大きさである. 表 2 により,$S$に含まれる集合毎に公開鍵を設定するので, $2N-1$ , Nlog $N$法を単純に公開鍵暗号で構成する場合,
法の場合, ユーザの保管する秘密鍵量とユーザあたの公開鍵が必要になる. 一方, 秘密鍵に関しては,$\mathrm{C}\mathrm{S}$$\mathrm{S}\mathrm{D}$$\mathrm{C}\mathrm{S}$りのカバー集合の個数が一致するので, 公開鍵に対応する秘密鍵をユーザが保管するとよい.

しかし,

SD

法の揚合, ユーザあたりのカバー集合の個数が $O(2N)$ であるのに対し, 秘密鍵量を $\log^{2}N$ と抑えているため, 秘密鍵導出関数も構成する必要がある, 公開鍵 CS 法に関しては,$\mathrm{I}\mathrm{D}$

ベース暗号を用いることで,ユーザを配置する完全 2 分木の各ノードに対してノード名を公開鍵とする秘密鍵を対応させることで, 公法に関しては, 鍵導出関数を構成する
開鍵サイズをから $O(1)$ に減らすことができる. 一方,$‘ \mathit{2}N-1$$\mathrm{S}\mathrm{D}$

ベース暗号を単純に適用することはできない.
, 公開鍵量は $O(1)$Dodis ら [2] は, 階層的 ベース暗号の概念を利用し, ユーザの鍵保管量はの公開鍵暗号に基づく法を実現した 4 方法は非常にシンプルである.
法を公開鍵暗号で実現する最大のポイントは, BE-KDer をどのように設定するかということである. そこで階層的ベース暗号を適で構成する, ここで} Sva,v。を用する多分木を法の primary node
毎の差集合, すなわち便宜上,のルートに設定し, そのノード鍵 Kv。, がを設定する. つまりを primary node とす
必要があり,$\mathrm{I}\mathrm{D}$$O(\mathrm{l}^{\iota}\mathrm{o}\mathrm{g}^{\mathit{2}}N)$$\mathrm{I}\mathrm{D}$$\mathrm{S}\mathrm{D}$$\mathrm{S}\mathrm{D}$$\mathrm{I}\mathrm{D}$$v^{a}$$\mathrm{S}\mathrm{D}$$\{S_{v^{a},v^{b}}\}$$v^{a}$$\{S_{v^{a},v^{b}}\}$

る差集合$\bullet$$\iota$$S_{v^{a},v^{b}}$ノード鍵の鍵を生成するには$K_{v^{a},v^{b}}$

差集合の鍵

の生成

$SK_{v^{a},v^{b}}$の生成の二つのステップが必要である. これを以下のように階層的して生成する.

$v^{a}$

を差集合の鍵を階層的$v^{b}$$\mathrm{I}\mathrm{D}$

ベース暗号の鍵導出関数を再帰的に利用の親ノードとし $v^{b}=v^{a}v_{t+1}$ とする. 図はユーザを配置した二分木を表し, 図は$\mathrm{I}\mathrm{D}$

ベース暗号で導出するための多分木である.

$SK_{v^{a},v}b$,$K_{?J^{a}v^{b}}$$v^{a},$$vt+1,$ $SK_{v^{\text{。}},v^{a)}}$$arrow$$\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(PK,$$arrow$$\mathrm{H}\mathrm{I}\mathrm{B}\mathrm{E}-\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(PK, v^{b}, 2, SK_{v^{a},v}b)$$\ovalbox{\tt\small REJECT} \mathrm{b}\mathrm{g}N$

図 1: User Troe

法は階層的ベース暗号の概念のみを適用するため, 効率的な階層的ベース暗号が存在すれば, SD
法と同じ効率で実現できる. しかし, 現存の階層的ベース暗号 [3] は, HIBE-KDer, HIBE-hc, HIBE-Dec,
暗号文, ユーザ (ノード鍵) の大きさが, ユーザ数 $N$ の場合, それぞれ $O(1),$ $O(\log N),$ $O(\log N),$ $O(\log N)$ ,$O(\log N)$ となり,
法よりも効率が落ちる.
$\mathrm{D}\mathrm{F}$$\mathrm{I}\mathrm{D}$$\mathrm{I}\mathrm{D}$$\mathrm{I}\mathrm{D}$$\mathrm{C}\mathrm{S}$127$\ovalbox{\tt\small REJECT} 1\circ \mathrm{g}N$

図 2: Key Derivation Tree

参考文献
[1] R. Canetti, S. Halevi, and J. Katz. “A forward-secure public-key encryption scheme.” Advances in
Eurocrypt 2003, Lecture Notes in Computer Science, 2656, Springer-Verlag, 2003.
Cryptology–[2] Y. Dodis and N. Fazio: “Public Key Broadcast Encryption for Stateless fficeivers”, prvceeding of, LNCS 2696, Springer-Verlag, pp.61-80, 2002.
$ACMDRM’ \mathit{0}\mathit{2}$[3] C. Gentry and A. Silverberg: “Hierarchical ID-Based Cryptography” Advances in CryptoloqyAsiacrypt 2002, LNCS $2\mathrm{S}01(2002)$ , Springer-Verlag, 548-566.
”
Public-Key Encryption”,[4] Y. Dodis, M. Franklin, . Katz, A. Miyaji and M. Yu ,RSA-CT 2003, Lecture Notes in Computer Science, 2612(2003), Springer-Verlag, 19-32.
$\mathrm{I}\mathrm{n}\mathrm{t}\mathrm{r}\backslash \mathrm{l}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}- \mathrm{R}P,\mathrm{S}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{t}$$.\mathrm{I}$$\mathrm{l}\mathrm{n}\mathrm{g}$[5] Y. Dodis, M. Franklin, J. Katz, A. Miyaji and M. Yung, “Generic construction for Intrusion-resilient
Cryptographers’ Track 2004, LNCS 2964(2004), Springer-Verlag,
public-key encryption.” $RSA$–

81-98.
[6] D. Naor, M. Naor and J. Lotspiech: “Revocation and Tracing Scheme for Stateless Receivers” , Ad.
vances Cryptology-CRYPTO 2001, LNCS 2139, Springer-Verlag,$\mathrm{p}\mathrm{p}.41-62,2001$$\iota n$[7] J. H. Silverm an, The Arithmetic of Elliptic Curves, GTM106, Springer-Verlag, New York, 1986.