Oracle
From CRYPTUTOR
←Older revision | Newer revision→
An oracle is a procedure which is only accessed by giving inputs and then receiving the corresponding output. In particular, no access is given to the procedure's source code or any additional (intermediate) state information. Another name for this kind of access to a procedure is black-box access.
Definition and notation
If A is an algorithm, we write Af to denote that A has oracle access to the procedure f. A may provide inputs to f and then receive the corresponding output. The running time of f is not counted against that of A -- we assume that the output of f is obtained in constant time. A may ask as many queries to f as desired, within the limits of A's running time, and its queries may be adaptive, i.e., depend on the answers to previous queries.
Black-box reductions
In cryptography, protocols and schemes are often constructed using standard, simpler primitives as their components. If a protocol for a task A can be implemented using only oracle access to a primitive B, then we say that the protocol is a black-box reduction from A to B. Black-box reductions are often desirable, since they provide extensibility in constructions and even implementation. The protocol for A can be realized by "plugging in" any implementation of B, without relying on additional properties of B or needing access to intermediate states in the computation of B.
