U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

Presentation

Hash functions, program secrets and lattices

March 23, 2022

Presenters

Giorgos Zirdelis - UMD

Description

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 2002-Mar-23

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created June 29, 2022, Updated July 05, 2022