Cryptography Reference

In-Depth Information

Computational limitations:
Typically, we consider computation-

ally-bounded adversaries (e.g., probabilistic polynomial-time

adversaries). However, the private-channel model allows for

the (meaningful) consideration of computationally-unbounded

adversaries.

We stress that, also in the case of computationally-unbounded

adversaries, security should be defined by requiring that for

every real adversary, whatever the adversary can compute after

participating in the execution of the actual protocol is com-

putable
within comparable time
by an imaginary adversary par-

ticipating in an imaginary execution of the trivial ideal proto-

col (for computing the desired functionality with the help of

a trusted party). That is, although no computational restric-

tions are made on the real-model adversary, it is required that

the ideal-model adversary that obtains the same impact does

so within comparable time (i.e., within time that is polyno-

mially related to the running time of the real-model adver-

sary being simulated). Thus, any construction proven secure in

the computationally-unbounded adversary model is (trivially)

secure with respect to computationally-bounded adversaries.

Restricted adversarial behavior:
The parameters of the model

include questions like whether or not the adversary is “adap-

tive” and “active” (where these terms are discussed next).

Adaptive versus non-adaptive
: The most general type of an

adversary considered in the literature is one that may corrupt

parties to the protocol while the execution goes on, and does so

based on partial information it has gathered so far (cf., (37)).

A somewhat more restricted model, which seems adequate in

many settings, postulates that the set of dishonest parties is

fixed (arbitrarily) before the execution starts (but this set is,

of course, not known to the honest parties). The latter model

is called
non-adaptive
as opposed to the
adaptive
adversary

discussed first. Although the adaptive model is stronger, the

author believes that the non-adaptive model provides a reason-

able level of security in many applications.