 |
 |
|
|
Public-key cryptography was introduced in 1976 by Diffie and Hellman to allow for secure communication over insecure channels. The first practical system and the one that gained most in popularity was the RSA cryptosystem introduced by Rivest, Shamir, and Adleman in 1977. This is the most popular public-key cryptosystem in use today. Its security rests on the fact that it is hard to factor a product of two large (unknown) primes.
Recently, however, number theorists have made great strides in implementing the number field sieve in order to factor such numbers. The challenge numbers RSA-140 and RSA-155 were factored in February, 1999 and August, 1999, respectively. It is striking that it took only six months to move up 15 decimal digits (about 50 bits).
The August press release claims that about 95% of all public-key cryptosystems in use today use RSA with a 512-bit key. This, alarmingly, is the magnitude of number that can now be cracked. Admittedly, cracking RSA-155 was computationally expensive (taking 8000 Mips-years), but the business community is already turning to 768-bit RSA or 1024-bit RSA for fear of future advances in attack algorithms.
The problem with such large key lengths is that they are not applicable in constrained environments, such as smart cards. Accordingly the business community is seeking alternatives. The most popular current alternatives are the elliptic curve cryptosystems (ECC) invented by Neal Koblitz and Victor Miller in 1985 independently. The security of elliptic curve cryptography depends on our inability to solve the elliptic curve discrete logarithm problem (ECDLP) in subexponential time.
For instance, a 97-bit challenge ECC was cracked in September 1999, but took 16,000 Mips-years, about twice the computational work to crack 512-bit RSA. The method was brute force, i.e. the parallelized Pollard's rho algorithm. The most recent challenge was solved in April 2000, where the combined effort of 9500 machines solved a 109-bit Koblitz curve challenge ECC. It took four months and was about 50 times that required to solve the 512-bit RSA cryptosystem.
There have been some scares regarding the security of ECC such as xedni calculus proposed by Silverman in 1998. Silverman's approach, if valid, would have threatened all public-key cryptosystems currently in use. After a nervous few weeks this was debunked by a group of people at the Centre for Applied Cryptographic Research (CACR) in Waterloo, Canada. But some people are looking for alternatives to ECC and RSA just in case .
An alternative approach was suggested in 1998 by Gerhard Frey. He suggested analyzing elliptic curve cryptosystems with the help of Weil-descent. Gaudry, Hess, and Smart successfully applied this method to elliptic curves over composite powers of small finite fields. On the other hand, Frey's idea can be used to derive secure public-key cryptosystems, if one embeds an elliptic curve into an abelian variety and uses the arithmetic of the elliptic curve while the security depends on the security in the higher-dimensional abelian variety.
Another possibility is hyperelliptic curve cryptosystems (HCC). This was a generalization of ECC proposed by Koblitz in 1988. Again the security depends on our inability to efficiently solve the discrete log problem, the HCDLP. Indeed, the set of ECC is a subset of HCC. In HCC one works with the Jacobian of a genus g-curve over a finite field. The case g=1 is ECC since in that case the Jacobian is the same as the curve. The fact that this simple description of the Jacobian does not hold for curves of genus g>1 has apparently led people to shrink back from HCC, but there are compact ways to represent elements in the Jacobians and efficient algorithms to add and double in these groups.
On the other hand, Gaudry, who is a member of the CNRS group in Paris, showed that hyperelliptic curves of genus bigger than or equal to 5 and possibly 4 are less secure than hyperelliptic curves of genus g<4 (or 5). That means that the key-per-bit-strength of hyperelliptic curves of genus 2 and 3 is the same as for elliptic curves, and thus far better than conventional systems based on discrete logs or integer factoring. In fact, genus 2 is particularly interesting because the arithmetic appears to be only minimally slower than elliptic curve arithmetic and the bit size of the underlying finite field is half as big as for elliptic curves having the same security level. To our knowledge nobody has performed a down-to-earth implementation of genus 2 hyperelliptic curves.
Genus 3 curves might save about a third in key lengths and so 180-bit ECC (which is beyond the usual range, as given in standards) is equivalent to 60-bit HCC, which can be implemented on a fast 64-bit computer. In practice, 160-bit ECC is typically used and so there is even room for added security in case of computational speed-ups in attacks. Stein, in particular, has pointed out how the use of``real'' forms of hyperelliptic curves (i.e., with infrastructure) allows considerable speed-ups in implementation in some cases.
We are considering hardware implementations of hyperelliptic curves of genus 2 and 3 . Among the currently available hyperelliptic curves there are, for instance, Koblitz curves and curves constructed by a complex multiplication method (CM-method). Both are natural extension of ideas from elliptic curves.
Elliptic Koblitz curves are recommended in the NIST standards since arithmetic on them is extremely efficient. Tanja Lange, currently a Ph.D. student of Gerhard Frey in Essen, Germany, generalized the arithmetic on Koblitz curves and found a variety of curves suitable for hardware implementations. Annegret Weng, also a Ph.D. student of Gerhard Frey, implemented the CM-method for genus 2 curves efficiently and constructed many hyperelliptic curves suitable for cryptographic applications. She is now investigating genus 3 curves and will visit us for 2 months next year.These are examples of the kind of collaboration that we intend to pursue with Frey and his group in Germany. In addition, our weekly Information Protection Seminar has concentrated on the NTRU cryptosystem, a lattice-based system, and whether it provides a safe alternative should the systems above be compromised.
The second part of our work involves information hiding. It seems that information hiding is about as mathematically developed as with both subjects, concerning competing factors. Whereas the mathematical foundations of coding theory are well-established, the same is as yet not true for e.g. watermarking. Moulin has proposed an information-theoretic approach similar to Shannon's in coding theory, and Boston has proposed a purely mathematical basis for watermarking. There could be mathematical objects analogous to e.g. the Golay codes awaiting discovery.
Information hiding is an emerging research area which encompasses applications such as copyright protection for digital media, watermarking, fingerprinting, television broadcasting, and steganography. In particular, watermarking is now a major activity in audio, image, and video processing, and standardization efforts for JPEG-2000, MPEG-4, and Digital Video Disks are underway. Commercial products are already being developed.
The first three International Workshops on information hiding were held in 1996, 1998, and 1999. Special issues of major technical journals have recently been recently devoted to information protection, and comprehensive surveys of image and multimedia watermarking techniques are available.
Information hiding borrows from a variety of areas, including signal processing, communications, game theory, and cryptography. Indeed, a vast array of techniques from signal processing and communications have been used to design algorithms for hiding information and for attempting to remove that information (by means of techniques such as signal compression, signal warping, and addition of noise.) Perceptual models for audio, imagery, and video can be used to quantify the distortions introduced by information--hiding and attack algorithms. Game-theoretic aspects of information hiding have been explored. Cryptographic aspects of information hiding include the use of secret keys to protect the message.
It should however be clearly recognized that the functional requirements of cryptography and information hiding as described above are very different, as secrecy of the message is the main objective in cryptography but is often not a requirement in information hiding, where reliable embedding of the message within the host data is often the single most important requirement.
Moreover, while cryptography has received significant attention in the Mathematics and Information Theory communities, information hiding today is an immature subject, both on a mathematical and a technological level. For instance, there is no consensus today about the formulation of system requirements; and there is considerable uncertainty about the eventual performance of such systems, as all published algorithms in current audio and image watermarking literature can be defeated by attacks such as those in the popular freeware package Stirmark .
The research papers in the above literature have focused on novel ways to hide information and to detect and/or remove hidden information. However, these papers have lacked a guiding theory describing the fundamental limits of any information--hiding system. The need for practitioners and system designers to understand the nature of these limits has been recognized.
Hence, compared with coding theory and cryptography, information hiding is an area that is relatively untouched by mathematics but seems ripe for ``mathematization''. Moulin has recently started working in that area, and now consults with Microsoft Research to investigate fundamental limits of watermarking and authentication, and developing methods to approach these limits.