# How can DNA Computing solve very complex problems that are present in cryptography?

This field was originally founded by Leonard Adelman of the University of Southern California in 1994. He proved the use of DNA as a computational form that solved the Hamiltonian problem.

By parallel search, it aims to solve some of the very complex problems that appear in cryptography.

How can it solve such complex problems?

The problem is scaling. Donald Beaver, looked at the factoring numbers with DNA. $$10^3$$-bit number will require $$10^{20000}$$ test tubes by using the Hamiltonian path idea of Adleman.

Adleman, also, observed that DES key search for 256 keys would occupy only a small set of test tubes. Let say $$2^4$$ tubes for $$2^8$$ keys. As a result we need $$2^{56} / 2^{8} * 2^{4} = 2^{52}$$ test tubes.

The previous statements are from previous DNA computing works directly on Cryptography. There are new studies on computing with DNA;

• There is a promising technique, called CRISPR9 with many version that enables editing DNA even at home.
• There is also interesting work called BLADE, where authors built 113 circuits from DNA.
• And, the DNS USB memory, MinION.

Under these and other new improvements in DNA computing, in the very near future, one may come up with new results affecting Cryptography.

Update: How the Hamiltonian DNA computing is performed;

1. Encode the vertices with DNA and together with Watson-Crick complement. e.g. ;

ATLANTA DNA name ACTTGCAG complement TGAACGTC and

BOSTON DNA nameTCGGACTG complement AGCCTGAC.

Here note that ACTT is considered as the first name and GCAG is considered as the surname. 2. The Edges defined as GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name 3. Polymerases step; this gene produces the complimentary copies. 4. Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA). 4. Polymerase Chain Reaction; used to remove all paths not starting from starting node and not ending with the end node. 5. Gel-Electrophoresis, when current is applied the negatively charged DNA molecules start to move to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length. 6. DNA synthesis. The DNA info was extracted.

As one can see, the process is completely biological, except Gel-Electrophoresis which is not a part of the DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. More detail can be found here.

Hamiltonian path to Factorization

Now, let talk about how the Hamiltonian Path problem can be turned into a factorization problem that Donald Beaver used. This is mostly from, normally the reduction is mentioned in the famous Introduction to Algorithms book of Cormen at. al.

• Build a non-deterministic polynomial-time Turing machine; given an $$n$$ and $$k$$ accepts if there exists some $$m$$ where $$1 and m divide n, or rejects otherwise.
• For each query $$(n,k)$$, by the Cook/Levin reduction to construct a boolean circuit which is satisfiable iff the Turing machine accepts $$(n,k)$$.
• Reduction from Circuit-SAT to 3-SAT.
• Reduction 3-SAT to Hamiltonian Path.
• Solve the Hamiltonian Path problem with DNA.

Reductions are answer-preserving, so backward available.

This is the process that Donald Beaver looked into and said

Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomial-time. This impossible task does, fortunately, expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to follow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.

• 2^52 test tubes is small?! Sep 26, 2018 at 10:20
• Very big, indeed. Sep 26, 2018 at 10:24
• @MeirMaor I know diddly squat about DNA computing. But isn't DNA smallish? So could a test tube be small too? Like microscopic, such as silicon based computing circuits? Sep 26, 2018 at 11:38
• No, test tubes are not microscopic. And 2^52 test tube would require approximately the area of South Africa. Sep 26, 2018 at 13:15
• Not computing, but storage. youtube.com/watch?v=tBvd7OSDGgQ Sep 26, 2018 at 13:16