Algorithmic Self-Assembly of DNA Tiles and its Application to Cryptanalysis

O. Pelletier, André Weimerskirch

To be presented at the Genetic and Evoluationary Computation Conference 2002 (GECCO 2002), New York, July 9-13, 2002. City, USA.


Abstract

The early promises of DNA computing to deliver a massively parallel architecture well-suited to computationally hard problems have so far been largely unkept. Indeed, it is probably fair to say that only toy problems have been addressed experimentally. Recent experimental development on algorithmic self-assembly using DNA tiles seem to o er the most promising path toward a potentially useful application of the DNA computing concept. In this paper, we explore new geometries for algorithmic self-assembly, departing from those previously described in the literature. This enables us to carry out mathematical operations like binary multiplication or cyclic convolution product. We then show how to use the latter operation to implement an attack against the well-known public-key crypto system NTRU.

[pdf] [gzipped postscript]

tags: convolution product, Cryptanalysis, DNA, multiplication, NTRU, self-assembly, Wang tiles