Search

Let N = {n1, n2, ..., nk} be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation gn1, gn2, ..., gnk, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of ni,1 ≤ i ≤ k. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences. [ABSTRACT FROM AUTHOR]

Summary: The problem of designing efficient parallel algorithms to calculate the product of n numbers when the multipliers are large is a fundamental problem in many applications of computer science such as cryptography. In this work, we present a new parallel algorithm on exclusive read shared memory model. The performance of the introduced algorithm is measured based on three factors, namely, (1) the number of cores, (2) the size of the array, and (3) the size of the multiplier. The experimental study on a multi core system reveals that the introduced algorithm is faster than the best‐known optimal parallel algorithm. The improvement of the proposed algorithm in processing time compared to the best known parallel algorithm is 80% when the size of the array was 220 and the sizes of the multiplier were 1024, 2048, and 4096 bits. Moreover, our algorithm is a highly scalable parallel algorithm compared with the best‐known optimal parallel algorithm. [ABSTRACT FROM AUTHOR]

Let h and (f, g) be the public and private keys of NTRU respectively. We present a new lattice to attack NTRU when the private polynomial g has one or more consecutive coefficients which are equal zeros, i.e., zero patterns. The target vector of the new lattice contains the private polynomial f, and the ratio between the size of the target vector and the expected size of a shortest non-zero vector in the new lattice is smaller than the ratio declared in the previous results. The zero patterns are not necessarily of the same or long lengths. Experimental results show that our attack succeeded to cryptanalyze NTRU faster than the previous attacks. [ABSTRACT FROM AUTHOR]

Multiplication is one of the basic operations that influence the performance of many computer applications such as cryptography. The main challenge of the multiplication operation is the cost of the operation as compared to other basic operations such as addition and subtraction, especially when the size of the numbers is large. In this work, we investigate the use of the window strategy for multiplying a sequence of large integers to design an efficient sequential algorithm in order to reduce the number of bit-multiplication operations involved in multiplying a sequence of large integers. In our implementation, several parameters are considered and measured for their effect on the proposed algorithm and the best-known sequential algorithm in the literature. These parameters are the size of the sequence of integers, the size of the integers, the size of the window, and the distribution of the data. The experimental results prove the effectiveness of the proposed algorithm are compared to the ones of the best-known sequential algorithm, and the proposed algorithm is able to achieve a reduction in computing time greater than 50% in most cases. [ABSTRACT FROM AUTHOR]

The aim of this paper is to generalize some results on addition chains to addition-multiplication chains. The paper concerns with generating shortest addition-multiplication chains. It first presents two methods for generating short addition-multiplication chains. Second, it presents an algorithm for generating a shortest addition-multiplication chain. Then it proposes three main improvements for generating a shortest addition-multiplication chain. The practical results show that the proposed improvements reduce, on the average, the running time and storage of the algorithm by about 95% and 35% respectively for data range 12 - 20 bits. Similar practical results are obtained for generating all shortest addition-multiplication chains. Finally, the paper discusses how to apply the algorithm to obtain some results that have been uncovered previously. [ABSTRACT FROM AUTHOR]