Cryptology ePrint Archive: Report 2019/1009

LLL and stochastic sandpile models

Jintai Ding and Seungki Kim and Tsuyoshi Takagi and Yuntao Wang

Abstract: We introduce stochastic sandpile models which imitate numerous aspects of the practical behavior of the LLL algorithm with compelling accuracy. In addition, we argue that the physics and mathematics of sandpile models provide satisfactory heuristic explanations to much of the mysteries of LLL, and pleasant implications for lattice-based cryptography as a whole. Based on these successes, we suggest a paradigm in which one regards blockwise reduction algorithms as 1-d stochastic self-organized criticality(SOC) models and study them as such.

Category / Keywords: foundations / LLL algorithm, sandpile models, lattice reduction

Date: received 6 Sep 2019

Contact author: seungki math at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190909:080530 (All versions of this report)

Short URL: ia.cr/2019/1009


[ Cryptology ePrint archive ]