Fast Parallel Molecular Algorithms for DNA-Based Computation: Solving the Elliptic Curve Discrete Logarithm Problem overGF(2n)

摘要

Elliptic curve cryptographic algorithms convert inputdata to unrecognizable encryption and the unrecognizable data backagain into its original decrypted form. The security of this form ofencryption hinges on the enormous difficulty that is required tosolve the elliptic curve discrete logarithm problem (ECDLP),especially overGF(2n),n∈Z+. This paperdescribes an effective method to find solutions to the ECDLP bymeans of a molecular computer. We propose that this researchaccomplishment would represent a breakthrough for applied biologicalcomputation and this paper demonstrates that in principle this ispossible. Three DNA-based algorithms: a parallel adder, a parallelmultiplier, and a parallel inverse overGF(2n)are described.The biological operation time of all of these algorithms ispolynomial with respect ton. Considering this analysis,cryptography using a public key might be less secure. In thisrespect, a principal contribution of this paper is to provideenhanced evidence of the potential of molecular computing to tacklesuch ambitious computations.