パネルディスカッション
公開鍵暗号技術の最新動向について
モデレータ： 高木 剛 (公立はこだて未来大学)
パネリスト： 田中圭介 (東京工業大学)
宮地充子 (北陸先端科学技術大学院大学)
伊豆哲也 (富士通研究所)

各パネラーの話題•

田中圭介 (東工大)
公開鍵暗号の安全性証明技術
新しい公開鍵暗号•

宮地充子 (JAIST)
楕円曲線暗号について
ISOにおける公開鍵暗号技術の標準化動向•

伊豆哲也 (富士通)
公開鍵暗号の解読実験
公開鍵暗号の鍵長の選択•

高木剛 (はこだて未来大学)
2009年度CRYPTRECリストガイドWGより、IDベース暗号

2009年度リストガイドWG
主 査： 高木 剛(公立はこだて未来大学)

委 員： 金岡 晃(筑波大学大学院)
小林 鉄太郎 (日本電信電話株式会社)
白石 善明(名古屋工業大学)
高島 克幸(三菱電機株式会社)
田中 秀磨(情報通信研究機構)
花岡 悟一郎 (産業技術総合研究所)
執筆協力者： 市川 幸宏 (三菱電機株式会社)
草川 恵太 (東京工業大学)

ＩＤベース暗号•公開鍵の例
RSA暗号 Æ 2個の素数の積n = 826ed558a0f0cba7ae09485abf80c544837efeb7116153f5d6479d5945fdb6c61f50c984445d601d85eceb6bad9f700b90ae28984dd590f5ca3e6ed968a3ca32a5cf584992d92590ae9ed4f81b70d008a9e4a16905925dbb
79d82b67dc6b70869a83f037c147d298c0e2eea5f858f3881ad1071c5c221ecb795d78b68bae7863

楕円曲線暗号 Æ 楕円曲線上のランダムな点
x = 4a96b568 8ef57328 46646989 68c38bb9 13cbfc82
y = 23a62855 3168947d 59dcc912 04235137 7ac5fb32

ＩＤベース暗号 Æ 鍵長以下の自由なビット列(氏名、email アドレス，携帯電話の番号，基礎年金番号など）

現在のPKIとIDベース暗号の比較

IDベース暗号の社会基盤化に向けた3つの視点

IDベース暗号の必要な標準化
RFC 5091,
ISO/IEC 15946‐5（曲線）
RFC 5091,
IEEE 1363.3
メール暗号化（S/MIME）がIETFにおいて標準化（RFC5408, 5909）

opensslに相当するものはまだ存在しない

2009/12/1

JNSA PKI相互運用WG

6IDベース暗号メールシステム①

公開パラメータ
サーバ
公開パラメータ

PKG
Private Key③②
SenderMail⑤
Enc MailEnc④

ReceiverDec

参考情報
RFC5408: Identity‐Based Encryption Architecture and Supporting Data Structures.
RFC5409: Using the Boneh‐Franklin and Boneh‐Boyen Identity‐Based Encryption
Algorithms with the Cryptographic Message Syntax (CMS).

公開鍵証明書を必要としないIDベース暗号が注目

暗号化メールに適用した場合
ＰＫＩ

ＩＤベース暗号

秘密鍵生成
ＣＡ

送信者

ＰＫＧ

サーバパラメータ

各公開鍵証明書

暗号化メール

受信者の認証

複数の受信者

送信者 暗号化メール 複数の受信者

事前に複数の公開鍵証明書必須

事前に単数のパラメータ必須

受信者ごとに公開鍵証明書を管理

公開鍵＝ＩＤであるため特殊な管理不要

Webシステム全体図
政府(0)初期設定処理、
秘密鍵・公開鍵生成

コンテンツ, 公開鍵, 利用者IDリスト(2)利用者登録(秘密鍵配布)

コンテンツ
保守業者

(3)(4)コンテンツ作成/更新(利用者のIDで暗号化)

インターネット(1)暗号化コンテンツ閲覧

利用者
参考情報：「情報システムの構築等におけるセキュリティ要件及びセキュリティ機能の検討に関する解説書」
2007 年11 月 内閣官房情報セキュリティセンター

パスワードPW利用
1.IDとPWを送信

ID,PWID,PW

攻撃対象

2. ID,PWを確認
利用者端末

IDベース暗号利用

3.コンテンツを送信Webサーバー

1.IDを送信

ID,SID
2.暗号化されたコンテンツを送信
利用者端末

3. ID,SIDを用いて暗号化されたコンテンツを復号

Webサーバー格子問題に基づく暗号• IDベース暗号‐ Gentry, Peikert, Vaikuntanathan: Trapdoors for hard lattices and new cryptographic constructions. STOC 2008.
‐ Agrawal, Boyen: Identity‐Based Encryption from Lattices in the Standard Model unpublished manuscript, 2009.
‐ Peikert: Bonsai Trees (or, Arboriculture in Lattice‐Based Cryptography), Cryptology ePrint Archive: Report 2009/359.
‐ Cash, Hofheinz, Kiltz: How to Delegate a Lattice Basis, Cryptology ePrint Archive: Report 2009/351.
‐ Boneh, Boyen: Efficient Lattice (H)IBE in the Standard Model from the BB‐1 Framework, rump session talk at CRYPTO 2009.
‐ Stehlé, Steinfeld, Tanaka, Xagawa: Efficient Public Key Encryption Based on Ideal Lattices. ASIACRYPT 2009.

• CCA安全な公開鍵暗号‐ Peikert, Waters: Lossy Trapdoor Functions and their Applications. STOC 2008, 187‐196.
• 完全準同型暗号‐ Gentry: Fully Homomorphic Encryption Using Ideal Lattices. STOC 2009, 169‐178.

A

E = U

AT s + x = p
UT s + y = v

Ext: Generate E
Enc: (p, v + wq/2)
Dec: d = v – ETp = wq/2 + y – ETx ≈ wq/2

一様分布と識別不可能
12

公開鍵暗号の解読実験• 676ビット 有限体上の離散対数問題DLP
2009年12月9日、(NICT、公立はこだて未来大学)
http://www2.nict.go.jp/pub/whatsnew/press/h21/100223/100223.html• 768ビット 素因数分解
2009年12月12日、(NTT、ボン大学、EPFL、INRIA、CWI)
http://www.ntt.co.jp/news2010/1001/100108a.html

有限体上のDLP計算世界記録
有限体

GF(p)

GF(2n)

GF(p3)

GF(p30)

GF(36n)

著者

Kleinjung et al

Joux et al

Joux et al

Joux, Lercier

本実験

日付

2007/2/5

2005/9/22

2006/8/23

2005/9/11

2009/12/09

アルゴリ
ズム

NFS

FFS

NFS

FFS

FFS関係探索ステップ

Many CPUs

16 Itanium2 ×
4ノード

16 alpha
processor

16 alpha
processor

Xeon (2.83 GHz)
計96コア

線形代数
ステップ

12‐24 Xeon
(3.2GHz)

16 Itanium2 ×
4ノード

16 alpha
processor

16 alpha
processor

Xeon (2.83 GHz)
計80コア

計算時間

33日

17日

19日

0.5日

33日

ビット長

532

613

394

556

676

15/15

2010/01/22