On Ideal Lattices, Gröbner Bases and Generalized Hash Functions
This work addresses cryptographic security by introducing multivariate ideal lattices, which is an incremental extension of univariate cases for building hash functions.
The paper tackles the problem of constructing collision-resistant hash functions by connecting ideal lattices and multivariate polynomial rings using Gröbner bases, establishing hardness results based on a worst-case problem called the shortest substitution problem.
In this paper, we draw connections between ideal lattices and multivariate polynomial rings over integers using Gröbner bases. Ideal lattices are ideals in the residue class ring, $\mathbb{Z}[x]/\langle f \rangle$ (here $f$ is a monic polynomial), and cryptographic primitives have been built based on these objects. As ideal lattices in the univariate case are generalizations of cyclic lattices, we introduce the notion of multivariate cyclic lattices and show that multivariate ideal lattices are indeed a generalization of them. Based on multivariate ideal lattices, we establish the existence of collision resistant hash functions using Gröbner basis techniques. For the construction of hash functions, we define a worst case problem, shortest substitution problem w.r.t. an ideal in $\mathbb{Z}[x_1,\ldots, x_n]$, and establish hardness results using functional fields.