ACE 暗号攻撃評価報告書

目次

1 はじめに
2 ACE 暗号の概要

3
3

3 公開鍵暗号の安全性
4 ACE 暗号のアルゴリズム概要

45

5 DiÆe-Hellman 問題
6 汎用一方向性ハッシュ関数
7 安全性解析77
72.1 仕様書の概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.2 知られている攻撃法 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.1 鍵生成 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.2 暗号化 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.3 復号化 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :7.1 安全性の証明 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :7.2 数論仮定 (DDH) の安全性 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

3
4

5
6
6

7
10

11

8 結論

2

1 はじめに
本報告では , Advanced Cryptographic Engine に含まれる公開鍵暗号方式に対する安全性評価を行う. 評価は数論仮定と関数仮定のもとで示された適応的選択暗号文攻撃に対する安全性証明の検証と , 用いられた数論仮定について推奨パラメータ長での安全性の評価の２点を行った. ２章で提案
暗号の概要, ３章では公開鍵暗号の安全性証明理論についての概略を述べ, ４章, 提案暗号アルゴ リ
ズムの紹介, ５, ６章, 数論仮定として用いられた DiÆe-Hellman 問題, および一方向性ハッシュ関数
についての簡単な説明, ７章で, 提案暗号方式の安全性の解析, 最後に８章で結論を述べる.

2 ACE 暗号の概要
Advanced Cryptographic Engine(以下 ACE) は公開鍵暗号方式だけでなく電子署名方式も実装しているソフトウェア・ルーチンライブラリである. 以後本報告の対象となる ACE に含まれる公開鍵暗号方式を ACE 暗号と呼ぶ. ACE 暗号は , 次に示す 3 つの仮定のもとで安全性の証明ができることを特徴としている.
(1) DiÆe-Hellman(DDH) 仮定.
(2) SHA-1 第 2 プレ イメージ衝突耐性.
(3) MARS 累積/カウンタ・モード の疑似ランダム性.
またランダムオラクルモデルを仮定した場合 (1) は計算量的 DiÆe-Hellman 仮定に置き換えることができる. ACE 暗号が達成している安全性について２章以降で説明する.

2.1

仕様書の概要仕様書は次のような構成になっている.
１章 はじめにACE 暗号の概略と仕様書の構成について述べられている.
２章 安全性の目標
公開鍵暗号方式の証明可能安全性についての解説. 公開鍵暗号の安全性証明理論, ACE 暗号の安全性を証明する上で前提とされている, DiÆe-Hellmann 問題, SHA-1 第 2 プレイメージ衝突
耐性, ブロック暗号 MARS の累積/カウンタ・モード 擬似ランダム性などについて述べられている.
３章 用語と表記法
４章 暗号方式
ACE 暗号のアルゴ リズムの詳細 (ハッシュ関数や対称暗号の仕様も含む), および ACE 暗号の安全性の解析, 証明が記述されている.
５章 ASN.1 鍵の構文
６章 パフォーマンス
４章で述べられている安全性の解析では , ACE 暗号についての安全性証明を , [5], [21] に述べられている基本となる暗号方式の解析方法などを引用しながら行っている. そこでは ACE 暗号の解読成功確率を , DDH の成功確率や, ハッシュ関数のプレイメージ探索成功確率, 擬似乱数生成器の出力と乱数との判別成功確率などを用いて評価しており, 攻撃ゲームを様々に変形しながら最終の評価式を導くという手法がとられている.

3

2.2

知られている攻撃法

現在のところ ACE 暗号に対して特化された攻撃は発表されていない.

3 公開鍵暗号の安全性
ACE 暗号の安全性を説明するために , まず一般に公開鍵暗号方式に対して構築されている安全性理論を紹介する.
公開鍵暗号への攻撃のタイプは , 暗号文のみから解読を試みる受動的攻撃と , 送信者に暗号文 (解読対象以外の) を送り復号結果を得ることが許され , そこで得た情報を利用して解読対象の暗号文を解読する能動的攻撃に分類される.
一方, 公開鍵暗号は通信内容の秘匿を目的に用いられるため, 通信内容の秘匿の度合いが重要になる. これを暗号の秘匿性と呼ぶ. さらに暗号文から平文の内容を知ることはできないが , 暗号文を操作することにより, 対応する平文の意図的な改ざんを行うことができる可能性がある. このような意
図的な改ざんが一切できないことを頑強性 (non-malleable 性) と呼ぶ. これら秘匿性と頑強性をまとめて強度と呼ぶ. 以上の 2 つの観点より, 公開鍵暗号の安全性を以下のように分類する.

 受動的攻撃 (passive attack){ 暗号文攻撃 (ciphertext-only attack) :暗号文だけを利用する攻撃.
{ 選択平文攻撃 (chosen-plaintext attack : CPA) ：任意の平文に対応する暗号文を，暗号化関数をオラクルとして用いることで得ることのできる状況下において，解読対象である暗号文を解読しようとする攻撃. (公開鍵暗号では暗号化鍵が公開されているため，常に実行可能) ．

 能動的攻撃 (active attack){ 非適応的選択暗号文攻撃 (non-adaptive chosen-ciphertext attack : CCA1) ：攻撃対象の暗号文が与えられる前の段階においてのみ，任意の暗号文 (攻撃対象を除く) に対する
平文を，復号化関数をオラクルとして用いる (decryption oracle) ことで得ることのできる状況下において，解読対象である暗号文を解読しようとする攻撃.

{ 適応的選択暗号文攻撃 (adaptive chosen-ciphertext attack : CCA2) ：ターゲットとなる
暗号文が与えられる前後に関わらず，任意の暗号文 (攻撃対象を除く) に対する平文を，復号化関数をオラクルとして用いる (decryption oracle) ことで得ることのできる状況下において，解読対象である暗号文を解読しようとする攻撃.

この定義から，CPA, CCA1, CCA2 の順でより強力な攻撃法であることが分かる．
さらに，強度の観点から次のように分類される．

 秘匿性{ 完全解読困難 : 一方向性 (one-way : OW) ：任意の暗号文の平文を完全に求めることが困難であること．

{ 部分解読困難 ： 暗号文から平文の部分情報を求めることが困難であること.
{ 強秘匿 (semantically secure / indistinguishable : IND) ：どのような部分情報も部分解
読困難なこと .

4 頑強性 (non-malleability : NM) ：暗号文 y = E (x) に対して，R(x; x1; x2 ; : : : ; xk ) となる関係 R と暗号文 yi = E (xi ) (1  i  k ) を作成することが困難であること (但し ，E は暗号化
関数) ．

f

gf

g

以上の定義から，公開鍵暗号の安全性として， 強度 - 攻撃法 の組み合わせを考える．例えば，NM-CCA2 は適応的選択暗号文攻撃に対して頑強であることを意味する．これらの安全性の定
B とは，ある公開鍵暗号が A であれば必ず B であることを意味
義間の関係を図 1 に示す. (Aする．A
B はその否定である.). ここで，特に重要な結果としては，IND-CCA2 と NM-CCA2の等価性が示されていることである．このことから，IND-CCA2 または NM-CCA2 である公開鍵暗号が最も安全な公開鍵暗号であると考えられている．これらに属し , かつ実用的である公開鍵暗号としては OAEP, EPOC 等が知られている.

!

6!



NM-CCA1
XXX
y

X
XX
 XX
X
?
?
 XXX
z

IND-CPA
IND-CCA1 
NM-CPA?
OW-CPA?
OW-CCA1-

NM-CCA2?6
IND-CCA2?
OW-CCA2

図 1: 公開鍵暗号の安全性の定義間の関係
後の考察のため, IND-CCA2 の概念をより詳しく説明する.
攻撃者は encryption oracle にメッセージ m0 , m1 を与え , encryption oracle はコイントスにより
b = 0 or 1 を選択, mb を暗号化したのち攻撃者に送り返す. 攻撃者がこの暗号文が m0 , m1 いずれの暗号文であるかを当てるゲームを考える. その際, 攻撃者は decryption oracle にターゲットである暗号文以外の任意の暗号文を復号してもらうことができる. しかも, それは問題となる暗号文を手にする前でも構わない. ある公開鍵暗号が IND-CCA2 であるとは , 任意の確率的多項式時間アルゴ
リズム (攻撃者) に対しても, このようなゲームにおいて攻撃者が 1/2 よりよい確率で正解しないことをいう.
暗号化関数が決定性の関数 (同じ平文に対して常に同じ暗号文を出力する) である場合にはこの概念は全く意味をなさない. IND-CCA2 は確率暗号に対しての概念である.
上記の定義をより正確に定式化することもできるがここでは省略する.

4 ACE 暗号のアルゴリズム概要
ACE 暗号は , 公開鍵暗号を用いて秘密鍵暗号である MARS 暗号の鍵共有を行い, 実際の平文の暗号化は , ブロック暗号 MARS を擬似乱数生成器として用い, 平文と MARS の出力との排他的論理和
を暗号文とするハイブリッド 方式を採用している. その際, MARS は累積/カウンタ・モード で用いられ , 同時に メッセージ認証も行う. また暗復号化の過程で用いられるハッシュ関数として SHA-1を用いて構成された関数も合わせて提案されている. 本報告では , 特に DiÆe-Hellman 判定問題との関連を中心に評価を行うため, ハッシュ関数, MARS の使用モード 等の詳細には触れず , ACE 暗号
を簡略化したものを評価対象とする.
4.1

鍵生成

入力: サイズ・パラメータ 1024 m  16; 384.
5

出力: 公開鍵 (P; q; g1 ; g2 j1 ; k2 ), 秘密鍵 (w; x; y; z1 ; z2 ).

1. jqj = 256 なる素数 q をランダムに生成する.
2. P  1 (mod q), jP j = m なる素数 P をランダムに生成する.
3. g1q  1 (mod P ), g1 2 ZP , g1 6= 1 なる整数 g1 をランダムに生成する.
4. w; x; y; z1 ; z2 2 Zq なる整数 w; x; y; z1 ; z2 をランダムに生成する.
5. 次の整数を計算する.

g2 = g1w ; c = g1x ; d = g1y ; h1 = g1z1 ; h2 = g1z2 :6. ハッシュ鍵 k1 ; k2 をランダムに選択する.
7. 公開鍵/秘密鍵のペア (P; q; g1 ; g2 ; c; d; h1 ; h2 ; k1 ; k2 ), (w; x; y; z1 ; z2 ) を出力して終了.
4.2

暗号化

入力: 平文 m, 公開鍵 (P; q; g1 ; g2 ; c; d; h1 ; h2 ; k1 ; k2 ).
出力: 暗号文 (s; u1 ; u2 ; v; e).

1. 128 ビット列 s を任意に生成する.
2. r 2 Zq なる r をランダムに生成する.
3. 暗号文のプリアンブル (u1 ; u2 ; v) を生成する.
3.1. u1 = g1r , u2 = g2r をそれぞれ計算する.
3.2. 160 ビットの出力を持つ汎用一方向性ハッシュ関数 H を用いて 0  < 2160 , =H (k1 ; s; u1 ; u2 ) なる整数 を計算する.
3.3. v = cr d r を計算する.
4. 対称暗号の鍵 k を計算する.
4.1. h~ 1 = hr1 , h~ 2 = hr2 をそれぞれ計算する.
4.2. 256 ビットの出力を持つ, 汎用一方向性ハッシュ関数 H 0 を用いて 0  k < 2256 ,k = H 0 (k2 ; s; u1 ; h~ 1 ; h~ 2 ) なる整数 k を生成する.
5. 鍵長が 256 ビットの対称暗号 C 及び鍵 k を用いて, e = Ck (m) を計算する.
6. 暗号文 (s; u1 ; u2 ; v; e) を出力して終了.
4.3

復号化

入力: 暗号文 (s; u1 ; u2 ; v; e), 公開鍵 (P; q; g1 ; g2 ; c; d; h1 ; h2 ; k1 ; k2 ), 秘密鍵 (w; x; y; z1 ; z2 ).
出力: 復号文 m.

1. 汎用一方向性ハッシュ関数 H を用いて = H (k1 ; s; u1 ; u2 ) なる整数 を計算する.
2. v 6= ux1 + y の場合, Reject を出力して終了.
3. 対称暗号の鍵を計算する.
3.1. h~ 1 = uz11 , h~ 2 = uz22 をそれぞれ計算する.
3.2. 汎用一方向性関数 H 0 を用いて 0  k < 2256 , k = H 0 (k2 ; s; u1 ; h~ 1 ; h~ 2 ) なる整数 k を生成する.
4. m = Ck (e) を計算する.
5. m を出力して終了.
6

5 DiÆe-Hellman 問題

G を素数位数 q の群とし g 2 G を生成元とする. このとき計算量的 DiÆe-Hellman(CDH) 問題とは g x と g y から g xy を計算する問題のことであり, 計算量的 DiÆe-Hellman 仮定とは計算量的DiÆe-Hellman 問題が計算量的に困難であるという仮定である.
与えられた g1 ; g2 ; u1 ; u2 2 G に対して , u1 = g1x ; u2 = g2x を満たす x が存在するか否かを判定する問題を決定性 DiÆe-Hellman 問題 (DDH) という. この問題が計算量的に困難であるという仮定を決定性 DiÆe-Hellman 仮定という.
これらの問題の困難性は , 任意の確率的多項式時間アルゴ リズムに対し , 問題に正解する確率が十分小さいという形で定式化することができるが , ここでは詳細には触れない.
DiÆe-Hellman 問題の持つ重要な性質として自己ランダム帰着性がある.
明らかに G 上の離散対数問題 (DL) が解ければ CDH と解くことができ, また CDH が解ければDDH を解くことができる. しかしながら現在のところ, DDH, CDH と DL との計算量的同値性は ,特殊な条件下での結果が若干知られているのみであり, 一般的には未解決である.

6 汎用一方向性ハッシュ関数
汎用一方向性ハッシュ関数は , Naor と Yung([17]) により導入された概念である. 鍵付きハッシュ関数 H が , 平文 x が選択され , さらにランダムな鍵 k 与えられた場合において, Hk (x) = Hk (y ) とな
るような y = x を求めることが難しいという条件を満たしてとき H を汎用一方向性関数と呼ぶ.
明らかに分かるように , ハッシュ関数に対する要求条件としては , 汎用一方向性ハッシュ関数の方が衝突困難ハッシュ関数よりも弱い.

67 安全性解析
ACE 暗号はいくつかの仮定のもとで安全性が証明できる暗号方式であり, 安全性の評価は (1) 安
全性証明の検証, (2) 安全性証明のために用いられた仮定についての安全性検討 の２点について行う必要がある. この章では安全性の証明を説明し , 次に数論仮定 (DDH) の安全性について考察する.
7.1

安全性の証明ACE 暗号は次の定理により安全性を保障する.
定理

7.1. 汎用一方向性ハッシュ関数と, 擬似ランダム性を持つ対称暗号の存在，および決定性 DiÆe-Hellman 問題 (DDH) の困難性を前提として, ACE 暗号は適応的選択暗号文攻撃に対して安全 (INDCCA2) である.
以下, 定理 7.1 の証明の概略を説明する．特に断ることなく前章までに用いた記号をそのまま用いる.
IND-CCA2 の定義で想定しているゲームにおいて，攻撃者の攻撃実行時間が高々t, decryption
oracle への質問回数が高々 , テストメッセージ m0 , m1 の長さの上限が l の場合の攻撃者の優位性(正解確率-1/2) をAdvEnc(t; ; l)と書く.

7同様に実行時間が高々 t の DDH に対する, 出力 0, 1 の統計テスト全体の集合を

AdvDDH(t) = max
fjPr[T (R) = 1] Pr[T (D) = 1]jg
T 2T

T とするとき(Pr[E ] は事象 E が生じる確率) とおく.
hash 関数 H に対し , 実行時間が高々 t の, 第 2 プレ イメージを見つけるアルゴ リズムを全て動かしたときの最大確率を

AdvH(t)とかく.
最後に擬似乱数を生成するアルゴ リズム C に対し , 実行時間が高々 t, C の l-bit の出力分布と, l-bit のランダムな系列の分布 l とを区別する全ての統計テストの集合を
とするとき

R

AdvC(t; l) = maxfjPr[T (Rl ) = 1] Pr[T (Pl ) = 1]jg

T

Pl

T 2T

とおく.
定理 7.1 は次の定理から導かれる：
定理

7.2. l0 を P のバイト長とするとき
AdvEnc(t; ; l)  AdvDDH(O(t)) +AdvH(O(t))(dl=64e + d(2dl0 =4e + 4)=16e) +AdvC(O(t); 65dl=1024e + 7)  2 +(2 + 3)=q + ( + 2)=2128 :ここで定義をする：

7.1. 暗号文が vaild とは, logg (u1) = logg (u2) であることをいう. そうでないとき invalid

定義
という

1

.

2

実行時間 t, 長さ高々 l のテストメッセージについて decryption oracle への高々  回の質問をする攻撃ゲームを考える. もともとのスキームに対する攻撃ゲームを G0 とし , S0 を攻撃者がゲーム
G0 の中で秘匿ビット b をあてる事象とする. (以下, 同様にゲーム Gi 内で秘匿ビットをあてる事象
を Si とおく)
このとき定義により, AdvEnc(t; ; l) = Pr[S0 ] 1=2 である. 定理の証明は攻撃ゲームを変形していきながらこの値の上限評価をしていくことで行われる.

jj

Game G1. スキームを次のように変形する: プライベート鍵を x1, x2, y1, y2, z11, z12, z21, z22, 公

開鍵を

c = g1x1 g2x2 ; d = g1y1 g2y2 ; h1 = g1z11 g2z12 ; h2 = g1z21 g2z22とし , さらに復号化において,uq1  uq2  1 (mod P ); ux1 1 +y1 ux2 2 +y2  v (mod P )を確認するステップを挿入する. 最後に対称暗号 (C ) の鍵の導出において,h~ 1 = uz111 uz212 ; h~ 2 = uz121 uz222
8とする. [5] と同様の議論 (攻撃者に公開されている情報から reject されない invalid な暗号文をつくるためには , あるいくつかの超平面の共通部分として与えられる曲線 (line) 上の点をあてなければな
らい...), および簡単な確率計算 (仕様書 Lemma 4.10.1) により

cf.

jPr[S1 ]が得られる.

Game

Pr[S0 ]j 

2

q

(1)

cf. x

G2 . [5] で用いられた議論と同様に ( [5] 4, Lemma 2, Claim 2, Case 3), encryption oracleの動きを次のように変形する:
encryption oracle がつくるターゲットの暗号文において u01 , u02 を (位数 q の) ランダムな値とす
00
る. また encryption oracle は v 0 = (u01 )x1 +y1 (u02 )x2 +y2 を計算する. このとき

jPr[S2 ]Pr[S1 ]j 

2

q

(2)

が成り立つ.

Game G3. G2 において攻撃者が decryption oracle に (s; u1; u2) 6= (s0; u01; u02) であって, = 0 なる暗号文を submit する事象を V2 とおく. G3 では (s0 ; u01 ; u02 ; 0 ) の計算を攻撃に先駆けて行うこと
として, V2 が生じた場合は攻撃を終了させることとする. このとき [21] と同様の議論により,

jPr[S3 ]Pr[S2 ]j  AdvH(O(t))d(2dl0 =4e + 4)=16e(3)が成り立つ.

Game G4. G4 ではさらに encryption oracle において h~ 01, h~ 02 を (位数 q の) ランダムな値とする.
[5] と同様の議論により, invalid な暗号文が reject されない確率は高々 1=q となり, これにより

jPr[S4]Pr[S3 ]j 

+1
q

(4)

が得られる.

Game G5. G5 では対称暗号の鍵をランダムなものに置き換える. このとき entoropy smoothing

theorem ([15], [12]), および h~ 01 , h~ 02 が少なくとも 2a , a = 256 + 2  127 個の元を持つ集合からランダムに選ばれていることから

jPr[S5 ]2
Pr[S4 ]j  1282(5)が得られる.

Game

G6 . decryption oracle に質問された暗号文のプ リアンブル (s; u1 ; u2 ; v) がターゲットの暗号文のプリアンブルと等しい場合には reject するよう decryption oracle を変更する. このとき次が示される：

jPr[S6 ]Pr[S5 ]j

 AdvC(O(t); 65dl=1024e + 7)
+AdvH(O(t))dl=64e + =2128 :(6)

Game G7. G6 の encryption oracle における擬似乱数生成アルゴ リズムの出力を乱数に置き換える. このときゲーム G7 はランダムな出力をあてるゲームとなり,

jPr[S7]j = 219(7)

であり, また

jPr[S7]

Pr[S6 ]j  AdvC(O(t); 65dl=1024e + 7)

(8)

がわかる.

(10) をまとめることで定理を証明する

これらのゲーム間における攻撃成功確率の差の評価 (2)ことができる.

以上の証明において, 考察の不足, 理論的ギャップ等は特に認められず , ACE 暗号の安全性証明には問題はないと考える.

7.2

数論仮定 (DDH) の安全性

現在のところ, DDH, CDH を解くためには離散対数問題 (DL) を解くことが必要であるため, ここでは推奨パラメータ長のうち最小のものについて DL を考える.
現在知られている有限体の乗法群における DL への攻撃アルゴ リズムは , 次の２種類に大別される：(1) 対象となっている部分群の位数のサイズに依存したもの (ACE 暗号では q のサイズに依存).
(2) 有限体の元の個数に依存したもの (ACE 暗号では P のサイズに依存).
(1) に属するものとしては Shanks, Pohlig-Hellman, Pollard のアルゴ リズムなどがあり, (2) としては指数計算法として, Adleman, Coppersmith, Gordon のアルゴ リズムなどが知られている.

Z有限素体の乗法群 p における離散対数計算法として , 現在比較的有効とされているアルゴ リズ
ムは Gordon のアルゴ リズム ([11]) で, これは素因数分解のために考案された数体ふるい法に基づいており, 一般数体ふるい法によるものと特殊数体ふるい法によるものに分けられる. 一般と特殊は pの性質の違いによる. この Gordon のアルゴ リズムは計算量評価に用いられる関数

Lp [a; b] = exp((b + o(1))(log p)a (log log p)1 a )を用いると "一般"の場合, Lp [1=3; 2:08008] であり, "特殊"では Lp [2=5; 1:00475] と評価されている(素因数分解に一般数体ふるい法を用いた場合, Lp[1=3; 1:901]). この評価からは漸近的に "一般"の方が高速に動くことがわかるが , 実は p が極めて巨大にならなければ "特殊"の方がやはり早いことが知られている.
攻撃アルゴ リズム (1) に属する代表的なものとして Pohlig-Hellman のアルゴ リズムがあるが , こ
れは p 1 の素因子が大きければ有効に働かない.

ACE 暗号で用いられている群は , P は 1024 ビット以上, q は 256 ビットとされている.
この群に対して , 上記攻撃法の適応を考えると , まず Pohlig-Hellman 法に対しては P 1 が大きな素因子として q を含むので適応は難しいと考えられる.
次に Gordon 法を適応した場合を考えると , "特殊"版の条件 (ここでは詳細な記述は避けるが , 大雑把には , 整数係数多項式 f であって, P において解を持ち, かつ係数が適当に小さくなるものが存在するような素数 P のことを "特殊"といっている) に当てはまらない P を選択しさえすれば , "一般"版を用いることになり, その場合, 現在の計算機能力では困難とされる 1024 ビット RSA タイ
プ合成数の素因数分解と同等以上の強度を持つことがわかる.
ACE 暗号の仕様書には上記 Gordon のアルゴ リズムなどに対して耐性を持つ素数 (鍵) の生成について特に記述がなく, 注意が必要と思われるが , 素数サイズの設定には全く問題はないと考える.

Z

10

8 結論
本報告では ACE 暗号に対して以下の観点から安全性の評価を行った.

(1) 汎用一方向性ハッシュ関数と, 擬似ランダム性を持つ擬似乱数生成器の存在，および決定性 DiÆeHellman 問題の困難性を前提としての, 適応的選択暗号文攻撃に対しての安全性.
(2) 推奨パラメータ長での DiÆe-Hellman 仮定の安全性.
(1) については [5], [21] で構築された理論に基づいた形で仕様書に記載されている安全性の証明を検証した. 結果, 証明の不足, 誤り等は特に認められず , 主張通り ACE 暗号はいくつかの仮定のもとで適応的選択暗号文攻撃に対して強秘匿性 (または頑強性) を持つことがわかった. 従って ACE 暗号は現在の公開鍵暗号方式に対する安全性の概念の中で , 最強暗号に属すことがわかった.
安全性証明のための仮定には汎用一方向性ハッシュ関数の存在が含まれるが , この仮定は , 安全性証明可能を主張する他の暗号の多くが前提とするいわゆる理想的ハッシュ関数の存在 (ランダムオラ
クルモデル) に比べると弱い (現実的) 仮定と考えられ , 比較的現実的な仮定のもとで安全性が証明され得る希少な公開鍵暗号方式であるといえる.
(2) については決定性 DiÆe-Hellman 問題の困難性を直接は評価せず, 対象となっている群上の離散対数問題の困難性について考察した. その結果, 指数計算法の適応に対して耐性を持つために素数P の選択方法に注意が必要と思われるが , 適切な選択をするならば , パラメータ長は十分大きく取られているため現在の計算能力では離散対数を求めることは困難であり, 安全性には問題がないことがわかった. ただし , 離散対数問題の困難性と DiÆe-Hellman 問題の困難性との等価性については未解決な部分があることに注意すべきと考える.

参考文献[1] M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing eÆcient
protocols, In First ACM Conference on Computer and Communications Security, pp.62-73(1993).
[2] M. Bellare and P. Rogaway. : Optimal asymmetric encryption { How to encrypt with RSA,
Advances in Cryptology { Eurocrypt'94, LNCS 950, Springer-Verlag, pp.92-111 (1994)[3] C. Burwick, D. Coppersmith, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S. Matyas Jr.,
L. O'Connor, M. Peyravian, D. Sa ord, and N. Zunic, MARS-a candidate cipher for AES,
June 1998.
[4] D. Coppersmith, Modi cations to the Number Field Sieve, J. Cryptology, 6, 3, pp.169-180(1993).
[5] R. Crammer and V. Shoup, A practical public key cryptosystem provably secure against
adaptive chosen ciphertext attack, In Advances in Cryptology-Crypto '98, pp.13-25 (1998).
[6] C. Curry, The NFSNET Project, http://orca.st.usm.edu/ cwcurry/nfs/nfs.html[7] I. Damgard, Collision free hash functions and public key signature schemes, In Advances in
Cryptology-Eurocrypt (1987).

11[8] W. DiÆe and M. E. Hellman, New directions in cryptography, IEEE Trans. Info. Theory
pp.644-654 (1976).

22,[9] T. ElGamal. : A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Information Theory, IT-31, 4, pp.469-472(1985).

[10] S. Goldwasser and M. Bellare. : Lecture Notes on Cryptography, http:/www-cse.ucsd.edu/
users/mihir/ (1997).
[11] D. Gordon, Discrete logarithms in GF (p) using the number eld sieve, SIAM J. Discrete
Math. , pp.124-138 (1993).

6[12] R. Impagliazzo and D. Zuckermann, How to recycle random bits, In 30th Annual Symposium
on Foundations of Computer Science, pp.248-253 (1989).
[13] H. W. Lenstra Jr., Factoring Integers with Elliptic Curves, Annals of Math., 126 pp.649-673(1987).
[14] A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse and J. M. Pollard, The Number Field Sieve,
Proc. of STOC, pp.564-572 (1990).
[15] M. Luby, Pseudorandomness and Cryptographic Applications, Princeton University Press,
1996.
[16] A. Menesez, P. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC
Press, 1997.
[17] M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications,
In 21st Annual ACM Symposium on Thoery of Computing, 1989.
[18] T. Okamoto and S. Uchiyama, : A new public-key cryptosystem as secure as factoring,
Advances in Cryptology { Eurocrypt'98, LNCS 1403, Springer-Verlag, pp.308-318 (1998).
[19] 岡本龍明，山本博資．：現代暗号，産業図書 (1997).
[20] R. L. Rivest, A. Shamir and L.Adleman. : A method for obtaining digital signatures andpublic-key cryptosystems, Communications of the ACM, Vol.21, No.2, pp.120-126 (1978).
[21] V. Shoup, A composition theorem for universal one-way hash functions, In Advances in
Cryptology-Eurocrypt2000 (2000).
[22] V. Shoup, Using hash functions as a hedge against chosen ciphertext attack, In Advances in
Cryptology-Eurocrypt2000 (2000).
[23] D. Simon, Finding collisions on a one-way street: can secure hash functions be based on
general assumptions?, In Advances in Cryptology-Eurocrypt '98, pp.334-345 (1998).
[24] P. Zimmerman, The ECMNET Project, http://www.loria.fr/ zimmerma/records/ecmnet.html

12