Score:1

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

cn flag

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.

enter image description here

(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.

kelalaka avatar
in flag
Challenger's coin flipping is not available to the adversary ( generating the key and selecting left or right, etc). Accessing the oracles depends on the level of the adversary. The Oracle there represent the access of the system like they are a malicious client that can ask encryption and sign any document from the company's server ( or persons that has the access) etc..
Score:0
cn flag

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.

Score:0
cn flag

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.

Chandler avatar
cn flag
Hi, thanks. For "the adversary has access to the encryption/decryption oracle", does the adversary have to know the secret key? If the adversary does not know the secret key but has access to the encryption/decryption query (he may guess the key), can we still say the adversary can do a chosen plaintext attack or chosen ciphertext attack?
cn flag
The adversary does not have the secret key. The secret key is hard coded in to the oracles by the challenger. The oracle knows the secret key, accepts messages from the adversary and perform encryption/decryption.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.