Lattice Attacks on Digital Signature Schemes

We describe a lattice attack on the Digital Signature Algorithm (DSA) when used to sign many messages, m_i, under the assumption that a proportion of the bits of each of the associated ephemeral keys, y_i, can be recovered by alternative techniques.     

On the Security of the Digital Signature Algorithm

We present a key-recovery attack against the Digital Signature Algorithm (DSA). Our method is based on the work of Coppersmith [7], and is similar in nature to the attacks of Boneh et al. [5,9] which use lattice reduction techniques to determine upper bounds on the size of an RSA decryption exponent under which it will be revealed by the attack. This work similarly determines provable upper bounds on the sizes of the two key parameters in the DSA for which the system can be broken. Specifically if about half of the total number of bits in the secret and ephemeral keys, assuming contiguous unknown bits in each key, are known, the system can be shown to be insecure. The same technique shows that if about half of the total number of bits in two ephemeral keys are known, again assumed contiguous unknown bits in each key, but with no knowledge of the secret key, the system can be shown to be insecure.     

Communication-Computation Trade-off in Executing ECDSA in a Contactless Smartcard

Emerging standards specify a communication rate between a contactless smartcard and a terminal that is of the same order of magnitude as the internal clock rate in the card. This gives a natural ground for the known card-terminal communication-computation trade-off, where non-secure operations should rather be performed by the terminal and not in the card. In this paper we treat an implementation of Elliptic Curve Digital Signature Algorithm (ECDSA), the most cost effective digital signature algorithm, which has a potential of being executed under the heavy constraints imposed by a contactless smartcard environment. This algorithm heavily relies on numerous calculations of modular multiplicative inverses. It is shown in this paper that, based on communicating with the terminal, each modular inverse operation needed to be executed in the card during ECDSA signature generation requires only two modular multiplications in the card. Each modular inverse operation performed during signature verification requires only one modular multiplication in the card. A complete ECDSA implementation over integers or over GF(2ⁿ) is then treated in detail AMS Classification: 94A62     

模块化可靠性系统的Signature计算方法研究

系统Signature是体现结构设计优良性的一组向量,描述系统设计对系统故障率的影响,在诸如系统可靠性指标分析、系统设计、系统寿命比较、寿命极限行为以及系统设计优化等方面展现出了强大的功能,成为可靠性研究领域越来越强有力的研究工具。而如何求解一个系统的Signature往往成为分析的关键一步,当系统庞大而复杂时,Signature计算难度将随着元件数目的增加呈指数增加,出现维数爆炸问题,这无疑对后续的分析造成巨大的障碍. 本文为了解决此问题,建立了基于模块化思想的系统Signature求解方法,并给出了基于模块化思想的模块化串、并联系统与模块化备份系统的求解方法,对比于传统算法,运用模块化思想大大减少了计算Signature的复杂度,能够有效减小计算量,缩减计算时间,并拓展了可求解Signature的系统范围。     

Generic Groups,Collision Resistance,and ECDSA

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudorandomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public keys are mapped into the private key space. For completeness, a brief survey of necessary security conditions is also given. Some of the necessary conditions are weaker than the corresponding sufficient conditions used in the security proofs here, but others are identical. Despite the similarity between DSA and ECDSA, the main result is not appropriate for DSA, because the fourth condition above seems to fail for DSA. (The corresponding necessary condition is plausible for DSA, but is not proved here nor is the security of DSA proved assuming this weaker condition.) Brickell et al. [Vol. 1751 of Lecture Notes in computer Science, pp. 276--292], Jakobsson et al. [Vol. 1976 of Lecture Notes in computer Science, pp. 73--89] and Pointcheval et al. [Vol. 13 of Journal of Cryptology, pp. 361--396] only consider signature schemes that include the ephemeral public key in the hash input, which ECDSA does not do, and moreover, assume a condition on the hash function stronger than the first condition above. This work seems to be the first advance in the provable security of ECDSA.AMS classification: 94A60Supported in part by a National Science and Engineering Research Council of Canada Industrial Research Fellowship.     

Cycle detection for secure chaos-based encryption

Digital generators of chaos present several limitations that affect the vulnerability of chaotic encryption systems, among the most important are degraded probability distribution and short cycle lengths. Periodic perturbations of the chaotic parameter and/or state variable have been employed to deal with these limitations, although blindfold; the periodicity of the perturbation is set up during the initialization process without reference to the cycle length of the chaotic map under consideration. For best results, the periodicity of the perturbation must be close to the actual cycle length. So far, it is analytically impossible and numerically impractical (for real-time applications) to have a priori information of the cycle length. In this work we propose an on-the-fly detection and quantification of the chaotic cycle length to eliminate short cycles (which make cryptosystems vulnerable to attacks) and maximize the strength of long cycles by perturbing the system at the right time. Our proposal consists of two algorithms: (1) Unrestricted Search Algorithm (USA), which tracks down the cycle without any assumption or restriction on the digital chaotic trajectory, and (2) Ergodic Search Algorithm (ESA), which assumes ergodic trajectories to reduce the cycle search space, without this being a necessary requirement for the analyzed trajectory. USA and ESA are intended to increase the security of chaotic encryption systems without compromising their performance. Furthermore, they can be employed for the development of new chaotic-map independent encryption systems, where a full knowledge of the map is not required.     

Convergence of nonstationary multisplitting methods using ILU factorizations

In this paper, we first study convergence of nonstationary multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations for solving a linear system whose coefficient matrix is a large sparse H-matrix. We next study a parallel implementation of the relaxed nonstationary two-stage multisplitting method (called Algorithm 2 in this paper) using ILU factorizations as inner splittings and an application of Algorithm 2 to parallel preconditioner of Krylov subspace methods. Lastly, we provide parallel performance results of both Algorithm 2 using ILU factorizations as inner splittings and the BiCGSTAB with a parallel preconditioner which is derived from Algorithm 2 on the IBM p690 supercomputer.     

蚂蚁算法和小生境遗传算法的融合

蚂蚁算法是一种新型的模拟进化算法,也是一种随机型智能搜索算法.较为系统的总结了算法的基本理论,分析了其基本算法解决TSP问题的模型,针对蚂蚁算法易出现停滞的缺点,把小生境遗传算法和蚂蚁算法融合,仿真比较实验结果表明优于基本蚂蚁算法.     

扭化的Atiyah-Singer算子(I)

本文证明黎曼流表上的ｄｅ Ｒｈａｍ以及Ｓｉｇｎａｔｕｒｅ算子都同构于扭化的Ａｔｉｙａｈ－Ｓｉｎｇｅｒ算子。这两类算子的局部指数定理和局部Ｌｅｆｓｃｈｅｔｚ不动点公式都可以从扭化的Ａｔｉｙａｈ－Ｓｉｎｇｅｒ算子得到。     

扭化的Atiyah-Singer算子(Ⅰ)

本文证明黎曼流形上的deRham以及Signature算子都同构于扭化的Atiyah－Singer算子.这两类算子的局部指数定理和局部Lefschetz不动点公式都可以从扭化的Atiyah-Singer算子得到．     

基于乌鸦喝水的元启发式优化算法

启发式优化算法已成为求解复杂优化问题的一种有效方法,可用于解决传统的优化方法难以求解的问题.受乌鸦喝水寓言故事启发,提出一种新型元启发式优化算法—乌鸦喝水算法,首先建立了乌鸦喝水算法数学模型;其次,给出实现该算法的详细步骤;最后,将该算法用于基准函数优化,并将该算法与乌鸦搜索算法、粒子群优化算法、多元宇宙优化算法、花授...     

On-line version of Rabinovitch theorem for proper intervals

We analyze the on-line dimension of semi-orders as a two-person game between Algorithm and Spoiler, in a customary way. The game is played in rounds. Spoiler presents a collection of intervals representing a semi-order, one interval at a time. Algorithm maintains its realizer, i.e., the set of linear extensions intersecting the semi-order presented so far. Each time a new interval is presented, Algorithm inserts it into all maintained linear extensions and is not allowed to change the ordering of the previously introduced elements. Reading carefully the theorem of Rabinovitch on dimension of semi-orders one can prove that Algorithm needs only 3 linear extensions when Spoiler presents intervals of unit length. With the introduction of proper intervals, however, Algorithm can be forced to use one more extension. We prove that the value of the game on proper intervals is exactly 4.     

Weak greedy algorithms[*]This research was supported by National Science Foundation Grant DMS 9970326 and by ONR Grant N00014‐96‐1‐1003.

Theoretical greedy type algorithms are studied: a Weak Greedy Algorithm, a Weak Orthogonal Greedy Algorithm, and a Weak Relaxed Greedy Algorithm. These algorithms are defined by weaker assumptions than their analogs the Pure Greedy Algorithm, an Orthogonal Greedy Algorithm, and a Relaxed Greedy Algorithm. The weaker assumptions make these new algorithms more ready for practical implementation. We prove the convergence theorems and also give estimates for the rate of approximation by means of these algorithms. The convergence and the estimates apply to approximation from an arbitrary dictionary in a Hilbert space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bijective soft set decision system based parameters reduction under fuzzy environments

Gong et al. (2010) and Xiao et al. (2010) have proposed the notion of bijective soft set and exclusive disjunctive soft set, respectively, which is a subtype of soft set. On the basis of their work, this paper extends these notions to fuzzy environments, and formulates the concept of bijective fuzzy soft set, which can deal with more uncertain problems. Moreover, this paper proposes two parameters reduction algorithms: one (Algorithm 1) is based on bijective fuzzy soft system, and the other (Algorithm 2) takes weight of an element into consideration. Since the threshold plays an important role in these algorithms, we proposed an algorithm (Algorithm 3) to decide the optimal value of threshold specially. Afterwards, an example analysis of the two parameters reduction algorithms is given and the result shows that the two algorithms lead to the same parameters reduction of a bijective fuzzy soft system. Since Algorithm 2 considers the detail weights of elements, thus it can be used in more uncertain problems, such as time series analysis problems, than Algorithm 1.     

The Hurwitz determinants and the signatures of irreducible representations of simple real Lie algebras

The paper deals with the real classical Lie algebras and their finite dimensional irreducible representations. Signature formulae for Hermitian forms invariant relative to these representations are considered. It is possible to associate with the irreducible representation a Hurwitz matrix of special kind. So the calculation of the signatures is reduced to the calculation of Hurwitz determinants. Hence it is possible to use the Routh algorithm for the calculation.     

Theoretical analysis of steady state genetic algorithms

Evolutionary Algorithms, also known as Genetic Algorithms in a former terminology, are probabilistic algorithms for optimization, which mimic operators from natural selection and genetics. The paper analyses the convergence of the heuristic associated to a special type of Genetic Algorithm, namely the Steady State Genetic Algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite Evolutionary Algorithms, conditions are given under which the SSGA heuristic converges to the population consisting of copies of the best chromosome.     

Cascading Multilevel Finite-Element Analysis for Local and Nonlocal Parabolic Problems

In this article, several cascading multilevel finite-element algorithms are considered to discretize nonlinear parabolic problems, of which the nonlinearity has either local or nonlocal form. Algorithm I solves only a stationary linear system of equations at each level of P1 finite element spaces, while Algorithm II works on the coupling of a stationary linear system of equations with a linear parabolic equation. The convergence orders of Algorithms I and II are both O(h _J ) in the energy norm; in Algorithm I the estimation depends on the number of grids, while Algorithm II does not. Algorithm III is based on Picard linearization techniques and Algorithm IV on Newton iteration. Both algorithms have convergence order—O(h _J ).     

Properties of two DC algorithms in quadratic programming

Some new properties of the Projection DC decomposition algorithm (we call it Algorithm A) and the Proximal DC decomposition algorithm (we call it Algorithm B) Pham Dinh et al. in Optim Methods Softw, 23(4): 609–629 (2008) for solving the indefinite quadratic programming problem under linear constraints are proved in this paper. Among other things, we show that DCA sequences generated by Algorithm A converge to a locally unique solution if the initial points are taken from a neighborhood of it, and DCA sequences generated by either Algorithm A or Algorithm B are all bounded if a condition guaranteeing the solution existence of the given problem is satisfied.     

Some remarks on greedy algorithms

Estimates are given for the rate of approximation of a function by means of greedy algorithms. The estimates apply to approximation from an arbitrary dictionary of functions. Three greedy algorithms are discussed: the Pure Greedy Algorithm, an Orthogonal Greedy Algorithm, and a Relaxed Greedy Algorithm.This research was supported by the Office of Naval Research Contract N0014-91-J1343.     

Fireworks algorithm framework for Big Data optimization

This paper presents a novel optimization framework based on the Fireworks Algorithm for Big Data Optimization problems. Indeed, the proposed framework is composed of two optimization algorithms. A single objective Fireworks Algorithm and a multi-objective Fireworks Algorithm are proposed for solving the Big Optimization of Signals problem “Big-OPT” which belongs to the Big Data Optimization problems class. The single objective Fireworks Algorithm adopts a modified search mechanism to ensure rapidity and preserve the explorative capacities of the basic Fireworks Algorithm. Afterward, the algorithm is extended to handle multi-objective optimization of Big-OPT with a supplementary special sparks phase and a novel strategy for next generation selection. To validate the performance of the framework, extensive tests on six EEG datasets are performed. The framework is also compared with several approaches from recent state of the art. The study concludes the competitive performance of the proposed framework in comparison with the other techniques reported in this paper.