Public-Key Encryption Schemes from Different Assumptions

by Benny Applebaum, Boaz Barak and Avi Wigderson.

Oded's comments

The point of this work is seeking alternative computational problems on which public-key encryption schemes can be based. The different problems used here are of combinatorial flavor, as opposed to problems coming from the domain of number theory and algebra. Much of the work is devoted to studying various version of these problems, presenting average-case reductions among them. The problems are related, at varying levels, to my candidate one-way functions based on expander graphs.

The original abstract

I will talk about recent attempts for constructing public-key encryption schemes that are based on the average-case hardness of combinatorial problems like Constraint Satisfaction Problems (e.g., 3XOR) and graph problems (e.g., densest sub-graph problem).

Back to list of Oded's choices.