Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


Hash functions, program secrets and lattices

March 23, 2022


Giorgos Zirdelis - UMD


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.

Presented at

Crypto Reading Club talk on 2022-Mar-23

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created June 29, 2022, Updated September 13, 2022