Fast parallel DNA-based algorithms for molecular computation: discrete logarithm

摘要

Diffie and Hellman (IEEE Trans. Inf. Theory 22(6):644-654, 1976) wrote the paper in which the concept of a trapdoor one-way function was first proposed. The Diffie-Hellman public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption, and converts the unrecognizable data back into its original decryption form. The security of the Diffie-Hellman public-key cryptosystem is based on the difficulty of solving the problem of discrete logarithms. In this paper, we demonstrate that basic biological operations can be applied to solve the problem of discrete logarithms. In order to achieve this, we propose DNA-based algorithms that formally verify our designed molecular solutions for solving the problem of discrete logarithms. Furthermore, this work indicates that public-key cryptosystems based on the difficulty of solving the problem of discrete logarithms are perhaps insecure.