The closest vector problem in tensored root lattices of type A and in their duals
type: Item
instance of: scholarly article
title: The closest vector problem in tensored root lattices of type A and in their duals
zbMATH Open document ID: 1381.11057
author: Léo Ducas
author: Wessel P. J. van Woerden
published in: Designs, Codes and Cryptography
publication date: 2018-01-26T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/25527
review text: The closest vector problem (also known as maximum likelihood decoding) is a fundamental question in lattice based cryptography. The authors study the closest vector problem in the tensor root lattices of Type A, \((A_m \otimes A_n)\), and in their duals \((A_m^* \otimes A_n^*).\) They solve the closest vector problem in \(Z[\zeta_c]\) and \(Z[\zeta_c]^\lor\) for conductors of the form \(c = 2^\alpha p ^\beta q^\gamma\) for any two odd primes \(p\) and \(q\). In the primal case \((A_m \otimes A_n)\), they give a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph \(K_{m+1,n+1}.\) Using this, they obtain a closest vector problem algorithm running in polynomial time. The algorithm performs \(O(l m^2n^2 \min \{ m,n \})\) operations on reals, where \(l\) is the number of bits per coordinate of the input target. In the dual case a gluing construction is used to solve the closest vector problem in sub-exponential time \(O(nm^{n+1})\).
reviewed by: Steven T. Dougherty
Mathematics Subject Classification ID: 11H71
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94B75
Mathematics Subject Classification ID: 94B35
zbMATH DE Number: 6830013
zbMATH Keywords: lattice based cryptography
zbMATH Keywords: cyclotomic lattices
zbMATH Keywords: tensored root lattices
zbMATH Keywords: closest vector problem
zbMATH Keywords: maximum likelihood decoding
describes a project that uses: ring-LWE
MaRDI profile type: Publication
OpenAlex ID: W2583468640
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
cites work: Fast quantizing and decoding and algorithms for lattice quantizers and codes
cites work: Voronoi regions of lattices, second moments of polytopes, and quantization
cites work: Q3651735
cites work: On Ideal Lattices and Learning with Errors over Rings
cites work: A Toolkit for Ring-LWE Cryptography
cites work: An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$
cites work: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
cites work: Algebraic Number Theory and Code Design for Rayleigh Fading Channels
DOI: 10.1007/S10623-017-0332-X
Recommended article: Q2754148
Recommended article: Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
Recommended article: A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices
Recommended article: Corrigenda: Complexity of the closest vector problem in a lattice generated by (0,1)-matrix
Recommended article: Dual vectors and lower bounds for the nearest lattice point problem
Recommended article: Lattice Sparsification and the Approximate Closest Vector Problem
Recommended article: Q5741633
Recommended article: Q3740576
Recommended article: A vector lattice version of r˚ adström's embedding theorem
description: scientific article; zbMATH DE number 6830013