The Taub Faculty of Computer Science Events and Talks

A collision resistant hash function is a function that compresses the input, yet it is computationally infeasible to find two inputs on which it has the same output. Collision resistant hash functions are widely used for making digital signatures efficient and have many other applications in cryptography. The talk will discuss the question of minimizing the complexity of collision resistant hash functions, where complexity is measured in terms of algebraic degree, circuit size, or locality. In particular, we will describe a construction that uses degree-3 polynomials over GF(2) to compress the input by a constant factor, where collision resistance is implied by the conjectured intractability of finding a low-weight codeword in a random linear code.