What is the relationship between "Challenger" and "Oracle" in a security proof?

Question

In game-based security proof, I found that games are defiend to be played between a PPT adversary and a challenger. The adversary is able to issue queries to different oracles and receives corresponding reponses. Assume A is the participant of the protocol, the queries sent by the adversary could be: Test(A) or hash queries.

A little explaination about Test(A) query: This query is typically used in proofing the semantic security of a key-exchange protocol. If this query is asked, A will filp a random coin 'b', if b=1, A replies the adversary with the correct session key (if formed); otherwise, a random bitstring is replied.

My question is: since games are played between adversary and challenger, does it mean the challenger has access to all the oracles (e.g., participants, hashes) and the adversary can only query the oracle through the challenger? Say, if the adversary want to issue a Test(A) query, the challenger will receive this query and pass it to participant A and transfer the received reply from A to the adversary (see image below)? It seems the challenger is a communicaiton media between the adversary and the oracles.

(Actually I'm not sure whether A in the above example could be called oracle. The concept "oracle" is also confusing to me...)

Many thanks in advance.

Answer 1

You define security via a game that is played between a challenger and the adversary and the goal for the adversary is to win the game. Oracles are capabilities that are given to the adversary, e.g., the Test oracle allows to “implement” a challenge for the adversary. All the oracles are controlled by the challenger and if you are in the random oracle model then the challenger controls the hash function, i.e., the random oracle, and usually can program the answers to this oracle (this means it can choose how to answer as long as the answers look uniformly random to the adversary and are consistent with previous queries). So actually your box around the challenger should also cover all the oracles to the left as they are controlled by the challenger.

What you do when you want to prove security, i.e., show that there cannot be an efficient adversary that wins the game with some non-negligible probability, you show that the challenger can “simulate” the entire environment, i.e., the oracles, for the adversary in a way not noticeable to the adversary but where winning the game would require the adversary to break some problem that is assumed to be hard. Therefore, in the most simple case you can build a direct reduction in that you can show that the challenger can “connect” an external challenger (for some assumed hard problem, e.g., CPA security of the encryption scheme) and e.g., forward all its Enc() queries to the external challenger, and an adversary that wins this game also wins the “external” game (thus contradicting the assumed CPA security). It can also be the case that the challenger can directly embed some hardness assumption, e.g., DDH, by receiving the instance to the problem from an external challenger, e.g., DDH challenger.

Typically in key-exchange protocols that are not only passively secure (plain DH can be shown under DDH), the security proof will work via a sequence of “hybrid games”, where one modifies the security game step by step (every step is argued to be not noticeable by the adversary based on some hardness assumption, e.g,. CPA security) until one reaches a game where the conclusion is easy. In key-exchange protocols this will typically be a transition from a variant of the game where we hardcode b=0 to a variant of the game where we hardcode b=1.

Answer 2

The concept of oracles is that it models the adversary's power. For example, for symmetric key ciphers, if the adversary has access to the encryption oracle, we say the adversary can do a chosen plaintext attack, if the adversary has access to the decryption oracle (as well as the encryption oracle), we say it can do a chosen ciphertext attack. Usually, the more oracles that the adversary can use, the more powerful it is.

It does not really matter whether the oracle query is routed through the challenger or not. Conceptually it's the same as having a direct access to the oracle that the challenger configured. You can also think of the challenger an environment and the adversary lives inside the environment and the only legal queries it can make to the environment are defined by the oracles.