International Association
for Cryptologic Research

We present a general framework that converts certain types of linear collision-resistant hash

functions into one-time signatures. Our generic construction can be instantiated based on both

general and ideal (e.g. cyclic) lattices, and the resulting signature schemes are provably secure

based on the worst-case hardness of approximating the shortest vector (and other standard

lattice problems) in the corresponding class of lattices to within a polynomial factor. When

instantiated with ideal lattices, the time complexity of the signing and verification algorithms,

as well as key and signature size is almost linear (up to poly-logarithmic factors) in the dimension

n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve

lattice problems in the worst case, even when restricted to ideal lattices, our construction gives

a digital signature scheme with an essentially optimal performance/security trade-off.