Multiplicative Complexity and Circuit Optimization Problems with Applications in Cryptography

Lecturer: Nicolas T. Courtois (University College London, UK).

About the lecturer | Course Summary | Slides: 1 2 | Assignment

About the lecturer: Nicolas T. Courtois was born in Poland. He he has studied pure mathematics and computer science at Ecole Normale SupŽrieure and Paris 6 University. He holds an advanced master degree in both pure mathematics and in computer science. He has received his PhD in Algorithmics/Cryptography from Paris 6 University in 2001. then he worked as a cryptographic engineer for 8 years for Gemalto, the biggest smart card and secure hardware manufacturer in the world. He has 7 patents on industrial applications of cryptography. He currently is a Senior Lecturer at University College London. His research interests are applied and industrial cryptography, smart cards, algebraic cryptanalysis, and automated problem solving. He has published nearly 50 peer-reviewed papers, with 4 major papers with 500+ citations each, he has 4000 citations total. His h-index is 29. There were some 50 press and media reports about his research in a dozen of countries. In June 2003 New Scientist put a title "Cipher Crisis" on the first page and dedicated a 4-pages paper to his research about the security of the U.S. encryption standard AES. He is responsible for the cryptanalysis of many real-life ciphers used by hundreds of hundreds of millions of people every day, such as the Bluetooth cipher E0, the automobile cipher KeeLoq and the MiFare Classic Crypto-1 system which is widely used in public transportation and building access control. Dr. Courtois has served on more than 30 program committees such as CANS, IMA CC, ACISP, WEIS, Asiacypt, ACNS, FSE, etc. In 2012 he has obtained the best paper award at Computation Tools.

Course summary: This course will be a patchwork of special yet related topics from algebra, combinatorial optimization, algorithms, cryptography and cryptanalysis. Not very theoretical, on the contrary. We focus on practical applications and solving practical problems with "software solvers" in practice.

One of the most famous combinatorial optimization problems in algebra and in computer science is the problem of Multiplicative Complexity: how many multiplications are needed to compute a certain function? This question goes back to early 19th century and has a very substantial footprint in computer science. It is closely related to the complexity of many algorithms used by millions of people every day: in implementation of important cryptographic algorithms, when solving large linear algebra problems such as Google page ranking, in code breaking, etc. Interestingly solving just once for all a certain combinatorial optimization problems can lead to asymptotically faster fundamental algebraic/graph/language/cryptanalysis algorithms. More generally, how many gates of certain type are needed to compute a certain function? In our approach this kind of problems can be solved by formal coding and SAT solvers, though it it remains very difficult. Formal coding and SAT solvers are also used to break ciphers by software, and methods are quite similar. For problems we can solve or hope to solve soon practical applications are: efficient implementation of cryptographic schemes in silicon and in software, synthesis of secure implementations of cryptographic algorithms, automated cryptanalysis of block ciphers with SAT solvers, and many other.

We will look at selected questions in cryptanalysis of ciphers with emphasis on two fundamental problems in cryptanalysis:

  1. How to optimize and "algebra-ize" a cryptographic scheme?
  2. How to exploit high-level self-similarity to cryptanalyse a composition of permutations?
We will study very selectively some components and the structure of the following well-known block ciphers: AES, GOST and PRESENT.

Assignment: The problem set is here.
Please send your solutions (pdf) to Nicolas T. Courtois (e-mail given in the problem set) or to Bartek Klin (klin AT[you-know-what]) by 31 January, 2013.