Hash functions, program secrets and lattices

In this talk we focus on two lattice-based works.

Our first result is a worst-case reduction from the set of all hash functions to a worst-case variant of the Short Integer Solutions (SIS) problem, that we call constrained-SIS. This implies that finding collisions in any hash function reduces to finding collisions for the constrained-SIS problem. This demonstrates that lattices-based techniques are quite powerful, and resolves an open problem from [Papadimitriou '94]. Our work leaves open many interesting questions. First, is there a worst-to-average reduction from constrained-SIS to SIS? This would imply that SIS is as hard to break as any other hash function, in the average case. Moreover, can we reduce the task of finding collisions in any hash function, to finding short lattice vectors of length close to the Minkowski bound?

Our second result is a construction of program obfuscation for a large and expressive class of evasive programs that we call, Compute-and-Compare (CC). A CC program tests whether f(x) = y, for a value of y that looks random enough and is proven secure under the Learning-with-Errors (LWE) assumption. We show both positive and negative applications of our obfuscation scheme. Specifically, we show a generic upgrade from attribute-based encryption to predicate encryption, and we give the first counterexample for circular security of a public-key bit encryption scheme under standard assumptions.

Based on joint works with Daniel Wichs, Katerina Sotiraki and Manolis Zampetakis.