Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Low-Complexity Collision Resistant Hashing
event speaker icon
Naama Haramaty (M.Sc. Thesis Seminar)
event date icon
Thursday, 08.09.2016, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. E. Kushilevitz and Prof. Y.Ishai
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.