In a landmark paper, Len Adleman showed that DNA can be used to perform computation at the molecular level when he solved a small instance of the Directed Hamiltonian Path problem. Richard Lipton soon adapted Adleman's techniques into a more general method for performing bitwise computation using DNA. This talk discusses how one can apply Lipton's approach to the daunting task of breaking the federal Data Encryption Standard (DES) cryptosystem.
I will first briefly discuss the fundamentals of DNA structure and function, followed by a description of some common molecular biology procedures that will be used to manipulate DNA for our purposes. I will then introduce Lipton's method for circuit evaluation and show how to apply it to the DES circuit.
We will close the discussion with a survey of the pitfalls one can encounter in a DNA computer, and I will describe our ongoing experiments in the biology laboratory.
This is joint work with Dan Boneh, Richard Lipton, and Ted Cox.