日時：11/22（金）10:30-12:00
場所：九州大学 伊都キャンパス ウェスト2号館 3階 第5・6講義室
講演者：Ravi Montenegro (University of Massachusetts Lowell)
題目：A sharp heuristic for complexity of some Birthday attacks 
inspired by Markov Processes

概要：
Birthday attacks use probabilistic "paradoxes'' to solve 
cryptographic problems. However, the heuristics used to justify such 
methods are usually not strong enough to differentiate a more 
efficient approach from a less efficient one. We remedy this 
shortcoming with a rigorous result for Pollard's Kangaroo method for 
discrete logarithm, and extend it with a very precise heuristic that 
applies to those attacks which are modeled on a Markov chain. This 
precision makes it possible to explain the differing performance 
between attacks that are superficially similar, such as Pollard's 
Rho for discrete logarithm when compared to Teske's additive 
version, and can also be used in optimizing birthday attack design.

問合せ：来嶋(B01)