Can DNA computing to solve elliptic curve algorithms using this method The authors of this paper: Fast Parallel Molecular Algorithms for DNA-Based Computation: Solving the Elliptic Curve Discrete Logarithm Problem over $GF(2^n)$ proposed a novel algorithm based on DNA computing which they claim (in theory, at least) can solve elliptic curve algorithms in polynomial time. 

An excerpt from the article:


  "We have constructed the algorithm above for parallel computing the point of the sum of two points. Then, we can solve the elliptic curve discrete logarithm problem as follows: consider point P and Q are given, and l is what we want to get which matches Q = lP. First, we amplify P into two tubes and add P in one tube. Check if 2P equals to Q; if not, note down the value of 2P and pour two tubes together. Then, amplify the tube into two tubes and add 2P in one tube. Check if any point equals to Q; if not, note down the value of 4P and pour two tubes together, or we get the value of l. Then, amplify the tube into two tubes and add 4P in one tube,…, while this loop executes n times, the value from 1 to 2n for l will have been checked, and the elliptic curve cryptosystem has been broken by the solved elliptic curve discrete logarithm problem."


I'm just starting to learn cryptography as a hobby, so I'm not too familiar with it yet. Can someone explain their strategy to me in simpler terms? Is their strategy practical in real life? The authors claim they can solve elliptic curve algorithms "in polynomial time" but I'm not so sure......
TL:DR; The algorithm is working in parallel, however not practical due to the number of DNA strands requirements for safe-curves. Generic Discrete logarithm algorithms can easily beat this, [see here].



The algorithm

The algorithms work in theory. The authors use $Q =lP$ let change it $Q = [x]P$.

Their method, actually, is highly parallelized like any DNA algorithms. DNA algorithms are actually very good at parallelization.

Let call their algorithm amplify-and-double-and-add;

t1 = P / here t is tube

while x not found:
   t1.amplify()   
   t2.amplifyWith(t1)
   t1.add(t1)
   if t1 contains Q
     return matched value
   t1 = pour(t1,t2)


As one can see, the algorithm actually calculates the intermediate values, too. The while loop requires $\lfloor(\log x)\rfloor +1 \in \mathcal{O}(\log n)$-steps. The addition is performed by the AddTwoNode algorithm that requires $O(n^3)$ extract operations, $O(n^3)$ append operations, $O(n^3)$ merge operations, and $O(n)$ test tubes for parallel adder for elliptic curve.

The $n$ is the extension number of the Binary Galois Field $GF(2^n)$  under consideration. Therefore for a curve like Edwards25519 we have $n=255$


$\approx 2^{24}$ extract operations
$\approx 2^{24}$ append operations
$\approx 2^{24}$ merge operations
$\approx 2^8 $ test tubes.


The private random key $x$ is also around 255-bit $\approx 2^{8}$. Then in total the amplify-and-double-and-add requires;


$\approx 2^{32}$ extract operations
$\approx 2^{32}$ append operations
$\approx 2^{32}$ merge operations
$\approx 2^{16} $ test tubes (?).


The notes from the conclusion of the article


  so it is feasible in theory and inspirits the development of DNA computing. This indicates that the elliptic curve cryptosystems are perhaps insecure if the technique of DNA computing is skillful enough to run the algorithms efficiently as discussed in this paper.


Considerations

DNA computing is started with Adleman's novel work, or see here. The Adleman almost has written all the steps clearly since they performed a real experiment. In this article, there is no experiment or any calculations about it. I've looked for but couldn't find one, either.

This work is clearly a theoretical work and doesn't calculate anything about the timings or amounts of DNA computing. For example;


For example, a PCR can take around 1 hour, and it's not clear how many iterations are required by the algorithm?
How scales this algorithm is not clear. Now in practice, a test tube can contain $2^{18}$ DNA strands
The number of required DNA strands is not explained/calculated. What is the last tube's requirement for the final step? We can simply say that, if it was good it was in the paper.
how much their algorithm is requiring for a curve like edwars25519 is not calculated.
The timing of test tube operations - Extract, Merge, Amplify, Append, and Append-head- are not given.
Written in 2008 and has only 18 citations according to Google Scholar. That is too low for real groundbreaking work.
The timings of their 7 algorithms are not given at least the current stage of the technology when the article was written. Adleman spent 7 days in the lab for a graph with 7 cities and took 54 seconds.


The required number of DNA strands

Let call $\text{D-SPACE}$ for the required DNA strands for the running of any algorithm. The amplify-and-double-and-add algorithms in any step calculates values between $[2^k,2^{k-1}]$, while $1&lt;k\leq x$.

Let forget about the intermedia steps and concentrate on the last step. We need around $2^{555}\text{-D-SPACE}$ so that all values can appear in the tube to be matched with $x$. This amount is too bighugehumongous even a little less than than the number of particles in the universe; and that is $3.28 \times 10^{80} \approx 2^{266}$.

The Conclusion

Not practical due to the $2^{555}\text{-D-SPACE}$ for a curve Edwards25519 or even 128-bit curves.