基于N进制的DNA并行加法与乘法模型

现有DNA数值计算模型大多在二进制基础上进行计算,通用性不强。针对该问题,设计基于N进制的DNA自装配并行加法与乘法模型。在Labean模型的基础上,加法模型通过改进库分子的编码方式将DNA算法的时间复杂度降为O(1),空间复杂度降为O(n);乘法模型在解决一位数连加问题后,转换为相应的加法模型进行计算。实验结果表明,该并行模型编码简单,具有较低的时间复杂度和空间复杂度。     

DNA计算机算术运算的自装配模型（I）—加法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在Labean加法的基础上,设计了通用的N进制的并行加法DNA自装配模型,算法的时间复杂度为O（1）,空间复杂度为O（n）。在此基础上又设计了一位数连加的DNA自装配模型,为今后的并行乘法奠定了基础。算法的主要优点在于编码简单、效率高,且具有通用性。     

一种基于身份证书的数字签名方案设计

在分析了基本数字签名方法的基础上，本文设计并实现了基于离散对数困难问题（DLP）、辅以Hash函数和公钥证书进行签名和验证签名的数字签名方法。它在随机Oracle模式下是安全的且签名方进行签名只需要一次指数运算、一次模乘运算和一次加法运算，在线计算量则只需一次乘法和一次加法，因而是高效的且适合智能卡的应用。     

DNA计算机算术运算的自装配模型（II）—乘法

DNA计算机与传统电子计算机相比具有高度并行性、容量大、速度快等特点。它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在自装配加法的基础上,设计了DNA自装配乘法模型,算法的时间复杂度为[O(1)],空间复杂度为[O(n)],并给出实例验证了算法的有效性。该算法具有编码简单、效率高、通用性强等优点。     

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。（1）与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L, 2 L-1}; 余数系统Ω包括八个模数,它们都具有如2L－2Ki+1的形式。这种选择使其模算术变得简单。（2）在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5N·I, 其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。     

基于DNA下推自动机二进制减法和乘法的实现

提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,将低位产生的借位作为高位试管操作巾的输入符号串,从而完成高位的减法运算.两位二进制乘法中包含移位和加法操作,在两个试管中分别设计好DNA下推自动机模型,分别完成被乘数与乘数各位的移位操作,同时结合相应的生物操作,将其作为另一个试管加法操作中的输入符号串,则加法操作中产牛的结果即为所求.在此基础上,m位二进制乘法可通过移位操作的并行性和加法操作的串行性来完成运算.这些实现方法为DNA下推自动机实现基本的算术运算提供了比较完整的运算机制.     

一种基于随机混合坐标表示的防功耗分析标量乘法实现方法

提出了一种新的防功耗分析(包括简单和差分功耗分析simpleanddifferentialpoweranalysis)的椭圆曲线标量乘法实现方法,该方法实现简单,并且适合于各种不同有限域上椭圆曲线标量乘法的实现.该方法以模乘和模加减操作为最小调度单位,将标量乘法转换成完全随机的模乘和模加减操作序列;基于随机混合坐标表示实现点的加法和倍加操作,并随机地从点的加法和倍加操作序列中选取后续的模乘和模加减操作;任务调度与模乘和模加减操作的执行是并行的.另外,本文定量分析了该实现方法对于功耗分析的防护能力以及运算性能.     

DNA计算机算术运算的自装配模型(Ⅲ)—减法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在DNA自装配加法的基础上,设计了一般的DNA自装配并行减法模型,算法的时间复杂度为O(1),空间复杂度为O(n),并通过实例验证了算法的有效性。算法的主要优点在于编码简单、效率高,且具有通用性。     

Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Zp+ DNA-based Computing

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用.研究一种加群Zp+上离散对数问题的DNA计算算法.算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成.其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间.本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数).最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。     

基于DNA自组装的EIGamal系统破译

自组装DNA计算在破译密码系统方面,具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息,借助于分子瓦之间的粘性末端进行自组装,通过引入非确定性的指派型分子瓦,提出了用自组装DNA计算破译EIGamal公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦,该算法可以并行地以高概率地破译EIGamal公钥密码系统。     

Arithmetic computation in the tile assembly model: Addition and multiplication

Formalized study of self-assembly has led to the definition of the tile assembly model [Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, Caltech, Pasadena, CA, June 1998; Paul Rothemund, Erik Winfree, The program-size complexity of self-assembled squares, in: ACM Symposium on Theory of Computing, STOC02, Montreal, Quebec, Canada, 2001, pp. 459–468]. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal Θ(1)$\Theta \left(1\right)$ distinct tile types and prove the assembly time is linear in the size of the input.     

Staged self-assembly: nanomanufacture of arbitrary shapes with <Emphasis Type="Italic">O</Emphasis>(1) glues

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered. Under this assumption, traditional tile self-assembly cannot even manufacture an n × n square; in contrast, we show how staged assembly in theory enables manufacture of arbitrary shapes in a variety of precise formulations of the model.

Combining self-healing and proofreading in self-assembly

Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the high rate of error under existing experimental conditions. Recent theoretical work on algorithmic self-assembly has shown that under a realistic model of tile addition and detachment, error correcting tile sets are possible that can recover from the attachment of incorrect tiles during the assembly process. An orthogonal type of error correction was recently considered as well: whether damage to a completed structure can be repaired. It was shown that such self-healing tile sets are possible. However, these tile sets are not robust to the incorporation of incorrect tiles. It remained an open question whether it is possible to create tile sets that can simultaneously resist wholesale removal of tiles and the incorporation of incorrect ones. Here we present a method for converting a tile set producing a pattern on the quarter plane into a tile set that makes the same pattern (at a larger scale) but is able to withstand both of these types of errors.

基于D-H公钥系统前向保密的密码协议

Diffie-Hellman(D-H)算法可以实现密码系统的密钥交换,其安全性依赖于计算离散对数的难度,并且Diffie-Hellman密钥交换协议能够提供前向保密性。文中通过分析Diffie-Hellman密钥交换协议,给出了一个可以应用于任何非对称密码体制的具有前向保密的密码协议。     

基于自组装DNA计算的NTRU密码系统破译方案(英文)

自组装DNA计算在解决NP问题,尤其在破译密码系统方面,具有传统计算机无法比拟的优势．文中提出了一种用自组装DNA计算破译NTRU公钥密码系统的方法．针对NTRU密码系统的特点,采用DNA瓦片编码信息,借助于瓦片间的粘性末端进行自组装,给出了求解多项式卷积运算的实现方案．在此基础上,通过引入非确定性的指派瓦片,提出了一种破译NTRU系统的非确定性算法．通过创建数以亿计的参与计算的DNA瓦片,该算法可以并行地测试每个可能的密钥,以高概率地输出正确密钥．该方法最大的优点是充分利用了DNA瓦片具有的海量存储能力、生化反应的巨大并行性以及组装的自发有序性．理论分析表明,该方法具有一定的可行性．     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models

Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.     

Towards a neighborhood simplification of tile systems: From Moore to quasi-linear dependencies

Self-assembly is the process by which objects aggregate independently and form complex structures. One of the theoretical frameworks in which the process of self-assembly can be embedded and formally studied is that of tile systems. A Wang tile is a square unit, with glues on its edges, attaching to other tiles which have matching glues, and forming larger and larger structures. In this paper we concentrate over two basic, but essential, self-assembling structures done by Wang tiles. The first one, called ribbon, is a non-self-crossing wire-like structure, in which successive tiles are adjacent along an edge, and where tiles are glued to their predecessor and successor by use of matching glues. The second one, called zipper, is a similar contiguous structure, only that here, all touching tiles must have matching glues on their abutting edges, independently of their position in the structure. In case of Wang tiles, it has been shown that these two structures are equivalent. Here we generalize this result for the case when the tiles have eight glues, four on their edges and four on their corners. Thus we show that an eight neighborhood dependency, namely the Moore neighborhood, can be simulated by a quasi-linear dependency.