The beauty and the beasts—The hard cases in LLL reduction

Saed Alsayigh; Jintai Ding; Tsuyoshi Takagi; Yuntao Wang

doi:10.1007/978-3-319-64200-0_2

The beauty and the beasts—The hard cases in LLL reduction

Saed Alsayigh^*, Jintai Ding, Tsuyoshi Takagi, Yuntao Wang

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Title of host publication	Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings
Editors	Satoshi Obana, Koji Chida
Publisher	Springer Verlag
Pages	19-35
Number of pages	17
ISBN (Print)	9783319641997
DOIs	https://doi.org/10.1007/978-3-319-64200-0_2
Publication status	Published - 2017
Externally published	Yes
Event	12th International Workshop on Security, IWSEC 2017 - Hiroshima, Japan Duration: 30 Aug 2017 → 1 Sept 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10418 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Workshop on Security, IWSEC 2017
Country/Territory	Japan
City	Hiroshima
Period	30/08/17 → 1/09/17

Keywords

Hard cases
Lattice
LLL reduction
Post-quantum cryptography

Access to Document

10.1007/978-3-319-64200-0_2

Cite this

Alsayigh, S., Ding, J., Takagi, T., & Wang, Y. (2017). The beauty and the beasts—The hard cases in LLL reduction. In S. Obana, & K. Chida (Eds.), Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings (pp. 19-35). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10418 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-64200-0_2

Alsayigh, Saed ; Ding, Jintai ; Takagi, Tsuyoshi et al. / The beauty and the beasts—The hard cases in LLL reduction. Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings. editor / Satoshi Obana ; Koji Chida. Springer Verlag, 2017. pp. 19-35 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3fba5b7c2cde4460b1468790fc5b4e67,

title = "The beauty and the beasts—The hard cases in LLL reduction",

abstract = "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.",

keywords = "Hard cases, Lattice, LLL reduction, Post-quantum cryptography",

author = "Saed Alsayigh and Jintai Ding and Tsuyoshi Takagi and Yuntao Wang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 12th International Workshop on Security, IWSEC 2017 ; Conference date: 30-08-2017 Through 01-09-2017",

year = "2017",

doi = "10.1007/978-3-319-64200-0_2",

language = "English",

isbn = "9783319641997",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "19--35",

editor = "Satoshi Obana and Koji Chida",

booktitle = "Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings",

}

Alsayigh, S, Ding, J, Takagi, T & Wang, Y 2017, The beauty and the beasts—The hard cases in LLL reduction. in S Obana & K Chida (eds), Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10418 LNCS, Springer Verlag, pp. 19-35, 12th International Workshop on Security, IWSEC 2017, Hiroshima, Japan, 30/08/17. https://doi.org/10.1007/978-3-319-64200-0_2

The beauty and the beasts—The hard cases in LLL reduction. / Alsayigh, Saed; Ding, Jintai; Takagi, Tsuyoshi et al.
Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings. ed. / Satoshi Obana; Koji Chida. Springer Verlag, 2017. p. 19-35 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10418 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

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.

KW - Hard cases

KW - Lattice

KW - LLL reduction

KW - Post-quantum cryptography

UR - http://www.scopus.com/inward/record.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 Proceeding

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 -

Alsayigh S, Ding J, Takagi T, Wang Y. The beauty and the beasts—The hard cases in LLL reduction. In Obana S, Chida K, editors, Advances in Information and Computer Security - 12th International Workshop on Security, IWSEC 2017, Proceedings. Springer Verlag. 2017. p. 19-35. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-64200-0_2

The beauty and the beasts—The hard cases in LLL reduction

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this