Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
There are some classic ZKP examples out there (the alibaba cave, the colored balls, etc. See the Wikipedia page for details)
To me it looks like these protocols were invented "ad-hoc". That is, someone came up with a clever solution for that particular problem, and it's not immediately clear how it applies to other problems.
Is there a more "direct" way of coming up with a protocol? Are there situations where a ZKP is not possible?
Any statement that is checkable in P (i.e., any NP statement) can be proved in zero knowledge. This can be shown by giving a ZK proof for any NP-complete problem --- historically, 3-colorability of graphs or Hamiltonian cycle. But giving a reduction to these graph problems might seem artificial. Perhaps a better approach is to use an NP-complete problem like circuit satisfiability, which is what is suggested in:
Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently. ACM CCS 2013.
I don't know if you'll necessarily consider this more "direct", since it is only direct if you already know about oblivious transfer and garbled circuits.
Even the toy examples from wikipedia have aspects that are fairly standard to many ZK proofs: in particular, pre-commitment to some answers, a randomized challenge, and amplification.
Another good example of a not-so-cryptographic ZK proof is the graph non-isomorphism proof.
