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


Low-Complexity Collision Resistant Hashing
event speaker icon
Naama Haramaty, M.Sc. Thesis Seminar
event date icon
Thursday, 8.9.2016, 14:30
event location icon
Taub 601
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.
[Back to the index of events]