B2: 暗号解析手法の計算量理論による改良とそれに基づく暗号方式河内戸田渡辺田中亮周（東京工業大学）誠之助（日本大学）治（東京工業大学）圭介（東京工業大学）研究の目的と活動の概要    暗号の安全性に関する精密な解析手法の開発（戸田） – chordal graphを対象としたグラフ同型性判定問題ならびにグラフ自己同型群計算問題暗号の効率に関する精密な解析手法の開発（渡辺, 河内） – 充足可能性問題に対する考察，計算量クラスの相対化における妥当な比較の枠組目的１および２に基づく具体的暗号方式の提案（田中）世話人となった研究集会ミニ研究集会: chordal graphに関する計算問題ならびにアルゴリズム      Chordal graphに関する計算問題ならびにアルゴリズムを中心に研究成果の発表と新たな課題探求に向けた討論を行った．日時: 2005 年 3 月 19 日(土) 午前10時-午後6時場所: 日本大学文理学部8号館レクチャーホール参加者数: 20名世話人: 戸田誠之助 (日大) プログラム      Computing automorphism groups of chordal graphs whose simplicial components are of small size (戸田誠之助 (日大)) 2-リンクパズルの多項式時間解法 (牧野格三 (東工大)) On the Laminar Structure of Ptolemaic and Distance Hereditary Graphs (上原隆平 (JAIST), 宇野裕之 (大阪府立大学)) On precoloring extension problem (名古屋孝幸（東京電機大学)) Computational Distinguishability between Quantum States and Its Applications (河内亮周（東工大)) 第1回暗号関係ミニ研究集会     日時: 2006年2月16日(木) 13:00-17:30 場所: はこだて未来大学小講義室585 参加者: 20名世話人: – 太田和夫 (電気通信大学) – 國廣昇 (電気通信大学) – 櫻井幸一 (九州大学) – 高木剛 (はこだて未来大学) – 田中圭介 (東京工業大学) プログラム Privacy-preserving Text Mining in Distributed Environment Chunhua Su, Kouichi Sakurai (九州大学) Pairing Implementation using Hyperelliptic Curves Colm O hEigeartaigh (Dublin City University) A Survey about Side Channel Attacks on XTR Dong-Guk Han, Tsuyoshi Takagi (はこだて未来大学) オフライン検証性を満たす追跡不可能な量子現金國廣昇 (電気通信大学) 離散対数問題系に基づく安全で効率的な署名方式太田和夫 (電気通信大学) 匿名性をもつ公開鍵暗号林良太郎, 田中圭介 (東京工業大学) 第2回暗号関係ミニ研究集会 • • • • 日時: 2007年3月2日(金) 13:30-17:30 3月3日(土) 9:30-15:45 場所: 電気通信大学総合研究棟 601 会議室参加者: 1日目が40名，2日目が30名世話人: • 太田和夫 (電気通信大学) • 國廣昇 (電気通信大学) • 櫻井幸一 (九州大学) • 高木剛 (はこだて未来大学) • 田中圭介 (東京工業大学) プログラム 1 日目      証明可能安全性理論に向けて太田和夫 (電気通信大学) 耐タンパ性を備えたユニークデバイスに基づく暗号認証基盤の検討蘇春華 (九州大学) ペアリング暗号の安全な高速実装について高木剛 (はこだて未来大学) 指定検証者署名の定式化、および、送信者と受信者の匿名性について大山千尋 (東京工業大学) Concurrently Secure Password-based Authenticated Key Exchange without Random Oracles or Setup Assumptions 米山一樹 (電気通信大学) プログラム 2 日目      スタンダードモデル PA の基礎に関して寺西勇 (NEC) Non-Malleability Definitions Reconsidered 宮川聡 (電気通信大学) Collusion-resistant Private Association Rules Mining in Distributed Environment 蘇春華 (九州大学) Revisiting Zero-Knowledgeness of an On the fly Authentication Scheme Santoso Bagus （電気通信大学）格子問題をベースとした暗号について草川恵太 (東京工業大学) これまでの成果研究発表            Discrete Applied Mathematics Algorithmica SIAM Journal on Computing Eurocrypt 2005 Asiacrypt 2005 ACISP 2005, 2006, 2007 PKC 2005, 2007 ISAAC 2005, 2006 SWAT 2006 ICALP 2006 SIGACT News 計算理論（計算限界）からの暗号理論へのアプローチ計算理論と暗号理論 (1) 少ない計算資源のもとでのアルゴリズムの効率化（本特定でも議論)  暗号アルゴリズムについては、高速で動作したり少ないメモリで動作することが求められることが多い。特に、SUICAなどのICカードや携帯電話などで快適に動作することが求められている。計算理論と暗号理論 (2) 漸近的解析ではない計算時間解析 (本特定もで考察)  暗号アルゴリズムの効率化は基本的にサイズ固定である。それ以外にも、攻撃を行うためのアルゴリズムの高速解法を追求していく中で、キャッシュの使用効率を上げるためなどに特定サイズのパッキング問題を解く状況が生じる。計算理論と暗号理論 (3) PでもNP完全でもない計算問題  公開鍵暗号の仕組みとして用いるには、ベースとなる計算問題はPでもNP完全でもいけない – – – – 数論問題格子上のベクトルに関する問題 (本特定でも考察) ナップザック問題（本特定でも議論) 符号に関する問題（本特定でも議論) 計算理論と暗号理論 (4) 新たな計算モデルに対する考察  暗号の攻撃では未知の敵に対処しなくてはならない。新たな計算モデルが存在する可能性を常に考察していく必要がある。 – – – – 量子計算 (本特定でも考察) 並列計算グリッド計算計算モデルはかえずに状況をかえる • デバイスからのデータの直接的リーク • 匿名性 (本特定でも考察) 計算理論と暗号理論 (5) 平均ケースと最悪ケースの計算量が同等である計算問題  暗号アルゴリズムは本質的に確率的アルゴリズムとなる。数論ベースの暗号では平均ケースと最悪ケースのつながりは難しい。 – 格子問題をベースとした暗号 – 格子問題をベースとした署名 – 格子問題をベースとした認証平均/最悪のつながりと暗号システム    鍵生成 - 確率的アルゴリズム – みんなで同じ鍵を使うわけにはいかない暗号化 - 確率的アルゴリズム – おなじメッセージを２回暗号化するとばれる復号 - 決定的アルゴリズム – メッセージはひととおりに復元してほしい暗号システムではアルゴリズムの平均的な性質が本質的に必要主要な成果のひとつ - 格子ベース暗号システム ◆平均ケースと最悪ケースのつながりをもつ初めてのマルチ・ビットの暗号 ◆１ビットしかなかった。 ◆マルチ・ビットのものでは平均/最悪のつながりをもたないものしかなかった。 ◆平均ケースと最悪ケースのつながりをもつ初めての署名 ◆平均/最悪のつながりをもたないものしかなかった。 ◆平均ケースと最悪ケースのつながりをもつ初めての認証 ◆平均/最悪のつながりをもたないものしかなかった。今後の課題  計算理論（計算限界）と暗号理論との関係を広く捉えて問題を探していく – 特に、暗号理論から計算理論に対するフィードバック例えば、暗号理論における匿名性は計算理論の方では何に対応する？