Paper 2019/1009
LLL and stochastic sandpile models
Jintai Ding, Seungki Kim, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- LLL algorithmsandpile modelslattice reduction
- Contact author(s)
- seungki math @ gmail com
- History
- 2019-09-09: received
- Short URL
- https://ia.cr/2019/1009
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1009,
author = {Jintai Ding and Seungki Kim and Tsuyoshi Takagi and Yuntao Wang},
title = {{LLL} and stochastic sandpile models},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/1009},
year = {2019},
url = {https://eprint.iacr.org/2019/1009}
}
