PSEC-KEM 自己評価書
1

まえがき
本資料では、鍵共有を目的とする公開鍵暗号方式（暗号スキーム）「PSEC-KEM」の安全性および性能に関する自己評価について述べる。

2

設計方針および理論・技術

PSEC-KEM は、楕円 ElGamal 暗号関数（基本暗号プリミティブ）を [1] における変換方式で高い安全性を持つスキームに変換した（秘匿目的）暗号方式（PSEC-2 と呼んでいたスキーム）を鍵共有方式（Key Encapsulation Mechanism）に改良した方式 [4] （PSECKEM と呼ばれているもの）である。
PSEC-KEM は、実用上様々な特長を持つ楕円曲線暗号関数（楕円 ElGamal 暗号関数）の利点を引き継ぐと共に、最も高いレベルの安全性（適応的選択暗号文攻撃に対して強秘匿）をもつことが証明された暗号方式である。以下、安全性、性能についての概要を示す。

2.1

安全性の概要

PSEC-KEM は、楕円曲線上の Die-Hellman 計算 (CDH) 仮定とランダムオラクルモ
デルの下で、適応的選択暗号文攻撃に対して強秘匿である。
楕円曲線上の実用的かつ最強の意味の安全性の証明のついた他の公開鍵暗号（鍵共有／秘匿）としては、楕円 Cramer-Shoup 暗号や ECIES が知られている。楕円 Cramer-Shoup
暗号は、ランダム関数に対する仮定が現実的な汎用一方向性ハッシュ関数である点で優れているが、整数論的な仮定では（PSEC-KEM で仮定する CDH 仮定よりも強い仮定である）楕円 Die-Hellman 決定 (DDH) 仮定に基づいている。一方、 PSEC-KEM は、理想的なランダム関数（ランダムオラクルモデル）に基づいているものの、整数論的な仮定では基本的な楕円曲線上の Die-Hellman 計算 (CDH) 仮定に基づいている点で楕円Cramer-Shoup 暗号よりも優れている。また、 ECIES は、ランダムオラクルモデルの下で、整数論的な仮定が楕円曲線上の Gap-Die-Hellman (GDH) 仮定（CDH 仮定よりも強い仮定である）である。（ECIES は、ランダムオラクルモデルを用いない証明も可能であるが、その代わりにオラクルハッシュという非常に特殊な仮定が必要となる。他との比較のためには、ランダムオラクルモデルによる証明を用いる方が適切である。）

1

表 1: 安全性の比較
方式

PSEC-KEM
楕円 Cramer-ShoupECIES
楕円 ElGamal

安全性

整数論的ランダム関数（最強の意味で）仮定

仮定

安全性証明つき

楕円 CDH

真にランダム楕円 GDH

真にランダム

楕円 DDH

安全性証明つき
安全性証明つき

0

攻撃可

UOWHF

0

帰着の効率

*****0（注： UOWHF は、汎用一方向性ハッシュ関数を意味する。また、帰着の効率の欄で** は、ほぼ optimal であること、 * はそれに比べて効率が悪いことを意味する。）
2.2

性能の概要

PSEC-KEM の性能を他の代表的な方式と比べる。鍵サイズ、暗号文サイズでは、楕円Cramer-Shoup が他に比べてかなり長くなるが、その他の方式はほぼ同等である。以下の表では、速度に関する比較を示す。各方式とも、ハッシュ関数の処理量は楕円曲線上の乗算演算の処理量に比べほぼ無視できるため、ここでは楕円乗算演算の回数のみで比較を行なう。
表 2: 処理量の比較
方式

暗号化

復号化

（乗算演算回数）（乗算演算回数）

252223 (43 )
1 (23 )
1PSEC-KEM
楕円 Cramer-ShoupECIES
楕円 ElGamal（注：3 を付けたものは、安全性証明上の理由で、復号処理において暗号文がベースポイントのつくる部分群に入っていることを検証する必要がある場合の演算回数である。 PSEC-KEM では、このような検証は必要ないが、 Cramer-Shoup, ECIES では必要となる場合がある。）

2

3

PSEC-KEM の安全性証明
本節では、 PSEC-KEM の安全性に関する結果（楕円曲線上の Die-Hellman 計算 (CDH)

仮定とランダムオラクルモデルの下で、 PSEC-KEM が適応的選択暗号文攻撃に対して強秘匿であること）を示す（[4] 参照）。

ここで、 MGF をランダムオラクルと考える。つまり、以下のような 2 つの独立なランダムオラクルを想定する。

G : BhLen ! BpLen+128+KeyLen ;H : B32+21qmLen ! BhLen :また、簡単のため、 EC で ECP2OSP(C1 ; qmLen) を、また EQ で ECP2OSP(Q; qmLen)を表すものとする。

A を、復号オラクル、ランダムオラクル G H にそれぞれ qD 回、 qG 回、 qH回の質問をし、アドバンテージが " で実行時間が t であるような(K; E ; D)定理 3.1,

PSEC-KEMに対する IND-CCA2 （適応的選択暗号文攻撃に対して強秘匿）における攻撃者とする。こ"tのとき、成功確率が 0 で実行時間が 0 の（qqK に関する）楕円Die-Hellman 問題の回答を含む ( H + D ) 個の値のリストを出力するようなアルゴリズムが存在して、+ 20128 ) 0 qD + qG :"0  2(1 + "20128) 0 (qG + 3qD )(1p2hLent0  t + qH 1 (T + O(1)) :ここでT は K に関する楕円曲線上の乗算2 回を行う計算時間である。

qq

注： Die-Hellman 問題の回答を含む ( H + D ) 個の値のリストを出力するようなアルゴリズムが存在すれば、そのアルゴリズムを用いて効率的に Die-Hellman 問題の回答を抽出することができる [3, 4] （Die-Hellman 問題の持つランダム帰着性の性質を用いる）。
以降の評価において、下記の補題をしばしば用いる。
補題 3.2 任意の事象 E, F and G に対して、以下が成立する。

8< Pr[E j F ^ G]
Pr[E ^ F j G]  :Pr[F j G]:3

定理 3.1 を以下のような 3 段階の手順で証明する。まず最初に、（計算的） Die-Hellman(CDH) 問題を破る問題を PSEC-KEM を IND-CCA2の意味で破る敵に帰着させるアルゴリズムを示す。その次に、この帰着における復号オラクルのシミュレーションが圧倒的確率で効率的に実行できることを示す。最後に、上で述べた復号オラクルシミュレーションを含めて帰着の全体の成功確率ならびに実行時間を評価する。
注：鍵配送機能（key encapsulation mechanism:KEM）における IND（つまり、強秘匿）の定義は、（公開鍵）暗号における INDの定義と若干違っている。この定義については、文献 [4] の 2.2 節を参照されたい。

3.1

帰着アルゴリズムA を PSEC-KEM (K; E ; D) の IND-CCA2攻撃者とする。 A は、時間 t 以内で、 Aは、復号オラクル、 G- オラクル、 H - オラクルにそれぞれ qD 回、 qG 回、 qH 回の質問を行ない、鍵 K が正しいものかランダムに選ばれたものかの判断を " 以上のアドバンテー
ジで行なう。帰着アルゴリズム B は以下のとおりである。
3.1.1

トップレベルの記述

1. B は、曲線 E 上の点 P 、 W を含む公開鍵 PK と別の点 C13 を与えられる。帰着B の目的は、 (P; W;C13 ) が与えられたとき以下を満足するような CDH 問題の回答
Q3 を含む値のリストを求めることである。 logP W = logC13 Q3 (= s).
2. B はランダムなビット b と二つのランダムなビット列 c32 2 BhLen と K 2 BkeyLenを生成する。 B は A にこの公開鍵と暗号文 c3 = (EC 3 ; c32 ) （ここで、 EC 3 =ECP2OSP(C13 ; qmLen)）ならびに K を入力として与え、実行させる。 B は、復号オラクルやランダムオラクル G, H への A からの質問に対する回答をシミュレーションする。これらシミュレーションの方法は下で述べる。

3. A は最終的に K に対する判断 b0 を出力する。 B は、 H への質問の（特に EQ の部分の）全リストを出力する（その中に正しいEQ3 が含まれていることが期待される）。

G、 H のシミュレーション
ランダムオラクルシミュレーションは、 G、 H の回答をシミュレーションするとともに

3.1.2

ランダムオラクル

その質問／回答をそれぞれ G-List、 H-List として以下のように管理する。それらの初期値

4

は空リストである。（同じ値が質問された場合は、このリストに従い同じ回答を返す。）

 H オラクルに対して、 EC 6= EC 3 であるような最初に聞かれた質問  = (EC; EQ)に対しては、シミュレータはランダムな値 H ( ) を回答し、その対 (;H ( )) が H-Listに追加される。 G オラクルに対して、最初に聞かれた質問 r に対しては、シミュ
レータはランダムな値 G(r) を回答し、その対 (r;G(r)) が G-List に追加される。
 H オラクルに対して、最初に聞かれた質問 3 = (EC j3 ; EQ) に対しては、シミュ
レータはランダムな値 H ( 3 ) を回答し、その対 ( 3 ; H ( 3 )) が H-List に追加される。次に、 r = c32 8 H ( 3 ) を求め、 GList にその値があるかどうかを探す。もし無ければ、 t = [G(r)]pLen+128 として t 2 BpLen+128 をランダムに定める。それ= OS2IP(t) mod p を計算し、 C13 = P を満足するかどうかを確を用いて、認する。もし満足すれば、 Q3 = W を計算する（これが、求めたい CDH 問題(P; W;C13 ) の回答であり、出力する）。もし、 EQ = ECP2OSP(Q3 ; qmLen) な
らば、 [G(r)]keyLen = K （b = 0 のとき）とするか、 [G(r )]keyLen をランダムに定める（b = 1 のとき）。この場合、 (EC 3 ;c32 ) は、正しい暗号文（暗号オラクルの正6 P のときは、 [G(r)]keyLen をランダムに定める。
しい出力）である。 C13 =3.1.3

復号オラクルのシミュレーションc = (EC; c2) に対して、シミュレータ DS は  = (EC; EQ)（EQ は任意）が質問であるような対 (;H ( )) 2 H-List を探す。もしそのような対がH-List にない場合、 \Reject" を返す。もしそのような対が H-List にある場合、 r = c2 8H () を計算し、 GList に r があるかどうかを調べる。もしなければ、 G の r への回答
G(r) をランダムに選び、 GList に追加する。次に、 t = [G(r)]pLen+128 として、 =OS2IP(t) mod p を計算し、 EC = ECP2OSP( P ) および EQ = ECP2OSP( W ) を満復号オラクルへの質問足するかどうかをチェックする。もしいずれかが満足されなければ、 \Reject" を返す。いずれも満足されたならば、

3.1.4

DS は、 [G(r)]keyLen を鍵 k として出力する。

補足

Q3 を発見したとき、それを出力して以降の処理を終了することもできるが、ここでの解析では、帰着処理を継続して行ない、最後に、 B は、その値を出力するか、 H への質問のリストを出力する。
上記のシミュレーション過程でシミュレーション環境下でのミュレーション環境下でのの分布は実環境でのの分布はの分布とは異なる。つまり、シf0; 1; : : : ;p 0 1g 上で一様であるが、実環境での5の分布は、t が BpLen+128 上で一様であるとき = OS2IP(t) mod p であり、一様分布から少しだけ偏っている。

C1 = C10 ならばかつそのときに限り EC = EC 0 であり、 Q = Q0 ならばかつそのときに限り EQ = EQ0 である。
ここで用いる楕円曲線上の点の符号化は全単射写像なので、

3.2

記法

まず最初に、星印 (3 ) のついた変数はすべて、暗号オラクルから出力された解読対象暗c号文 3 = (EC 3 ; c32 ) に関連するものである。それ以外の変数は、敵から復号オラクルに質問された暗号文に関連するものである。

 AskH は、 (EC 3 ; EQ3 ) が H に質問される事象を意味し、 AskG は、 r3 が G に質問される事象を意味する。

 GBad は、 r3 (= c32 8H (EC 3 ; EQ3 )) が G に質問され、かつ EC 3 6= ECP2OSP( P ),もしくは EC 3 = ECP2OSP( P ) であるが [G(r 3 )]keyLen =6 K （b = 0 のとき）であるような事象のことを意味する。ここで、 t3 = [G(r 3 )]pLen+128 、 = OS2IP(t3 ) modp である。ここで、 GBad ならば AskG であることに注意されたい。上で見たように、 GBad は、選択平文攻撃において、シミュレーションが失敗する唯一の事象である。

 Fail は、上記の復号オラクルシミュレータが qD 個の回答のうち少なくとも 1 個の間違った復号結果を返す事象である。

 Bad = GBad _ Fail.
 CBad = RBad _ EBad。ここで、{ EBad は、 EC = EC 3 となる事象;{ RBad は、 r = r3 となる事象;

 AskRE = AskR ^ AskE。ここで、{ AskR は、 r (= c2 8 H (EC; EQ)) が G に質問される事象;{ AskE は、 (EC; EQ) が H に質問される事象;

Fail という事象は、 DS が暗号文を不正としたにもかかわらず復号オラクルが正しい暗号文と判断する場合に限定されることに注意。実際、たときは、復号オラクルが必ず正しい暗号文とする。

6DS が暗号文を正しいものと判断し

3.3
3.3.1

復号オラクルシミュレーションの解析
安全性の命題c

EC 3 ; c32 ) を暗号オラクルから受け取るとき、復号オラ
6 c3 ）に対して復号オクルシミュレータ DS は、 qD 個の質問（暗号文 c = (EC; c2 ) c =ラクルと同じ回答を成功確率 "1 で、実行時間 t1 で出力することができる。ここで、
+ 20128 ) + qD ;"1  1 0 (qG + 3qD )(1p2hLen
t1  qH 1 (T + O(1));
であり、 T は P と W を計算する計算時間である。
補題 3.3 最大 1 個の暗号文 3 = (;,解析を始める前に、もう一度復号オラクルシミュレータの動作を確認しておこう。シミュc

レータは、暗号オラクルから暗号文 3 ならびにランダムオラクルシミュレータとのやりとc を復号する。もし、暗号文が敵により正しく作られていれば（つまり、 r が G に問い合わされ、 (EC; EQ)が H に問い合わされる）、シミュレーションは正しく復号できる。それ以外の場合には、\Reject" を出力するが、敵は、ランダムオラクル G、 H へ質問せずに正しい暗号文を作りの結果 G-List and H-List を受け取り、 (敵から受け取った）暗号文ることができるかもしれない。

3.3.2

成功確率

ここでの目標は、事象 Fail の生起確率を求めることである。

:CBad ^ AskRE を認めれば、シミュレーションは完全であり、 Fail の生起確率は 0 である。従って、その補事象を考える：

Pr[Fail] = Pr[Fail ^ CBad] + Pr[Fail ^ :CBad ^ :AskRE]:^ CBad] について考えよう。 CBad = RBad _ EBad であるが、= 3 , C1 = C13 (i.e.,
ここで RBad は決して起こらない。なぜなら、 r = r3 ならば
EC = EC 3 )、 Q = Q3 、 H (EC; EQ) = H (EC 3 ; EQ3 ) となる。従って、 c2 = c32 、
つまり c = (EC; c2 ) は c3 = (EC 3 ; c32 ) と等しい。そのような c は、復号オラクルへの質問としては許されない。よって、 CBad = EBad。そこで、 Pr[Fail ^ EBad] を評価しよ
6 c32 (i.e., r =6 r3 )、 OS2IP([G(r)]pLen+128 )  OS2IP([G(r3 )]pLen+128 )う。これは、 c2 =(mod p) であるような c = (EC 3 ; c2 ) が qD 個の質問に含まれている確率である。それぞ
まず、最初の項 Pr[Fail7

c がこの関係を満足する確率は、高々 1+2p0128 である。敵は、 qG 回の確認する（潜在的）機会と qD 回の復号オラクルへの質問の機会がある。従って、以上より
0128
Pr[Fail ^ EBad]  (qG + qD )(1 + 2 ) :p
次に、後の項、 Pr[Fail^:CBad^:AskRE]、の評価を行う。 CBad = EBad and AskRE =AskR ^ AskE なので、この項の値は、以下となる。
れのPr[Fail ^ :EBad ^ (:AskR _ :AskE)] Pr[Fail ^ :EBad ^ :AskR] + Pr[Fail ^ :EBad ^ AskR ^ :AskE]:
この前の項に対して、 r は G に質問されなく r3 から独立なので、 c が正しい（つま= OS2IP([G(r)]pLen+128 ) (mod p) かつ EC = ECP2OSP( P )) 確率は高々り、
0128
1+2である。敵は、 qD 回の質問を復号オラクルにする機会があるので、pq (1 + 20128) :p
この後の項、 Pr[Fail ^ :EBad ^ AskR ^ :AskE]、に対して、 r は G に質問されるが、(EC;EQ) は H に質問されず (EC 3 ; EQ3 ) から独立である。そこで、 r0 = c2 8H (EC;EQ)
1 + 1+20128 である。
が r と等しいか G(r 0 ) が C1 と整合が取れている確率は、高々 2hLenp
敵は qD 回の質問を復号オラクルにする機会があるので、
Pr[Fail ^ :EBad ^ :AskR]  D

1 + 1 + 20128 ):Pr[Fail ^ :EBad ^ :AskR]  qD ( hLen
2p
以上より、

0128

Pr[Fail]  (qG + 3qD )(1 + 2p) + qD :2hLen

このシミュレーションの実行時間を評価する。ここでは、復号オラクルへの質問暗号文

c = (EC; c2), それに対応する H-List に含まれる (EC;EQ) の値ならびに対応する G-Listの r の値から得られる のすべての値に対して、 P and W の計算を行う。従って、このシミュレーションの実行時間は高々qH 1 (T + O(1));
であり、T は P と W の実行時間である。

83.4

帰着の成功確率ここでは、この方式に対する IND-CCA2の敵のアドバンテージに関して帰着の成功確率

P; W;C13 ) を受け取って、 Q3 を含を求める。帰着の目標は、楕円曲線のパラメータと (qむ H からなる値のリストを出力することである。つまり、この帰着の成功確率は、事象AskH が起こる確率により得られる。
そこでまず、事象 AskH を事象 Bad に関して分解して考える。

Pr[AskH] = Pr[AskH ^ Bad] + Pr[AskH ^ :Bad]:
最初に、前の項を評価する。

Pr[AskH ^ Bad] = Pr[Bad] 0 Pr[:AskH ^ Bad] Pr[Bad] 0 Pr[:AskH ^ GBad] 0 Pr[:AskH ^ Fail] Pr[Bad] 0 Pr[GBad j :AskH] 0 Pr[Fail] Pr[Bad] 0 Pr[AskG j :AskH] 0 Pr[Fail]+ 20128 ) 0 2qD + qG :
 Pr[Bad] 0 (qG + 3qD )(1p2hLen) + qD は、補題 3.3 より得られ、 Pr[GBad j :AskH] 2hLen
Pr[AskG j :AskH] は、事象 GBad が起こるならば必ず事象 AskG が起こることより得られる。 :AskH ならば、 H (EC 3 ; EQ3 ) は予測不可能であり、 r3 = c32 8 H (EC 3 ;EQ3 ) も+qD .
また予測不可能である。従って、 Pr[AskG j :AskH]  q2GhLen
ここで、 Pr[Fail] (qG +3qD )(1+2p0128

次に後の項を評価する。

Pr[AskH ^ :Bad] = Pr[:Bad] 1 Pr[AskH j :Bad]
 Pr[:Bad] 1 Pr[A = b ^ AskH j :Bad]
 Pr[:Bad] 1 (Pr[A = b j :Bad] 0 Pr[A = b ^ :AskH j :Bad]) ::AskH ならば、 H (EC 3 ; EQ3 ) は予測不可能であるため、 r3 = c32 8H (EC 3 ; EQ3 )も予測不可能であり、同様に b も予測不可能となる。このことは、 :Bad と独立な事象である。従って、 Pr[A = b ^ :AskH j :Bad]  Pr[A = b j :AskH ^ :Bad] = 1=2. シミュレーションにおける c3 = (EC 3 ; c32 ) の分布は、実環境での c3 の分布と若干異なっている
ここで、（(1 + 20128 ) 倍のバイアスがある）ため、"2(1 + 20128 )+ 1  Pr[A = b]  Pr[A = b j :Bad] 1 Pr[:Bad] + Pr[Bad]:29従って、



0128
+ 1 0 Pr[Bad] 0 Pr[:Bad] = "=(1 + 2 ) 0 Pr[Bad] :01282(1 + 2 ) 222
前の項と後の項の評価を合わせ、また Pr[Bad]  0 という事実を用いると、以下が得られ

Pr[AskH^:Bad] る。

3.5

Pr[AskH] "0128"+20 (qG + 3qD )(12(1 + 20128 )p) 0 2q D + q G :2hLen

帰着時間の評価

この帰着の実行時間のほぼすべては、復号オラクルのシミュレーション時間なので、帰着の全体の実行時間は、であり、

4t0 = t + qH 1 (T + O(1));

T は P と W の実行時間である。

実装評価
この章では、 PSEC-KEM を C 言語で実装した場合の速度およびメモリ使用量を示す。

使用したパラメータは、技術仕様書で示した推奨パラメータである。
測定環境は以下の通りである。

CPUMemory
OSIntel Pentium-III 600MHz
128 Mbytes
Microsoft Windows2000 SP2
コンパイラ Microsoft Visual Studio 6.0 Enterprise Edition
速度測定は、演算にかかった clock 数を測定することにより行なった。ランダムなデータを用いた 1000 回の平均をとっている。
実行速度は以下の通りである。
鍵生成
暗号化
復号化

5.64 ms
11.09 ms
10.97 ms

メモリ使用量は以下の通りである。
鍵生成
暗号化
復号化

7.30 Kbytes
2.64 Kbytes
2.39 Kbytes
10参考文献[1] Fujisaki, E. and Okamoto, T.: Secure Integration of Asymmetric and Symmetric
Encryption Schemes, Proc. of Crypto'99, Springer-Verlag, LNCS 1666, pp. 535{554 (1999).
[2] Bailey, D. V. and Paar, C.: Optimal Extension Fields for Fast Arithmetic inPublic-Key Algorithms, Proc. of Crypto'98, LNCS 1462, Springer-Verlag, pp.472485 (1998).
[3] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In
Eurocrypt'97, LNCS, Springer-Verlag, Berlin, 1997.
[4] V. Shoup. A Proposal for an ISO Standard for Public Key Encryption (v.2.0).
ISO/IEC JTC1/SC27, N2563, http://shoup.net/papers/, 2001 Sep.

11