Public-Key Encryption Schemes from Different Assumptions
by Benny Applebaum, Boaz Barak and Avi Wigderson.
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).
list of Oded's choices.