TY - GEN
T1 - The beauty and the beasts—The hard cases in LLL reduction
AU - Alsayigh, Saed
AU - Ding, Jintai
AU - Takagi, Tsuyoshi
AU - Wang, Yuntao
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In this paper, we will systematically study who indeed are the hard lattice cases in LLL reduction. The “hard” cases here mean for their special geometric structures, with a comparatively high “failure probability” that LLL can not solve SVP even by using a powerful relaxation factor. We define the perfect lattice as the “Beauty”, which is given by basis of vectors of the same length with the mutual angles of any two vectors to be exactly 60°. Simultaneously the “Beasts” lattice is defined as the lattice close to the Beauty lattice. There is a relatively high probability (e.g. 15.0% in 3 dimensions) that our “Beasts” bases can withstand the exact-arithmetic LLL reduction (relaxation factors δ close to 1), comparing to the probability (corresponding <0.01%) when apply same LLL on random bases from TU Darmstadt SVP Challenge. Our theoretical proof gives us a direct explanation of this phenomenon. Moreover, we give rational Beauty bases of 3 and 8 dimensions, an irrational Beauty bases of general high dimensions. We also give a general way to construct Beasts lattice bases from the Beauty ones. Experimental results show the Beasts bases derived from Beauty can withstand LLL reduction by a stable probability even for high dimensions. Our work in a way gives a simple and direct way to explain how to build a hard lattice in LLL reduction.
AB - In this paper, we will systematically study who indeed are the hard lattice cases in LLL reduction. The “hard” cases here mean for their special geometric structures, with a comparatively high “failure probability” that LLL can not solve SVP even by using a powerful relaxation factor. We define the perfect lattice as the “Beauty”, which is given by basis of vectors of the same length with the mutual angles of any two vectors to be exactly 60°. Simultaneously the “Beasts” lattice is defined as the lattice close to the Beauty lattice. There is a relatively high probability (e.g. 15.0% in 3 dimensions) that our “Beasts” bases can withstand the exact-arithmetic LLL reduction (relaxation factors δ close to 1), comparing to the probability (corresponding <0.01%) when apply same LLL on random bases from TU Darmstadt SVP Challenge. Our theoretical proof gives us a direct explanation of this phenomenon. Moreover, we give rational Beauty bases of 3 and 8 dimensions, an irrational Beauty bases of general high dimensions. We also give a general way to construct Beasts lattice bases from the Beauty ones. Experimental results show the Beasts bases derived from Beauty can withstand LLL reduction by a stable probability even for high dimensions. Our work in a way gives a simple and direct way to explain how to build a hard lattice in LLL reduction.
UR - http://www.scopus.com/inward/record.url?scp=85028471590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028471590&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-64200-0_2
DO - 10.1007/978-3-319-64200-0_2
M3 - Conference contribution
AN - SCOPUS:85028471590
SN - 9783319641997
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 19
EP - 35
BT - Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings
A2 - Obana, Satoshi
A2 - Chida, Koji
PB - Springer Verlag
T2 - 12th International Workshop on Security, IWSEC 2017
Y2 - 30 August 2017 through 1 September 2017
ER -