Hard Instances for Satisfiability and Quasi-one-way Functions

  • Andrej Bogdanov ,
  • Kunal Talwar ,
  • Andrew Wan

Innovations in Computer Science (ICS) |

Published by Tsinghua University Press

We give an efficient algorithm that takes as input any (probabilistic) polynomial time algorithm A which purports to solve SAT and finds, for infinitely many input lengths, SAT formulas ! and witnesses w such thatA claims ! is unsatisfiable, butw is a satisfying assignment for ! (assumingNP !” RP). This solves an open problem posed in the work of Gutfreund, Shaltiel, and Ta-Shma (CCC 2005). Following Gutfreund et al., we also extend this to give an efficient sampling algorithm (a “quasi-hard” sampler) which generates hard instance/witness pairs for all algorithms running in some fixed polynomial time. We ask how our sampling algorithm relates to various cryptographic notions. We show that our sampling algorithm gives a simple construction of quasi-one-way functions, a weakened notion of standard one-way functions. We also investigate the possibility of obtaining pseudorandom generators from our quasi-one-way functions and show that a large class of reductions that work in the standard setting must fail.