Fast hash functions and convolution product

Abstract

We propose a new simple and efficient family of hash functions based on matrix-vector multiplications with a competitive software implementation. The hash design combines a hard mathematical problem based on solving a system of linear equations with special-random requirements and the fast computation of the convolution product algorithm. Such a mixing was often unrealizable. For security, the one-way and collision resistant criteria are based on the fact that inverting the compression function for random values is infeasible in reasonable time. In a subsequent result, we conjecture a general framework for producing secure matrix multiplication hash functions.

Keywords

• hash functions
• knapsack hash
• toeplitz hash
• swifft
• fft
• 94a60
• 11t71