Presentation 1999/7/22
Truncated Differential Search Using Graph Algorithms
Miyako Ohkubo, Shiho Moriai,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) 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.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) cryptanalysis / block ciphers / Dijkstra algorithm / Warshall-Floyd algorithm / truncated differential / Feistel structure / SPN structure
Paper # ISEC99-21
Date of Issue

Conference Information
Committee ISEC
Conference Date 1999/7/22(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Truncated Differential Search Using Graph Algorithms
Sub Title (in English)
Keyword(1) cryptanalysis
Keyword(2) block ciphers
Keyword(3) Dijkstra algorithm
Keyword(4) Warshall-Floyd algorithm
Keyword(5) truncated differential
Keyword(6) Feistel structure
Keyword(7) SPN structure
1st Author's Name Miyako Ohkubo
1st Author's Affiliation NTT Information Sharing Platformand Laboratories()
2nd Author's Name Shiho Moriai
2nd Author's Affiliation NTT Information Sharing Platformand Laboratories
Date 1999/7/22
Paper # ISEC99-21
Volume (vol) vol.99
Number (no) 208
Page pp.pp.-
#Pages 8
Date of Issue