| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Breaking the NTRU Public Key Cryptosystem Using Self-Assembly of DNA Tilings |
| Authors | ZHANG Xun-Cai1),2) NIU Ying2) CUI Guang-Zhao2) WANG Yan-Feng2) |
| Address | 1)(Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074) 2)(College of Electrical and Electronic Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002) |
| Year | 2008 |
| Issue | No.12(2129¡ª2137) |
| Abstract & Background | Abstract Computation by self-assembly of DNA is an efficient method of executing parallel DNA computing where information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations. This paper shows how the DNA self-assembly process can be used for breaking the NTRU public key cryptosystem. In order to achieve this, a method for implementing the cyclic convolution product of two polynomials using self-assembled DNA computing is expounded. Then, a non-deterministic algorithmic is provided to break efficiently the NTRU public key cryptosystem. By creating billions of billions of copies of the participating DNA tiles, the algorithmic will run in parallel on all possible private keys. The computation takes advantage of non-determinism, but theoretically, each of the non-deterministic paths is executed in parallel, yielding the solution in time polynomial in the size of the input, with high probability. It presents clear evidence of the ability of molecular computing to perform complicated mathematical operations. Keywords self-assembly; DNA tile; non-deterministic computation; NTRU; break; public key cryptosystem |