We introduce a complexity-theoretic model for studying computational security of binary image watermarking systems. Our model restricts algorithms used by the sender and the attacker to the class H of hiding functions. These are efficiently computable functions that preserve visual fidelity of the input image. Security of watermarking systems is to be established with complexity results about hiding functions. We also survey current theories of vision and propose an automata-theoretic model for visual fidelity called c-similarity. Finally we propose a candidate for H based on c-similarity and show that it is robust and contains infinitely many functions computable in polynomial time.