Abstract
(MATH) We define a new family of collision resistant hash functions whose security is based on the worst case hardness of approximating the covering radius of a lattice within a factor O(πn2log n), where π is a value between 1 and √ \over n that depends on the solution of the closest vector problem in certain "almost perfect" lattices. Even for π = √ \over n, this improves the smallest (worst-case) inapproximability factor for lattice problems known to imply the existence of one-way functions. (Previously known best factor was O(n3+ε) for the shortest independent vector problem, due to Cai and Nerurkar, based on work of Ajtai.) Using standard transference theorems from the geometry of numbers, our result immediately gives a connection between the worst-case and average-case complexity of the shortest vector problem with connection factor O(πn3}log n), improving the best previously known connection factor O(n4+ε), also due to Ajtai, Cai and Nerurkar.
Keywords
Connection (principal bundle)Lattice problemHash functionMathematicsCombinatoricsDiscrete mathematicsCryptographyBoolean functionComputer scienceAlgorithm
Affiliated Institutions
Related Publications
On lattices, learning with errors, random linear codes, and cryptography
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning...
Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem
In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are requ...
Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
Abstract An O( n 3 ) heuristic algorithm is described for solving d -city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorit...
An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
In this paper, we present an $O(N^2 \log ^2 )$ algorithm for finding the two nonoverlapping substrings of a given string of length N which have the highest-scoring alignment bet...
Robust Solutions to Least-Squares Problems with Uncertain Data
We consider least-squares problems where the coefficient matrices A, b are unknown but bounded. We minimize the worst-case residual error using (convex) second-order cone progra...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 609-618
- Citations
- 28
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
28
OpenAlex
Cite This
Daniele Micciancio
(2002).
Improved cryptographic hash functions with worst-case/average-case connection.
, 609-618.
https://doi.org/10.1145/509907.509995
Identifiers
- DOI
- 10.1145/509907.509995