Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing

T.M.M. Laarhoven; B.M.M. Weger, de

doi:10.1007/978-3-319-22174-8_6

Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing

T.M.M. Laarhoven, B.M.M. Weger, de

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

16 Citaten (Scopus)

Samenvatting

Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time and space $2^{0.2972n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers. Keywords: lattices, shortest vector problem, sieving algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing

Originele taal-2	Engels
Titel	Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015)
Redacteuren	K. Lauter, F. Rodríguez-Henríquez
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	101-118
ISBN van geprinte versie	978-3-319-22173-1
DOI's	https://doi.org/10.1007/978-3-319-22174-8_6
Status	Gepubliceerd - 2015

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	9230
ISSN van geprinte versie	0302-9743

Toegang tot document

10.1007/978-3-319-22174-8_6

Vingerafdruk Duik in de onderzoeksthema's van 'Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

Laarhoven, T. M. M., & Weger, de, B. M. M. (2015). Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In K. Lauter, & F. Rodríguez-Henríquez (editors), Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015) (blz. 101-118). (Lecture Notes in Computer Science; Vol. 9230). Springer. https://doi.org/10.1007/978-3-319-22174-8_6

Laarhoven, T.M.M. ; Weger, de, B.M.M. / Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015). redacteur / K. Lauter ; F. Rodríguez-Henríquez. Berlin : Springer, 2015. blz. 101-118 (Lecture Notes in Computer Science).

@inproceedings{6d97760b46684258a4acb104b1302629,

title = "Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing",

abstract = "Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time and space $2^{0.2972n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers. Keywords: lattices, shortest vector problem, sieving algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing",

author = "T.M.M. Laarhoven and {Weger, de}, B.M.M.",

year = "2015",

doi = "10.1007/978-3-319-22174-8_6",

language = "English",

isbn = "978-3-319-22173-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "101--118",

editor = "K. Lauter and F. Rodr{\'i}guez-Henr{\'i}quez",

booktitle = "Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015)",

address = "Germany",

}

Laarhoven, TMM & Weger, de, BMM 2015, Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. in K Lauter & F Rodríguez-Henríquez (redactie), Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015). Lecture Notes in Computer Science, vol. 9230, Springer, Berlin, blz. 101-118. https://doi.org/10.1007/978-3-319-22174-8_6

Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. / Laarhoven, T.M.M.; Weger, de, B.M.M.

Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015). redactie / K. Lauter; F. Rodríguez-Henríquez. Berlin : Springer, 2015. blz. 101-118 (Lecture Notes in Computer Science; Vol. 9230).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing

AU - Laarhoven, T.M.M.

AU - Weger, de, B.M.M.

PY - 2015

Y1 - 2015

N2 - Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time and space $2^{0.2972n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers. Keywords: lattices, shortest vector problem, sieving algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing

AB - Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time and space $2^{0.2972n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers. Keywords: lattices, shortest vector problem, sieving algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing

U2 - 10.1007/978-3-319-22174-8_6

DO - 10.1007/978-3-319-22174-8_6

M3 - Conference contribution

SN - 978-3-319-22173-1

T3 - Lecture Notes in Computer Science

SP - 101

EP - 118

BT - Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015)

A2 - Lauter, K.

A2 - Rodríguez-Henríquez, F.

PB - Springer

CY - Berlin

ER -

Laarhoven TMM , Weger, de BMM. Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In Lauter K, Rodríguez-Henríquez F, redacteurs, Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015). Berlin: Springer. 2015. blz. 101-118. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-22174-8_6