NEC Research Institute Technical Report 1999

Secure Short-Key Cryptosystems: Forty Bits is Enough

Samuel R. Buss and Peter N. Yianilos

Abstract: This paper discusses the use of short secret keys, as short as 40~bits or fewer, to implement secure public and private key cryptosystems. Short keys are readily memorized and do not need to be written down or stored electronically. Still, they can provide security comparable to that provided by conventional cryptosystems with much longer keys.

Our short secret key cryptosystems are based the use of slowed down key generation, as advocated by Quisquater, et al. We use a `slow one-way' function to convert a short secret key into an expanded key, which can be used in a conventional (long key) cryptosystem. Although the notion of slowdown in cryptographic systems is well-known, our analysis suggests that it is far more useful than is generally recognized.

The first contribution of this paper is the analysis of the security of short key cryptosystems and the tradeoffs between key length, amount of slowdown, and security. An important aspect of our analysis is the identification of the advantages of extremely slow slowdown functions for key generation. The second contribution is the inclusion of an auxiliary, nonsecret key; which we argue is necessary to maintain security, and also allows a single short key to be used for multiple independently secure communication sessions, and to be used as a master key in key management protocols.

Keywords: Cryptography, Key Management.