This paper concerns the hardness of approximating the closestvector in a lattice with preprocessing in l1norm,and gives a polynomial time algorithm for GapCVPPγin l1norm with gapγ=O(n/log n).The gap is smaller than...
详细信息
This paper concerns the hardness of approximating the closestvector in a lattice with preprocessing in l1norm,and gives a polynomial time algorithm for GapCVPPγin l1norm with gapγ=O(n/log n).The gap is smaller than that obtained by simply generalizing the approach given by Aharonov and *** main technical ingredient used in this paper is the discrete Laplace distribution on lattices which may be of independent interest.
Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai [in Proceedings of the 28th Annual ACM Symposium on Theory...
详细信息
Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai [in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, PA, 1996, pp. 99-108] connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous self-contained proof of results along the lines of Ajtai's seminal work. At the same time, we explore to what extent Ajtai's original results can be quantitatively improved. As a by-product, we de. ne a random class of lattices such that computing short nonzero vectors in the class with nonnegligible probability is at least as hard as approximating the length of the shortest nonzero vector in any n-dimensional lattice within worst-case approximation factors gamma(n) = n(3)omega(rootlog n log log n). This improves previously known best connection factor gamma(n) = n(4+epsilon) [J.-Y. Cai and A. P. Nerurkar, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 468-477]. We also show how our reduction implies the existence of collision resistant cryptographic hash functions based on the worst-case inapproximability of the shortest vectorproblem within the same factors gamma(n) = n(3)omega(rootlog n log log n). In the process we distill various new lattice problems that might be of independent interest, related to the covering radius, the bounded distance decoding problem, approximate counting of lattice points inside convex bodies, and the efficient construction of lattices with good geometric and algorithmic decoding properties. We also show how further investigation of these new lattice problems might lead to even stronger connections between the average-case and worst-case complexity of the shortest vectorproblem, possibly leading to connection factors as low as gamma(n) = n(1.5)
Following the recent line of work on solving the closest vector problem with preprocessing (CVPP) using approximate Voronoi cells, we improve upon previous results in the following ways: - We derive sharp asymptotic b...
详细信息
ISBN:
(纸本)9783030453879;9783030453886
Following the recent line of work on solving the closest vector problem with preprocessing (CVPP) using approximate Voronoi cells, we improve upon previous results in the following ways: - We derive sharp asymptotic bounds on the success probability of the randomized slicer, by modelling the behaviour of the algorithm as a random walk on the coset of the lattice of the target vector. We thereby solve the open question left by Doulgerakis-Laarhoven-De Weger [PQCrypto 2019] and Laarhoven [MathCrypt 2019]. - We obtain better trade-offs for CVPP and its generalisations (strictly, in certain regimes), both with and without nearest neighbour searching, as a direct result of the above sharp bounds on the success probabilities. - We show how to reduce the memory requirement of the slicer, and in particular the corresponding nearest neighbour data structures, using ideas similar to those proposed by Becker-Gama-Joux [Cryptology ePrint Archive, 2015]. Using 2(0.185d+o(d)) memory, we can solve a single CVPP instance in 2(0.264d+o(d)) time. - We further improve on the per-instance time complexities in certain memory regimes, when we are given a sufficiently large batch of CVPP problem instances for the same lattice. Using 2(0.208d+o(d)) memory, we can heuristically solve CVPP instances in 2(0.234d+o(d)) amortized time, for batches of size at least 2(0.058d+o(d)). Our random walk model for analysing arbitrary-step transition probabilities in complex step-wise algorithms may be of independent interest, both for deriving analytic bounds through convexity arguments, and for computing optimal paths numerically with a shortest path algorithm. As a side result we apply the same random walk model to graph-based nearest neighbour searching, where we improve upon results of Laarhoven [SOCG 2018] by deriving sharp bounds on the success probability of the corresponding greedy search procedure.
暂无评论