Paper 2019/1009 Original: eprint.iacr.org/2019/1009 ↗
LLL and stochastic sandpile models
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.
- History
- 2019-09-09: last updated
- 2019-09-09: published
- Short URL
- https://ia.cr/2019/1009
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}