Welcome to the resource topic for 2024/282
Title:
A Concrete Analysis of Wagner’s k-List Algorithm over \mathbb{Z}_p
Authors: Antoine Joux, Hunter Kippen, Julian Loss
Abstract: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 tightest known analysis of Wagner’s algorithm over \mathbb{Z}_p is due to Shallue (ANTS 08). However, it hides large polynomial factors and leaves a gap with respect to desirable concrete parameters for the attack. In this work, we develop a degraded version of the $k$-list algorithm which provably enforces the heuristic invariants in Wagner's original. In the process, we devise and analyze a new list merge procedure that we dub the interval merge. We give a thorough analysis of the runtime and success probability of our degraded algorithm, and show that it beats the projected runtime of the analysis by Shallue for parameters relevant to the generalized ROS attack of Benhamouda et al. (EUROCRYPT 21). For a 256-bit prime p, and k = 8, our degraded k-list algorithm runs in time \approx 2^{70.4}, while Shallue’s analysis states that the Wagner’s original algorithm runs in time \approx 2^{98.3}.
ePrint: https://eprint.iacr.org/2024/282
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .