Alternatives to RSA: An Overview

Since the invention of public key cryptography by Diffie and Hellman in 1976, very few public key schemes have been deployed in applications, besides the celebrated RSA algorithm designed by Rivest, Shamir, and Adleman. While millions of RSA keys are used in WEB browsers, most public key cryp-tosystems are only present in textbooks, with the noticeable exception of those based on elliptic curves, which seem to slowly make their way to the market.

There are however, several other challenging lines of research proposing public key schemes of a different flavour. Some use elliptic/hyperelliptic curves as mentioned, some are based on the computational hardness of various problems from coding theory or from the geometry of numbers. Some stem from considering the mathematical formula describing RSA as a univariate modular polynomial, and attempt to use multivariate polynomials instead. All hope to achieve a lower cost for encryption and/or decryption and/or communication.

While some of the original proposals have been shown insecure, many further schemes have been designed. In turn, these have been subject to active cryptanalytic work. The aim of the talk is to review some of the schemes, to explain some of the methods that have been used to attack them, and to assess their level of security. In other words, are these alternatives now ready for practical applications?

Yanghee Choi
Professor and Chair
School of Computer Science and Engineering
Seoul National University,...