Biological Cryptosystem And DNA Computing Of Cryptologcial Problems

Since Adleman’s pioneering research that showed DNA can be used to solve the Hamiltonian path problem, many researchers have explored the ability of biological molecules to perform computation. The power of DNA computing lies in its massive inherent parallelism, which provides potential advantages compared to conventional methods.With the development of DNA computing, biological cryptography becomes a new branch of cryptography. The security of conventional modern cryptography relies on hard computational problems, such as discrete logarithm problem and prime factorization. However, with the development of computing technology, if the computational problems we assume hard can be solved e?ciently in the future, the cryptosystems that rely on these computational problems can be broken. By contrast, the security of DNA cryptography relies on hard biological problems. Such schemes are immune to attacks of new computing technologies in the future, thus providing another level of security.The ?rst part of this dissertation focuses on DNA computing of cryptologcial problem. One of the most important assumptions in modern cryptography is the hardness of the discrete logarithm problem. Several algorithms in public-key cryptography, such as Di?e-Hellman key exchange scheme, El Gamal cryptosystem, etc., base their security on the assumption that the discrete logarithm problem has no e?cient solution. If e?cient solution can be found in the future, the security of the cryptosystems based on discrete logarithm problem will be threatened. Taking advantage of the massive inherent parallelism of DNA computing, in this dissertation we propose a new algorithm which solves discrete logarithm problem in polynomial time. The main results are summarized as follows:1- Using the tile assembly DNA computing model, we propose SDLP, a selfassembly system nondeterministically solving discrete logarithm problem in polynomial time. Given binary integers a, p, y, SDLP?nds x which satis?es ax≡ y(mod p).Our system randomly determines the order of executing the corresponding subsystems,nondeterministically selects x, computes axmod p for different x and compares the results with y in parallel. For np-bit modulo p, the worst-case assembly time of our system is O(n3p). Compared with pre-existing system whose assebmly time is O(2np),our system achieved signi?cant time-e?ciency improvement.2- We propose two new multiplier systems, both can deterministically compute A ? B for given A and B in linear time. Our ?rst system requires 24 computational tile types while our second system requires 16 tile types, which achieve smaller constants than Brun’s 28-tile multiplier system.3- We propose a system computing A mod B for given nA-bit binary integer A and nB-bit binary integer B, which is the ?rst system directly solving the modulus problem in tile assembly model. The worst-case assembly time of our system is Θ(nA(nA-nB))and the best-case assembly time is Θ(nA). Compared with the pre-existing division system, we achieved improved time complexity in our system. Our advantage is more signi?cant if nAis much greater than nB.4- Pre-existing multiplier system can not be executed directly on the ?nal con-?gurations of other subsystems, thus multiplier system can not be used to compute f(x) = g2(x) during the whole process. We propose a square system which can be executed directly after execution of other subsystems. As a result, all of the subsystems can be executed continuously without interruption.5- We present a DNA modular subtraction algorithm based on linear self-assembly,the biochemical experimental procedures can be accomplished in constant number of steps.The second part of this dissertation focuses on DNA-chip-based cryptosystems and related special features. Our main results are summarized as follows:1- We present DNA-PKC, which is the ?rst exploration of the DNA-chip-based asymmetric encryption system. The security of our scheme relies on hard biological problems, i.e. it is di?cult to precisely obtain all molecular information of mixed sequence-speci?c unknown DNA probes spotted on a DNA chip, thus our schemes are immune to attacks of new computing technologies in the future.2- We explore the special feature of DNA-PKC, i.e. the set of encryption keys and the set of decryption keys have a many-to-many relationship. Taking advantage of this feature, we present DNA-DBE, a DNA-chip-based dynamic broadcast encryption scheme, which is the ?rst exploration of the DNA-based group-oriented cryptosystem.Either the ciphertext or the decryption key is of constant-size. DNA-DBE also enjoys backward secrecy, which is not achieved in conventional dynamic broadcast encryption system3- DNA-PKC provides another special feature: for different messages which are of identical length, the corresponding ciphertext can be identical. As a result, we present DNA-IH, which is the ?rst DNA-chip-based information hiding scheme. Conventional information hiding process changes the statistical properties of the original data. The existence of secret messages embedded can be detected using statistical steganalysis schemes. In DNA-IH, for secret message and ordinary message, the corresponding DNA chips can be identical, thus statistical steganalysis is no longer able to detect whether or not a given DNA chip contains a secret message.