Narrow Results

The purpose of this paper is to suggest a new parallel algorithm for the knapsack problem. The design of the proposed parallel algorithm is based on a shared memory SIMD machine with a heap tree data structure. It can solve a general n-component knapsack problem in time O(2^n/2) with memory-processor tradeoff M²P = O(2^n/2). The proposed technique can have better performance in terms of cost as the number of processors needed can be offset by increasing memory space. The performance is compared with those of other algorithms to demonstrate its superiority. We believe that the proposed algorithm is pragmatically feasible at the moment when multiprocessor systems are gradually becoming popular.

The knapsack problem is known to be a typical NP-complete problem, which has 2ⁿ possible solutions to search over. Thus a task for solving the knapsack problem can be accomplished in 2ⁿ trials if an exhaustive search is applied. In the past decade, much effort has been devoted in order to reduce the computation time of this problem instead of exhaustive search. In 1984, Karnin proposed a brilliant parallel algorithm, which needs O(2^n/6) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Karnin's parallel algorithm is O(2^2n/3). In this paper, we propose a fast search technique to improve Karnin's parallel algorithm by reducing the search time complexity of Karnin's parallel algorithm to be O(2^n/3) under the same O(2^n/6) processors available. Thus, the cost of the proposed parallel algorithm is O(2^n/2). Furthermore, we extend this search technique to the case that the number of available processors is P = O(2^x), where x ≥ 1. From the analytical results, we see that our search technique is indeed superior to the previously proposed methods. We do believe our proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.

In recent years, a lot of chaotic cryptosystems have been proposed. However, most of these cryptosystems can encrypt only one plaintext in one encryption process. We call these cryptosystems single-plaintext-oriented cryptosystems. In this paper, the authors propose a new chaotic cryptosystem which can encrypt multiple plaintexts in one encryption process. The proposed cryptosystem is dedicated to encrypting multiple plaintexts in the situation of transmitting multiple secret files over public data communication network in one secure transmission. Experiments and theoretic analysis show that the proposed cryptosystem possesses high security and fast performance speed. They also show that the proposed cryptosystem is more secure than single-plaintext-oriented chaotic cryptosystems in this special situation.

A method of shared secret key distribution applicable to optical coherent multiplexing systems is proposed. It provides ways to detect the extent of eavesdropping. Detecting test factors and system design rules are suggested, and performance evaluation is performed in terms of mutual information between legitimate users and an eavesdropper. This scheme devises a new way of attaining secure optical communications without entirely relying on computational complexity.

There have been many ways to construct an algorithm to encrypt image. Most often the algorithms are based on DNA sequence or other methods. In this paper, we proposed a new method which is based on singular value decomposition. In this approach, we can encrypt a small portion of the data through RSA encryption algorithm. The strength of the proposed method is insured through various statistical and security analysis. It shows that the algorithm has good encryption effect and higher encryption efficiency, which can be applied to the storage and network transmission of military, medical and other digital images.

This paper proposes a fuzzy model-based chaotic encryption approach using synchronization. The cryptosystem uses T–S fuzzy models to exactly represent discrete-time chaotic systems into separate linear systems. Then the synchronization problem is solved using linear matrix inequalities. The advantages of this approach are: the general and systematic T–S fuzzy model design methodology suitable for well-known Luré type discrete-time chaotic systems; flexibility in selection of chaotic signals for cryptosystem secure key generator; and multiuser capabilities. Especially taking a chaotic superincreasing sequence as an encryption key enhances the chaotic communication structure to a higher-level of security compared to traditional masking methods. In addition, numerical simulations and DSP-based experiments are carried out to verify the validity of theoretical results.

It is said that the numerical generation of exact chaotic time series by iterating, for example, the logistic map, will be impossible, because chaos has a high dependency on initial values. In this letter, an algorithm to generate them without the accumulation of inevitable round-off errors caused by the iteration is proposed, where rational numbers are introduced. Also, it is shown that the period of the chaotic time series depends on the rational numbers including large prime numbers, which are fundamentally related to the Mersenne and the Fermat prime ones. Since the time series are numerically regenerated by the proposed algorithm in an usual computer environment, it could be applied to cryptosystems which do not need the synchronization, and have a large key-space by using large prime numbers.

A general methodology for designing chaotic and hyperchaotic cryptosystems has been developed using the control systems theory. Grassi et al. proposed a nonlinear-observer-based decrypter for the state of an encrypter. If we can design the decrypter without the knowledge of the parameters of the encrypter, the chaos-based secure communication systems are not secure. In this paper, we have designed an observer-based chaotic communication system, which allows us to assign the relative degree and the zeros of its encrypter system. Moreover, under some conditions, we have designed an adaptive decrypter using the adaptive parameter adjustment law based on a Riccati equation when the transfer function of the encrypter is of minimal-phase type. The simulations via MATLAB/Simulink suggest that the encrypter dynamics should be designed such that its relative degree is more than 2 and its zeros are unstable so as to fail to synchronize the cryptosystem for the intruders.

A Rao–Nam cryptosystem based on error correction code is proposed to provide both security and reliability. Since its security is drastically constrained by the limited error syndromes, in this paper, an improved Rao–Nam cryptosystem based on fractional order hyperchaotic system and Extended Difference Family–Quasi-Cyclic–Low-Density Parity-Check (EDF–QC–LDPC) codes is proposed to improve the security. A four-dimensional fractional order hyperchaotic system is constructed and is used to generate an excellent pseudorandom sequence. By replacing error syndromes with the pseudorandom sequence and permuting the coded message dynamically, the security of the Rao–Nam cryptosystem is enhanced greatly. The ability of the improved Rao–Nam cryptosystem against known attacks is analyzed and the error correction performance with different parameters is simulated. The results show that the proposed cryptosystem has a significant advantage of resisting the chosen-plaintext attack. Moreover, the proposed cryptosystem retains high capacity of error correction.

In this cryptosystem, we have considered RGB images for two-dimensional (2D) data security. Security of RGB images during transmission is a major concern, discussed globally. This paper proposes a novel technique for color image security by random hill cipher (RHC) over SL_n(𝔽) domain associated with 2D discrete wavelet transform. Existing techniques have discussed the security of image data on the basis of the keys only (which provide only one layer of security for image data), but in the proposed cryptosystem, the keys and the arrangement of RHC parameters are imperative for correct decryption of color image data. Additionally, key multiplication side (pre or post) with the RGB image data should inevitably be known, to correctly decrypt the encrypted image data. So, the proposed cryptosystem provides three layers of security for RGB image data. In this approach, we have considered keys from the special linear group over a field 𝔽, which provides enormous key-space for the proposed cryptosystem. A computer simulation on standard examples and results is given to support the fixture of the scheme. Security analysis, and detailed comparison between formerly developed techniques and proposed cryptosystem are also discussed for the robustness of the technique. This method will have large potential usage in the digital RGB image processing and the security of image data.

In this paper, an image encryption scheme based on reversible integer wavelet transform (IWT) with chaotic logistic map is designed. The proposed cryptosystem is applicable to encipher both the medical and natural images in lossless and lossy manners, respectively. Initially, the original image is transformed with the multilevel of IWT, then the image data set is divided into low sub-band (approximation part) and high sub-bands (detail part). The approximation part gets confused with the chaotic logistic map followed by the bit plane decomposition. Next, the individual bit planes are further diffused with several binary key metrics, generated using a chaotic logistic map. The proposed key schedule derives several large size of binary key metrics from a small size of key. Based on the type of applications, the detail part is considered for lossless/lossy compression. The lossless/lossy compressed detail part is further considered only for confusion process using the logistic map for the sake of enhancing the security level. Finally, the cipher image obtained after inverse IWT is significantly dissimilar than original image. The scheme has been tested on several standard medical and natural images and the experimental results substantiate that a small size of key is enough to protect the content of images completely. The security analysis reveals that the proposed scheme is suitable for protecting the image data effectively.

In this paper we introduce a novel cryptosystem based on finite automata without outputs. For encryption and decryption the apparatus uses the same secret keys, which have the transition matrix of a key-automaton without outputs and with an initial state and final states. To each character in the character set of the plaintext there is one or more final states of the key automaton assigned. During encryption the plaintext is read in sequentially character by character and the key automaton assigns to each plaintext character a character string, whose length is adjustable within a given length range. The apparatus creates the ciphertext by linking these character strings together. During decryption the key automaton starting from the initial state reads in the ciphertext character by character and decryption is accomplished by linking together the plaintext characters associated with certain final states, which provides the plaintext in its original form.