  In recent years much effort was put into developing polynomial-time
conditional lower bounds for algorithms and data structures in both static and
dynamic settings. Along these lines we suggest a framework for proving
conditional lower bounds based on the well-known 3SUM conjecture. Our framework
creates a \emph{compact representation} of an instance of the 3SUM problem
using hashing and domain specific encoding. This compact representation admits
false solutions to the original 3SUM problem instance which we reveal and
eliminate until we find a true solution. In other words, from all
\emph{witnesses} (candidate solutions) we figure out if an \emph{honest} one (a
true solution) exists. This enumeration of witnesses is used to prove
conditional lower bound on \emph{reporting} problems that generate all
witnesses. In turn, these reporting problems are reduced to various decision
problems. These help to enumerate the witnesses by constructing appropriate
search data structures. Hence, 3SUM-hardness of the decision problems is
deduced.
  We utilize this framework to show conditional lower bounds for several
variants of convolutions, matrix multiplication and string problems. Our
framework uses a strong connection between all of these problems and the
ability to find \emph{witnesses}.
  While these specific applications are used to demonstrate the techniques of
our framework, we believe that this novel framework is useful for many other
problems as well.
