Can DNA computing to solve elliptic curve algorithms using this method

Question

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

Answer 1

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

Answer 2

No,

DNA computing doesn't harness quantum phenomenon to achieve parallelisation/quantum speedup, DNA computing still falls under the classical classification.

Landauer's principle asserts that there is a minimum possible amount of energy required to erase one bit of information, known as the Landauer limit

Taking into account the Landauer limit on thermodynamic efficiency, practical key sizes are far too large to break in reasonable time with reasonable energy inputs.

There is further discussion on this topic recently over on this forum.

Answer 3

No, the DNA computing method in the article can not solve cryptographically interesting instances of the DLP problem. That's not ruling out that DNA computing could.

The main issue is that the method in the article is hopelessly inefficient: sure it has a number of steps linear with the key size $n$, but even in theory it uses exponentially much material: $\mathcal O(2^n\,n)$ nucleotides for storage alone (this is apparent in section 3.12, also quoted in the question, which describes the outer loop of the method). That's hopelessly much material when dealing with DLP problems of cryptographic interest.

Even for $n=117$ (below the current DLP computation record), and if we could get down to $k=100$ nucleons per bit, we need $2^n\,n\,k\approx2^{130.5}$ nucleons each $1.67\times10^{-27}$ kg, that is $\approx3\times10^{12}$ kg of material for storage alone at the end of the proposed experiment, over $100$ times the yearly meat production of USA (only a small fraction of which is DNA). And then, few deployed systems use less than $n=160$, which would require over a million million more material; and a more typical value is $n=256$.

Further, if I get it correctly, the algorithm performs at least $O(2^n\,n^3)$ chemical reactions, which is lots of energy.

Fact is, the article uses a very naive algorithm to solve the DLP: essentially, trying all $2^n$ keys, with cost $O(2^n)$ group operations. There are better algorithms, including Pollard's rho, bringing this down to $O(2^{n/2})$ group operations. I see no theoretical reason why the parallel variants of that would be much more difficult to transpose to DNA computing than what the article proposes. That, in theory, could attack sizes of cryptographic interest. I make no statement about feasibility, nor about how that would compare to modern computer technology.