Cryptography Reference
In-Depth Information
it for the construction, the underlying ideas of which are more transparent in papers
such as [20] and [175]. Actually, we suggest presenting a variant on the signature
scheme of [175], using collision-free hashing (cf. [58]) instead of universal one-way
hashing (cf. [175]). This allows one to present, within a few lectures, many impor-
tant paradigms and techniques (e.g., the refreshing paradigm, authentication trees, the
hashing paradigm, and one-time signature schemes). We believe that the draft available
online [100] provides sufficient details for such a presentation.
A basic treatment of message authentication (i.e., motivation, definition, and con-
struction based on pseudorandom functions) can be presented within one lecture,
and [100] can be used for this purpose too. (This, however, will not cover alternative
approaches employed toward the construction of more efficient message-authentication
schemes.)
B.3. Cryptographic Protocols: Brief Summary
A general framework for casting cryptographic (protocol) problems consists of speci-
fying a random process that maps
n
inputs to
n
outputs. The inputs to the process are to
be thought of as local inputs of
n
parties, and the
n
outputs are their corresponding local
outputs. The random process describes the desired functionality. That is, if the
n
parties
were to trust each other (or trust some outside party), then each could send its local input
to the trusted party, who would compute the outcome of the process and send each party
the corresponding output. The question addressed in this section is the extent to which
this trusted party can be “emulated” by the mutually distrustful parties themselves.
B.3.1. Definitions
For simplicity, we consider the special case where the specified process is deterministic
and the
n
outputs are identical. That is, we consider an arbitrary
n
-ary function and
n
parties that wish to obtain the value of the function on their
n
corresponding inputs.
Each party wishes to obtain the correct value of the function and prevent any other
party from gaining anything else (i.e., anything beyond the value of the function and
what is implied by it).
We first observe that (one thing that is unavoidable is that) each party can change
its local input before entering the protocol. However, this is also unavoidable when the
parties utilize a trusted party. In general, the basic paradigm underlying the definitions
of
secure multi-party computations
9
amounts to saying that situations that may occur
in the real protocol can be simulated in an ideal model (where the parties can employ
a trusted party). Thus, the “effective malfunctioning” of parties in secure protocols is
restricted to what is postulated in the corresponding ideal model. The specific definitions
9
Our current understanding of the definitional issues is most indebted to the high-level discussions in the
unfinished manuscript of [165]. A similar definitional approach is presented in [11, 12]. The approach of [122] is
more general: It avoids the definition of security (w.r.t a given functionality) and defines instead a related notion
of protocol robustness. One minimalistic instantiation of the definitional approach of [165, 11, 12] is presented
in [45] and is shown to satisfy the main conceptual concerns.
