Cryptography Reference
In-Depth Information
f s ( σ 2 σ 1 )= f 10 (01) = G 0 ( G 1 (10)) = 11 .
To compute this value, we must first compute G 1 (10) = 10 (i.e., the last
two bits of G (10) = 1110)andthen G 0 (10) = 11 (i.e., the first two bits of
G (10) = 1110). Hence, the output of the PRF is 11.
If the PRBG G ( s ) is cryptographically secure, then the function f s as defined
earlier can be shown to be a PRF. Considering the fact that s is an element
n ,
the set of all functions f s yields a PRF family. The efficiency of this PRF family
mainly depends on the efficiency of the underlying PRBG (i.e., the PRBG-based
PRFs are efficient if the underlying PRBG can be implemented efficiently).
{
0 , 1
}
13.3
RANDOM ORACLE MODEL
In Section 1.2.2, we introduced the notion of provable security and mentioned
that the random oracle methodology is frequently used to design cryptographic
systems (typically security protocols) that are provably secure in the so-called
random oracle model. The methodology was proposed by Mihir Bellare and Philip
Rogaway in the early 1990s to provide “a bridge between cryptographic theory
and cryptographic practice” [2]. In fact, they formalized a heuristic argument that
was already expressed in [1, 3, 4]. The random oracle methodology consists of the
following steps: 1
First, an ideal system is designed in which all parties (including the adversary)
have access to a random function (or a random oracle, respectively).
Second, one proves the security of this ideal system.
Third, one replaces the random function with a PRF (e.g., a cryptographic
hash function) and provides all parties (again, including the adversary) with a
specification of this function.
As a result, one obtains an implementation of the ideal system in the real
world. Bellare and Rogaway showed the usefulness of this methodology to design
and analyze the security properties of asymmetric encryption, digital signature, and
zero-knowledge proof systems. Meanwhile, many researchers have used the random
oracle model to analyze the security properties of various cryptographic systems
used in practice. Note, however, that a formal analysis in the random oracle model
is not a security proof (because of the underlying ideal assumption) but that it still
1
In some literature, steps 1 and 2 are collectively referred to step one.
Search WWH ::




Custom Search