Nondeterministic Algorithm for Breaking Diffie-Hellman Key Exchange using Self-Assembly of DNA Tiles
Keywords:
Modular multiplication, Discrete logarithm, Nondeterministic, Diffie- Hellman, Key exchange, Self-assembly, DNA tilesAbstract
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.
References
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. http://dx.doi.org/10.1016/j.jpdc.2005.05.018
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. http://dx.doi.org/10.1016/j.jco.2010.03.001
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. http://dx.doi.org/10.1080/10020070412331343781
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. http://dx.doi.org/10.1146/annurev.biophys.27.1.225
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. http://dx.doi.org/10.1021/ja9900398
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. http://dx.doi.org/10.1021/nl052038l
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. http://dx.doi.org/10.1038/35035038
Y. Brun, Arithmetic computation in the tile assembly model: addition and multiplication, Theoretical Computer Science, Vol. 378, pp. 17-31, 2006. http://dx.doi.org/10.1016/j.tcs.2006.10.025
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. http://dx.doi.org/10.1016/j.tcs.2007.07.051
Y. Brun, Solving NP-complete problems in the tile assembly model, Theoretical Computer Science, Vol. 395, pp. 31-36, 2008. http://dx.doi.org/10.1016/j.tcs.2007.07.052
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. http://dx.doi.org/10.1145/359340.359342
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. http://dx.doi.org/10.1090/S0025-5718-1987-0866109-5
G. Blakley, A computer algorithm for calculating the product A*B mod M, IEEE Transactions on Computers, Vol. C-32, pp. 497-500, 1983. http://dx.doi.org/10.1109/TC.1983.1676262
T. Acar, B.S. Kaliski, C. Koc, Analyzing and computing Montgomery multiplication algorithms, IEEE micro, Vol. 16, pp. 26-33, 1996. http://dx.doi.org/10.1109/40.502403
W. Diffie, M.E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol. 22, pp. 644-654, 1976. http://dx.doi.org/10.1109/TIT.1976.1055638
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. http://dx.doi.org/10.3724/SP.J.1016.2008.02116
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. http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x
E. Marcelo Kaihara, T. Naofumi, A hardware algorithm for modular multiplication/division, IEEE Transactions on Computers, Vol. 54, pp. 12-21, 2005. http://dx.doi.org/10.1109/TC.2005.1
P.L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, Vol. 44, pp. 519-521, 1985. http://dx.doi.org/10.1090/S0025-5718-1985-0777282-X
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
