Information-Theoretically and Computationally Secure Key Agreement in Cryptography

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.