Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's called the Fiat-Shamir heuristic; it's a nice trick to make non-interactive zero knowledge proofs.
Before getting to Fiat-Shamir, consider how your favorite basic zero-knowledge proof works. Since this is Crypto SE, not CSTheory SE, hopefully you are thinking about proving knowledge of discrete logarithms and quadratic residues, not graph isomorphisms or 3-coloring graphs. ;)
[Aside: technically these are not true zero-knowledge proofs, they are honest-verifier zero-knowledge proofs (sometimes called $\Sigma$-protocols) but we don't care about that distinction here]
Schnorr's proof of knowledge of a discrete logarithm
$P$ (for prover) comes along with two values $g$ and $y$ in some group $\mathbb{G}_q$ where the discrete logarithm is hard. She claims: I know the value $x$ such that $y=g^x$. As $x$ is the discrete logarithm of $y$ base $g$, computing $x$ directly is infeasible so $V$ (verifier) cannot initially be sure if she really knows $x$ or not.
The Schnorr protocol lets $P$ prove knowledge of $x$ to $V$ in a way that does not disclose anything about $x$. It goes as follows:
- $P$ generates a random value $a$, computes $b=g^a$, and sends $b$ to $V$
- $V$ generates a random value $c$ and sends $c$ back to $P$
- $P$ computes $d=a+cx$ and sends $d$ to $V$
- $V$ accepts $\langle b,c,d\rangle$ as proof for $\langle g,y \rangle$ iff $g^d=by^c$
Security Analysis
We can ask ourselves, what do you we want in terms of security from such a protocol? $V$ is concerned that sending a bunch of numbers back and forth might not actually constitue a proof that $P$ knows such an $x$. If he can actually conclude that $P$ must know $x$ if $P$ can produce many accepting $\langle b,c,d\rangle$ transcripts, the proof is said to be sound.
$P$ may be concerned that $V$ might learn some information about $x$ from seeing one or more accepting transcripts. This is supposed to be a proof that leaks zero information about $x$ (glossing over the honest verifier technicality). If it leaks zero information, it is said to be zero-knowledge.
Soundness (via Extraction)
To show the Schnorr protocol is sound, we are actually going to do it indirectly. We are first going to show it is something called "extractable" and then show that extractability implies soundness. I'm not going to give actual definitions or proofs, just a sketch of what is going on.
Schnorr protocols have a special soundness property (called, you guessed it, special soundness): if there are two accepting transcripts $t_1=\langle b,c,d \rangle$ and $t_2=\langle b,c',d' \rangle$ where $t_1$ shares the same value of $b$ with $t_2$ but $c$ (and thus $d$) are different, then it is possible to calculate the value of $x$: $x=(d-d')/(c-c')$. If $P$ can reliably generate accepting transcripts, then there is no reason to suppose she couldn't generate $t_1$. Likewise $t_2$. And if she can produce both, then she "knows" $x$ in the sense that the knowledge required to produce $t_1$ and $t_2$ is sufficient to produce $x$ itself.
When we eventually get to Fiat-Shamir, it will be important to have formalized this notion of "extractability" a little bit. Consider the situation where $P$ is a compiled binary program instead of a person. You can run $P$ which will perform the protocol and you can rewind $P$ to a previous internal state, but you can't decompile it or look at the internal state (this is called rewindable blackbox access; why these special powers are allowed in proving extractability is a topic for another time).
We say that a protocol is extractable if you can get $x$ from interacting with such a black box. And we say a protocol is sound if it is extractable in this way (a blackbox that you can rewind). Both of these propositions have proofs in the literature with lots of fine-print I am omitting. Note that you can prove soundness in other ways than extractability or other flavours than blackbox-rewindable extractability (extractability is sufficient but not necessary).
For Schnorr, it should be obvious how, but you do the following:
- Let $P$ output $b$
- Give $P$ a random $c$ as input
- Let $P$ output $d$
- Rewind $P$ to after step 1 and before step 2
- Give $P$ a different random $c'$ as input
- Let $P$ output $d'$
- Compute $x$ from $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$
Zero-knowledge (via Simulation)
Similarly, we can indirectly prove the protocol is zero-knowledge by showing it has a different property: simulatability. In this case, we get a compiled binary of $V$ and have to reliably supply it with acceptable $b$ and $d$ values for the $c$'s it gives us. However the protocol is for knowledge of an $x$ we do not actually know! If we can simulate acceptable protocol runs without knowing $x$, then the values in the protocol must not really be leaking any information about $x$. So if the protocol is simulatable in this regard, then it is zero-knowledge.
I mentioned before that Schnorr is not actually a zero-knowledge protocol. This creates some problems with simulating Schnorr transcripts that will get resolved when we use a random oracle with Fiat-Shamir. To simulate Schnorr protocols, we do the following:
- Generate random value $d$
- Guess the value of $c$
- Supply $b=g^dy^{-c }$ as input to $V$
- Let $V$ output $c'$
- If $c'\neq c$ (you guessed wrong), rewind to step 2. Else continue
- Supply $d$ to $V$ which will accept
If the values of $c$ are really short (say a bit), then the simulator is efficient. For longer values, you can't prove the zero-knowledgeness of Schnorr with this method. There are a handful of tricks to convert Schnorr into something that is true zero-knowledge.
Fiat-Shamir Heuristic
Reading the above, you might do a double-take: on one hand, you can show that $x$ must be known if transcripts accept and on the other, you can generate transcripts that accept without $x$: what gives? If you look closely, you'll see that the simulated transcripts are generated out of order while the extractable ones are generated in order. In fact, by generating out of order, we cannot produce $\langle b,c,d \rangle$ and $\langle b,c',d'\rangle$ transcripts since the value of $b$ is no longer being chosen: it is determined by $d$ and $c$.
The idea of Fiat-Shamir is to make Schnorr (and related) protocols non-interactive. This means $P$ can produce all three values $\langle b,c,d \rangle$ instead of relying on $V$ to provide $c$. Furthermore, since we know transcripts are simulatable, $P$ can produce a value of $c$ that has to have been generated after the value $b$ thus ruling out any simulation. How? It is really easy actually: set $c=\mathcal{H}(b)$. The verifier additionally checks that $c=\mathcal{H}(b)$. [Aside: there is actually a neat optimization here where you don't have to send the value $b$ at all but leave that aside].
Finally we can introduce random oracles. It turns out that if you use regular hash functions, you can't wrestle extractability or simulation out of the protocol. We'll try but ultimately we will require a random oracle that can be programmed.
Extraction with Fiat-Shamir heuristic
Recall that extraction relies on pairs of transcripts like $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$. With Fiat-Shamir, $c=\mathcal{H}(b)$ so if the values of $b$ between two transcripts are identical, then $c$ and thus $d$ will be as well. Therefore, we cannot get two such transcripts with a regular deterministic hash function. But if $\mathcal{H}$ is a programmable random oracle, we can get it to produce different values for the same input. Once again, we play the game of having rewindable blackbox access to $P$ but this time we also get the random oracle:
- Let $P$ generate $b$
- See $P$ query $O$ with $b$ for $\mathcal{H}(b)$
- Generate random $c$ and program $c=\mathcal{H}(b)$ in $O$
- Let $O$ answer query
- Let $P$ compute $d$
- Let $P$ output $\langle b,c,d \rangle$
- Rewind to end of step 2
- Generate random $c'$ and program $c'=\mathcal{H}(b)$ in $O$
- Proceed as before and eventually let $P$ output $\langle b,c',d' \rangle$
A few notes: (1) because this is non-interactive, $P$ does not output $b$ after step 1, so we rely on the ability to see queries to the random oracle; (2) if the oracle generates answers "on the fly" (instead of entering the protocol with a codebook of all queries/responses), we don't actually have to program it with different values of $c$. We just rewind to before the point it is about to generate a response and let it generate a random value (which will overwhelmingly be different than in the first execution). This sheds some light on the original poster's third question.
Simulation with Fiat-Shamir
Similarly to extraction, the use of a random oracle makes simulation a breeze. Assuming you've read this far, you can probably see how so I will just say it in a sentence: Set a random value for $c$, compute $\langle b,c,d \rangle$ by choosing $d$ first, and when the verifier checks with the oracle that $c=\mathcal{H}(b)$, program $c$ as the response.
