On Key Distribution Systems

This work proposes relaxed criteria for the security of KDS, and presents a system which meets most of the criteria, and gives evidence that one of the variants has super-polynomial security against any malicious adversary, assuming RSA modulus is hard to factor.

Abstract

Zero Knowledge (ZK) theory formed the basis for practical identification and signature cryptosysems (invented by Fiat and Shamir). It also was used to construct a key distribution scheme (invented by Bauspiess and Knobloch); however, it seems that the ZK concept is less appropriate for key distribution systems (KDS), where the main cost is the number of communications. We propose relaxed criteria for the security of KDS, which we assert are sufficient, and present a system which meets most of the criteria. Our system is not ZK (it leaks few bits), but in return it is very simple. It is a Diffie-Hellman variation. Its security is equivalent to RS A, but it runs faster. Our definition for the security of KDS is based on a new definition of security for one-way functions recently proposed by Goldreich and Levin. For a given system and given cracking- algorithm, I, the cracking rate is roughly the average of the inverse of the running-time over all instances (if on some instance it fails, that inverse is zero). If there exists a function s:N→N, s.t. for all I, the cracking-rate for security parameter n is O (1)/s(n), then we say that the system has at least security s. We use this concept to define the security of KDS for malicious adversary (the passive adversary is a special case). Our definition of a malicious adversary is relatively restricted, but we assert it is general enough for KDS. This restriction enables the proof of security results for simple and practical systems. We further modify the definition to allow past keys and their protocol messages in the input data to a cracking algorithm. The resulting security functi on is called the "amortized security" of the system. This is justified by current usage of KDS, where the keys are often used with cryptosystems of moderate strength. We demonstrate the above properties on some Diffie-Hellman KDS variants which also authenticate the parties. In particular, we give evidence that one of the variants has super-polynomial security against any malicious adversary, assuming RSA modulus is hard to factor. We also give evidence that its amortized security is super-polynomial. (The original DH scheme does not authenticate, and the version with public directory has a fixed key, i.e. zero amortized security.)