Public-key cryptography. State of the art and future directions. E.I.S.S. workshop, Oberwolfach, Germany, July 3-6, 1991. Final report (Q1202030)

This report is the result of a meeting of leading experts in the field of public-key cryptography. Although the presentation is aimed at researchers in the field as well as users of security technology, it is also accessible to non-specialists. Public-key cryptography is based on the existence of one-way functions, i.e. bijections \(\Phi\) which allow efficient computation but for which inversion \(\Phi^{-1}\) is considered computationally intractable. A prominent instance is the discrete logarithm problem; i.e. given an arbitrary element \(X\) from a cyclic group \(G\) of order \(| G|\) generated by a primitive element \(\omega\), find the unique integer \(x\in[0,| G|-1]\) with \(X=\omega^ x\). Usually \(G\) is taken to be the multiplicative group of a finite field but recently also the group of an elliptic curve over a finite field has been studied in view of the discrete logarithm problem. If this problem may be considered hard in the underlying group, exponentiation (or multiplication, depending on notation of the group law) is used to implement the Diffie-Hellman key exchange protocol in order to provide one-key cryptosystems with a key. Two-key systems are essentially one-way systems if considered by outsiders, while insiders can use the inherent trapdoor to invert the bijection \(\Phi\) in an effective way. An important instance of this case is the RSA cryptosystem. Both, the Diffie-Hellman key exchange and the RSA cryptosystem are based on the assumption that the system is secure if a problem in computational number theory is considered hard. In the two cases these are the discrete logarithm problem and the factorisation problem of (large) integers, respectively. Therefore a considerable part of the report is devoted to a survey of recent research in computational number theory. Various attacks on public-key cryptosystems are not directly based on number theory but on weaknesses due to protocol failures or inappropriate applications in a certain environment. As an alternative to the traditional way of designing cryptosystems, based on heuristics and the experience of the designer, a formal approach to cryptosystem design and analysis is outlined. Public-key cryptography will have to satisfy an increasing number of needs. Therefore an impressive list of tasks and a careful distinction between all the requirements is given. This may be a good guideline for future research in cryptography. In view of all these considerations, design criteria for a RSA chip are given which necessarily depend on the application. The report concludes with statements and predictions about the choice of parameters in implementations with respect to long lasting security.