Can I prove that I have x such that f(x) < c without revealing x?

I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob who has a powerful computer. Bob finds such an x, but he doesn't want to give it away before receiving payment from Alice, but at the same time Alice doesn't want to pay Bob before she is sure he has a sufficient value of x.

Is there a way for Bob to prove to Alice that he has such an x without revealing what the value of x is?

This can be done with a fully homomorphic encryption of f, right? For example Bob can demonstrate the equivalent inequality on the encrypted f and encrypted c for the encrypted x, and Alice can verify the encryption scheme on f and c, but this does not reveal x.

Is there any way that is less computationally expensive - even if for only certain types of functions f? Is there a partially homomorphic encryption scheme that will suffice? Or some other type of zero knowledge proof?

• Thank you D.W., i tried to add some more details. I don't really have any constraints of f right now besides that it is a real-valued function, and I am open to hearing solutions for more specific types of functions as I mentioned. Yes, I am aware of zero-knowledge proofs such as for graph colorings etc., but I have not heard of one for proving I have x such that f(x) < c. Jan 30, 2017 at 21:59

If the function $f$ is publicly known and is efficiently computable, it is possible for Bob to prove that he knows a value $x$ such that $f(x)<c$. This is known as a zero-knowledge proof of knowledge. There's lots written on zero knowledge proofs; you can go read about them.
In particular, given any predicate $\varphi(x)$ that is computable in polynomial time, there exists a polynomial-time zero-knowledge proof of knowledge that you know $x$ such that $\varphi(x)$. If $f$ can be computed in polynomial time, then the predicate $f(x)<c$ can certainly be tested in polynomial time, so it can also be proven in zero knowledge in polynomial time.