A Concrete Analysis of Wagner's $k$-List Algorithm over $\mathbb{Z}_p$

ePrint Report: A Concrete Analysis of Wagner's $k$-List Algorithm over $\mathbb{Z}_p$

Antoine Joux, Hunter Kippen, Julian Loss

Since its introduction by Wagner (CRYPTO `02), the $k$-list algorithm has found significant utility in cryptanalysis. One important application thereof is in computing forgeries on several interactive signature schemes that implicitly rely on the hardness of the ROS problem formulated by Schnorr (ICICS `01). The current best attack strategy for these schemes relies the conjectured runtime of the $k$-list algorithm over $\mathbb{Z}_p$. The …

algorithm analysis application computing concrete cryptanalysis crypto eprint report forgeries found hunter important introduction list loss report signature utility wagner