Information Technology Reference
In-Depth Information
1
p
(
n
)
is less than
(one must be cautious with “suciently
large” — if it is 'nonconstructive', the notion may become useless).
The indistinguishability can be used to formulate security properties, e. g.
to express that some piece of information
for suciently large
n
w
remains secrete in an execution, we
say that any execution with
is
replaced by some other piece of the same type. However, such general notions
are not always suciently practical for the verification.
Cryptography, more precisely, the theory of multi-party protocols (see Ch. 7
of [15]) gives also a classification of parameters that permits to specify differ-
ent aspects of system behavior in the context of security: the communication
channels (private, broadcast or intermediate); set-up assumptions (what is the
initial or other input knowledge of the parties); computational limitations (usu-
ally polytime adversary or that of unlimited computational power); constraints
of adversarial behavior (adaptive or non-adaptive, passive or active, and oth-
ers); notions of security; constraint on the number of dishonest parties and some
other. A hierarchy of private-key security notions was developed in [17] for secu-
rity goal of both indistinguishability and non-malleability. Security notions for
public-key encryption are compared in [2].
One more important question that was studied in cryptography concerns
preservation of security when composing a secure protocol with other ones [7].
The importance of this question is evident for the preservation of security prop-
erties in implementations of protocols.
The notions mentioned above give ideas how to formalize other contexts and
aspects of security. For example, paper [18] and later papers of the same authors
apply the indistinguishability notion and probabilistic polytime attacks in order
to incorporate probabilistic arguments into cryptographic protocol analysis on
an abstract level.
w
is indistinguishable from executions where
w
4 Protocols
Fault-tolerance of distributed algorithms has a long history. Some questions,
that are of security nature, were studied in this field as fault-tolerance in the
presence of Byzantine agents whose behavior is assumed to be the worst possible
with respect to the correct agents. If the channels are private (secure) there are
many algorithmic and complexity results not involving cryptography nor any
intractability conjectures, for example Byzantine consensus, clock synchroniza-
tion — e. g. see [26]. However, problems of this type are rather marginal for
the security, as they are relevant to situations when many agents participate
simultaneously.
Another research domain concerning protocols, is the domain of multi-party
protocols that are studied in cryptography, see Ch. 7 of [15]. The initial notion
to describe multi-party protocols is that of random process describing a func-
tionality; it is a random function mapping
outputs. Randomness
becomes crucial when the question of security of the involved cryptography be-
comes central.
M
inputs on
M
