ICS 2010
|
|
Welcome to ICS2010
Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 290-300,
978-7-302-21752-7
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 ω such that A claims Φ is unsatisfiable, but w is a satisfying assignment for Φ (assuming NP 6 ? BPP). 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. Preview: 
|
Copyright 2009-2010, Institute for Computer Science, Tsinghua University, All Rights Reserved.