| 講演名 | 1999/7/22 グラフ理論を用いたtruncated differential探索について 大久保 美也子, 盛合 志帆, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年, ブロック暗号の安全性を評価する上でtruncated differentialの役割が注目されている. ブロック暗号に対してtruncated differentialを利用して暗号攻撃を行なうには, その攻撃に利用できるtruncated differentialを見つける事が大変重要である. 従来の差分解読法では通常1bitごとのdifferentialを取り扱うのに対して, truncated differentialを利用した暗号解析では, 複数bitを1単位と見なして, その1単位と見なしたサブブロックごとのdifferentialを取り扱う. 一方, グラフ理論における最短経路問題の解法として, Dijkstraのアルゴリズム, Warshall-Floydのアルゴリズムなどが知られているが, 本稿ではtruncated differentialの探索へこれらの方法を適用する事を検討した. また, 実際に共通鍵暗号E2に適用し探索を行なった. 本稿ではその適用方法や探索計算量の比較を示す. |
| 抄録(英) | Recently truncated differentials play important roles in evaluating security of block ciphers. While differentials are based on bitwise differences, truncated differentials can be considered as t-bitwise differentials for a certain natural number t. This paper presents the truncated differential search using Dijkstra algorithm and Warshall-Floyd algorithm, which are known as algorithms for the shortest pathproblem in the field of graph theory. To put it concretely, we show how to apply the algorithms to the truncated differential search and compare both methods in terms of required memory and complexity. We also show the complexity in the case of the truncated differential search of the block cipher E2. |
| キーワード(和) | 暗号解析 / ブロック暗号 / truncated differential / Dijkstraのアルゴリズム / Warshall-Floydのアルゴリズム / Feistel構造 / SPN構造 |
| キーワード(英) | cryptanalysis / block ciphers / Dijkstra algorithm / Warshall-Floyd algorithm / truncated differential / Feistel structure / SPN structure |
| 資料番号 | ISEC99-21 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 1999/7/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフ理論を用いたtruncated differential探索について |
| サブタイトル（和） | |
| タイトル（英） | Truncated Differential Search Using Graph Algorithms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 暗号解析 / cryptanalysis |
| キーワード(2)（和/英） | ブロック暗号 / block ciphers |
| キーワード(3)（和/英） | truncated differential / Dijkstra algorithm |
| キーワード(4)（和/英） | Dijkstraのアルゴリズム / Warshall-Floyd algorithm |
| キーワード(5)（和/英） | Warshall-Floydのアルゴリズム / truncated differential |
| キーワード(6)（和/英） | Feistel構造 / Feistel structure |
| キーワード(7)（和/英） | SPN構造 / SPN structure |
| 第 1 著者 氏名（和/英） | 大久保 美也子 / Miyako Ohkubo |
| 第 1 著者 所属（和/英） | NTT情報流通プラットフォーム研究所 NTT Information Sharing Platformand Laboratories |
| 第 2 著者 氏名（和/英） | 盛合 志帆 / Shiho Moriai |
| 第 2 著者 所属（和/英） | NTT情報流通プラットフォーム研究所 NTT Information Sharing Platformand Laboratories |
| 発表年月日 | 1999/7/22 |
| 資料番号 | ISEC99-21 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 208 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |