Polynomials in the Nation's Service: Designing the Advanced Encryption Standard

Abstract

In 1973 the National Bureau of Standards (later renamed the National Institute of Standards and Technology, or NIST) issued a call for a symmetric-key algorithm for encrypting sensitive (unclassified) information. IBM submitted the algorithm that became the Data Encryption Standard. There was immediaye concern over key length (56 bits) and the security of the design but, despite this, with the exception of RC4 in web browsers and relatively insecure cable-TV signal encryption, DES became the most widely-used public cryptosystem in the world. DES's preeminence lasted twenty-five years, but by the late 1990s it had become clear that that a new algorithm was needed. NIST issued a call for a replacement. This time the agency was much more open to a public process. The criteria for the algorithm was open for public, including international, discussion and evaluation of the candidates was public as well. To the surprise of many, the algorithm chosen was not one developed in the U.S.; Rijndael was designed by two Belgians, Joan Daemen and Vincent Rijmen. Rijndael incorporates various security principles developed over the quarter-century study of DES and related block ciphers. In this talk I will discuss the mathematics and politics of the Advanced Encryption Standard and how polynomials, which form the basis of Rijndael's security, came to be in the nation's service.