Information-Theoretically and Computationally Secure Key Agreement in Cryptography
Stefan Wolf
One of the central problems in cryptography is secure message transmission
over insecure channels. By the use of classical symmetric cryptosystems,
this problem can be reduced to the one of generating a secret key by insecure
communication. The security of such secret-key agreement can be based
either on the computational hardness of certain number-theoretic problems,
or on information theory. Examples of both types of key distribution
are analyzed.
In the information-theoretic model, Maurer's setting of secret-key
agreement by public discussion from common information and earlier scenarios,
based on noisy communication channels, by Wyner and by Csiszár and
Körner, are considered. It is shown that in the noisy-channel
models, as also in Maurer's model, the generated secret key can
have a much higher security level than previously believed and demanded.
By using recent results from the theory of extractors, it is shown that
such a stronger key can even be generated at the same rate as
a key that is secure only with respect to the previous, weaker definition.
Furthermore, conditions on the joint distribution of the legitimate partners'
and the adversary's knowledge are given for the possibility and impossibility
of information-theoretic secret-key agreement. In this context, a new
information measure, the intrinsic conditional information, is introduced,
and evidence is provided which suggests that this quantity is directly
connected to the possibility of secret-key agreement. The case of key
agreement secure even against active adversaries is also considered. An
efficiently-verifiable criterion is given that allows for
deciding whether such key agreement is possible at all
in a specific situation. Finally, two protocols are described for
the important special case of privacy amplification, i.e., transforming
a common partially-secret string into a virtually-secret key, in the presence
of an active adversary. The conditions for these protocols to work however
are stricter than in the passive-adversary case. Both protocols are based on
novel interactive identification and message-authentication methods requiring
only a partially-secret key. In the computational model, we consider a number
of question related to the security of the Diffie-Hellman key-agreement
protocol. For instance, the relationship between the discrete-logarithm problem,
the Diffie-Hellman problem, and the Diffie-Hellman decision problem is
studied. The security of the Diffie-Hellman protocol is directly based on
the hardness of the computational and decisional variants of the Diffie-Hellman
problem. It is shown that with respect to generic algorithms, i.e.,
general-purpose algorithms that work in any group of a certain order,
the Diffie-Hellman problem and the discrete-logarithm problem are
computationally equivalent for certain, but not for all
group orders. The Diffie-Hellman decision problem, which is to
recognize a correct solution to the Diffie-Hellman problem, is not
genericallycomputationally equivalent to the Diffie-Hellman problem
for any non-trivial group order. Finally, additional related problems
are studied with respect to generic algorithms, such as the computation of
roots in cyclic groups,or the improvement of a faulty Diffie-Hellman oracle.
In all cases, the derived lower bounds turn out to nearly match the running
times of the fastest generic algorithms. This leads to a complete
classification of the problems of interest with respect to generic algorithms.