1
$\begingroup$

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 in cryptography.

How can it solve such complex problems?

$\endgroup$
5
$\begingroup$

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 considered as the first name and GCAG 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).
  5. Polymerase Chain Reaction; used to remove all path not starting from starting node and not ending with the end node.
  6. Gel-Electrophoresis, when current applied the negatively charged DNA molecules start to moves to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length.
  7. DNA synthesis. The DNA info extracted.

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

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. A 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<m<k$ and m divides 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 polynomialtime. 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 fallow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 2^52 test tubes is small?! $\endgroup$ – Meir Maor Sep 26 '18 at 10:20
  • 1
    $\begingroup$ Very big, indeed. $\endgroup$ – kelalaka Sep 26 '18 at 10:24
  • 1
    $\begingroup$ @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? $\endgroup$ – Paul Uszak Sep 26 '18 at 11:38
  • 5
    $\begingroup$ No, test tubes are not microscopic. And 2^52 test tube would require approximately the area of South Africa. $\endgroup$ – Meir Maor Sep 26 '18 at 13:15
  • 1
    $\begingroup$ Not computing, but storage. youtube.com/watch?v=tBvd7OSDGgQ $\endgroup$ – kelalaka Sep 26 '18 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.