could crack code
Technology Research News
Knowledge that electrical engineers have
gained from laying out components on circuit boards could make it easier
to coax DNA molecules to do computations. The result may make it possible
to crack a code that requires 3,000 years to solve on today's computers.
use the same type of molecules that make up the genetic code for all life
on earth and are potentially very powerful because they can perform computations
on many molecules at once.
A strand of DNA is a long string of phosphates, each attached to one of
four bases: adenine, cytosine, guanine and thymine. Various types of enzymes
can cut the long molecules in places where the bases appear in a certain
order, causing the strands to reassemble. This setup can be co-opted to
perform the logic of computing.
Researchers have already plotted the minimum requirements needed to build
a DNA computer. This involves a set of standard DNA molecules, or tiles,
that each handle two inputs and two outputs. The tiles compute by interacting
with each other, and the answer is extracted from the resulting structural
Researchers from Ruhr University in Germany and Accenture Technology Labs
in France are proposing to redesign the DNA tiles that make up a DNA computer
to look more like the layout of an electronic circuit.
"Because the computation is done through the spatial arrangement of DNA
tiles, you have to be really careful in the way you design your tiles,"
said Andre Weimerskirch, a graduate student at Ruhr University. "It turns
out that the schoolbook layout of an electronic circuit designed to perform
multiplication can be easily translated into a design for DNA tiles,"
These more complicated tile designs, which the researchers equate to DNA
programming, would make DNA computers easier to use, Weimerskirch said.
"To make it simple, imagine a jigsaw puzzle. There's only one way [the
pieces] all fit together, because there are rules governing their matching,"
he said. The DNA tiles are similar to the pieces of a jigsaw puzzle. "Your
knowledge of the problem is encoded in the pieces, and the results of
the computation is the whole jigsaw puzzle. The beauty is that you don't
need to assemble the jigsaw puzzle yourself, it self-assembles," he said.
The researchers designed a multiplication tile, then went on to design
even more complicated tiles. "We realized that we could do even more complicated
operations... with few modifications," Weimerskirch said.
In theory, the design could be used to break a strong public key encryption
system in a couple of days rather than the 3,000 years it would take an
electronic computer, said Weimerskirch. The key needed to decrypt the
NTRU Cryptosystems, Inc. encryption scheme is one in a very large number
of possibilities: around 1,460 billion billion billion billion billion,
which can also be represented as 2 to the 160th power.
The DNA computing scheme is fast; in addition, it can find an answer without
having to try every number until one fits, according to Weimerskirch.
Using the different types of tiles, the researchers can logically cut
down on the possibilities in order to reduce the number that must be weeded
out using brute force. This is essentially a type of programming. "The
design of our tiles gives us the flexibility to... program the attack.
The type of programming we can do is still rather crude, but we think
this is... an important step in the right direction," said Weimerskirch.
There are several hurdles to carrying out the scheme on real DNA, according
to the researchers.The first step is to make DNA tiles that conform to
the designs. "This should not be too difficult and is within the reach
of current technology," said Weimerskirch. The second challenge has to
do with the error rate, he said. "We're currently performing simulations
that will hopefully help us understand the problem better and hopefully
allow us to give advice to the experimentalists" who may want to carry
out the scheme, he said.
The researchers are also looking to find new tile designs that will solve
even more complex problems, Weimerskirch said.
Doing computations using self-assembly is a very powerful method, said
Nadrian Seeman, a chemistry professor at New York University. "The work...
takes advantage of the notion of computation by self-assembly. However,
the work remains a theoretical suggestion and its ultimate value will
depend on its experimental implementation," he said.
It looks feasible to build tiles like the researchers have suggested,
however, said Seeman. "We're not at this time building tiles exactly like
those suggested by the authors, but we may well be able to do so in the
foreseeable future," he said.
Because DNA computing is inherently more powerful than electronic computing,
it could eventually be applied to many difficult problems like scheduling
and cryptanalysis, said Weimerskirch. It is likely to take at least five
years to overcome the experimental hurdles, he said.
Weimerskirch's research colleague was Oliver Pelletier of Accenture Technology
Labs. The research was funded by Accenture Technology Labs.
Timeline: 5 years
TRN Categories: Biological, Chemical, DNA and Molecular
Computing;Cryptography and Security
Story Type: News
Related Elements: Technical paper, "Algorithmic Self-assembly
of DNA Tiles and Its Application to Cryptanalysis," posted on the arXiv
physics archive at http://xxx.lanl.gov/abs/cs.CR/0110009.
DNA could crack code
Molecule connects contacts
PC immortalizes ancient
Laser boosts liquid computer
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link