Nondeterministic Algorithm for Breaking Diffie-Hellman Key Exchange using Self-Assembly of DNA Tiles


  • Zheng Cheng Zhejiang University of Technology


Modular multiplication, Discrete logarithm, Nondeterministic, Diffie- Hellman, Key exchange, Self-assembly, DNA tiles


The computation based on DNA tile self-assembly has been demonstrated to be scalable, which is consider as a promising technique for computation. In this work, I first show how the tile self-assembly process can be used for computing the modular multiplication by mainly constructing three small systems including addition system, subtraction system and comparing system which can also be parallely implemented the discrete logarithm problem in the finite field GF(p). Then the nondeterministic algorithm is successfully performed to break Diffie-Hellman key exchange with the computation time complexity of Θ(p), and the probability of finding the successful solutions among many parallel executions is proved to be arbitrarily close to 1.

Author Biography

Zheng Cheng, Zhejiang University of Technology

Department of Mathematics and Computer Science


L. Pan and C. Martin-Vide, Solving multidimensional 0−1 knapsack problem by P systems with input and active membranes, Journal of Parallel and Distributed Computing, Vol. 65, pp. 1578-1584, 2005.

L. Pan and M. J. P¨Śrez-Jim¨Śnez, Computational complexity of tissue-like P systems, Journal of Complexity, Vol. 26, pp. 296-315, 2010.

L.M. Adleman, Molecular computation of solutions to combinatorial problems, Science, Vol. 266ÅŹ pp. 1021-1024, 1994.

L.Q. Pan, G.W. Liu, J. Xu, Solid phase based DNA solution of the coloring problem, Progress in Natural Science. vol. 14, pp. 104-107, 2004.

A. Carbone, N.C. Seeman, Molecular tiling and DNA Self-assembly, Springer-Verlag Berlin Heidelberg, Vol. 2950, pp. 61-83, 2004.

N.C. Seeman, DNA nanotechnology: novel DNA constructions, Annu. Rev. Biophy. Biomol. Struct., Vol. 27, pp. 225-248, 1998.

C. Mao, W. Sun, N.C. Seeman, Designed two dimensional DNA Holliday junction arrays visualized by atomic force microscopy, J. Am. Chem. Soc., Vol. 121, pp. 5437-5443, 1999.

E. Winfree, On the computational power of DNA annealing and ligation, DNA Based Computers, pp. 99-221, 1996.

T. Eng, Linear self-assembly with hairpins generates the equivalent of linear context-free grammars, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penn., 1997.

R. Barish, P.W. Rothemund, E. Winfree, Two computational primitives for algorithmic self-assembly: copying and counting, Nano Letters, Vol. 12, pp. 2586-2592, 2005.

P. M. Espane′s, A. Goel, Toward minimum size self-assembled counters, Springer Science Business Media B.V., 2008.

P.W. Rothemund, N. Papadakis, E. Winfree, Algorithmic self-assembly of DNA Sierpinski triangles, PLoS Biology, Vol. 12, pp. 2041-2053, 2004.

M. Cook, P.W. Rothemund, E. Winfree, Self assembled circuit patterns, DNA, pp. 91-107, 2004.

C. Mao, T.H. LaBean, J.H. Reif, Logical computation using algorithmic self-assembly of DNA triple-crossover molecules, Nature, Vol. 407, pp. 493-496, 2000.

Y. Brun, Arithmetic computation in the tile assembly model: addition and multiplication, Theoretical Computer Science, Vol. 378, pp. 17-31, 2006.

G.L. Michail, T.H. LaBean, 2D DNA self-assembly for satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, pp. 139-152, 1999.

Y. Brun, Nondeterministic polynomial time factoring in the tile assembly model, Theoretical Computer Science, Vol. 395, pp. 3-23, 2008.

Y. Brun, Solving NP-complete problems in the tile assembly model, Theoretical Computer Science, Vol. 395, pp. 31-36, 2008.

A. Gehani, T.H. LaBean, J.H. Reif, In DNA Based Computers: Proceedings of a DIMACS Workshop, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999.

R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, Vol. 21, pp. 120-126, 1978.

I.R. Jeong, J.O. Kwon, D.H. Lee, A Diffie-Hellman key exchange protocol without random oracles, Springer-Verlag Berlin Heidelberg, Vol. 4301, pp. 37-54, 2006.

ANSI X9.30. Public Key Cryptography for the Financial Services Industry: Part 1: The Digital Signature Algorithm (DSA), American National Standard Institute, American Bankers Association, 1997.

N. Koblitz. Elliptic curve cryptosystem, Math. Comp., Vol. 48, pp. 203-209, 1987.

G. Blakley, A computer algorithm for calculating the product A*B mod M, IEEE Transactions on Computers, Vol. C-32, pp. 497-500, 1983.

T. Acar, B.S. Kaliski, C. Koc, Analyzing and computing Montgomery multiplication algorithms, IEEE micro, Vol. 16, pp. 26-33, 1996.

W. Diffie, M.E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol. 22, pp. 644-654, 1976.

Z.H. Chen, Breaking the Diffie-Hellman key exchange algorithm in the tile assembly model, Chinese Journal of Computers, Vol. 31, pp. 2116-2122, 2008.

E. Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, Caltech, Pasadena, CA, June 1998.

P.W. Rothemund, E. Winfree, The program-size complexity of self-assembled squares, ACM Symposium on Theory of Computing (STOC), pp. 459-468, 2001.

H. Wang, Proving theorems by pattern recognition, I. Bell System Technical Journal, Vol. 40, pp. 1-42, 1961.

E. Marcelo Kaihara, T. Naofumi, A hardware algorithm for modular multiplication/division, IEEE Transactions on Computers, Vol. 54, pp. 12-21, 2005.

P.L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, Vol. 44, pp. 519-521, 1985.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.