About: Sieve, Enumerate, Slice, and Lift:: Hybrid Lattice Algorithms for SVP via CVPP

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Sieve, Enumerate, Slice, and Lift:: Hybrid Lattice Algorithms for SVP via CVPP Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Sieve, Enumerate, Slice, and Lift:: Hybrid Lattice Algorithms for SVP via CVPP
Creator	Doulgerakis, Emmanouil Laarhoven, Thijs De Weger, Benne
Source	PMC
abstract	Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension d with a cost proportional to running a sieve in dimension [Formula: see text], resulting in a [Formula: see text] speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of [Formula: see text] dimensions for free for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the [Formula: see text] term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.
has issue date	2020-06-06(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51938-4_15
has license	no-cc
sha1sum (hex)	510ea36f56d09f9c64d42f518ec9809e4e51044c
schema:url	https://doi.org/10.1007/978-3-030-51938-4_15
resource representing a document's title	Sieve, Enumerate, Slice, and Lift:: Hybrid Lattice Algorithms for SVP via CVPP
has PubMed Central identifier	PMC7335001
schema:publication	Progress in Cryptology - AFRICACRYPT 2020
resource representing a document's body	covid:510ea36f56d09f9c64d42f518ec9809e4e51044c#body_text
is schema:about of	named entity 'THESE' named entity 'large' named entity 'solving' named entity 'Lattice' named entity 'shortest vector problem' named entity 'CVP' named entity 'SVP' named entity 'asymptotic expansion' named entity 'heuristic' named entity 'Stirling's approximation' named entity 'asymptotic time complexity' named entity 'Heuristic result' named entity 'heuristic' named entity 'polynomial' named entity 'vector' named entity 'depth-first' named entity 'CVP' named entity 'SVP' named entity 'vector' named entity 'vector' named entity 'vectors' named entity 'polynomial' named entity 'SVP' named entity 'heuristic' named entity 'shortest vector' named entity 'iter' named entity 'CVP' named entity 'probability' named entity 'vector' named entity 'iter' named entity 'vectors' named entity 'algorithm' named entity 'brute-force' named entity 'CVP' named entity 'Gaussian distribution' named entity 'vectors' named entity 'hybrid algorithm' named entity 'data structures' named entity 'CVP' named entity 'CVP' named entity 'CVP' named entity 'time complexity' named entity 'algorithm' named entity 'probability mass function' named entity 'vectors' named entity 'probability' named entity 'iter' named entity 'vectors' named entity 'vector' named entity 'CVP' named entity 'shortest vector' named entity 'hash tables' named entity 'shortest vector' named entity 'data structure' named entity 'heuristic' named entity 'SVP' named entity 'CVP' named entity 'vector' named entity 'heuristic' named entity 'time complexity' named entity 'time complexity' named entity 'shortest vector' named entity 'hybrid algorithm' named entity 'vectors' named entity 'Asymptotically' named entity 'CVP' named entity 'basis vectors' named entity 'lattice sieving' named entity 'algorithm' named entity 'SVP' named entity 'vectors' named entity 'problem instances' named entity 'vectors' named entity 'algorithm' named entity 'lattice-based cryptography' named entity 'heuristic' named entity 'heuristic' named entity 'iter' named entity 'vectors' named entity 'lattice problems' named entity 'lattice sieving'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software