Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Because of their interesting algebraic properties, several authors promote the use of generalized Reed–Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed–Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed–Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed–Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed–Solomon code.     

Distributed source coding using chaos-based cryptosystem

A distributed source coding scheme is proposed by incorporating a chaos-based cryptosystem in the Slepian–Wolf coding. The punctured codeword generated by the chaos-based cryptosystem results in ambiguity at the decoder side. This ambiguity can be removed by the maximum a posteriori decoding with the help of side information. In this way, encryption and source coding are performed simultaneously. This leads to a simple encoder structure with low implementation complexity. Simulation results show that the encoder complexity is lower than that of existing distributed source coding schemes. Moreover, at small block size, the proposed scheme has a performance comparable to existing distributed source coding schemes.     

A Simple Generalization of the ElGamal Cryptosystem to Non-Abelian Groups

In this article we study the MOR cryptosystem. We use the group of unitriangular matrices over a finite field as the non-abelian group in the MOR cryptosystem. We show that a cryptosystem similar to the ElGamal cryptosystem over finite fields can be built using the proposed groups and a set of automorphisms of these groups. We also show that the security of this proposed MOR cryptosystem is equivalent to the ElGamal cryptosystem over finite fields.     

Lag synchronization of hyperchaos with application to secure communications

In this paper, hyperchaotic lag synchronization is restated as a nonlinear and lag-in-time observer design issue. This approach leads to a systematic tool, which guarantees the lag synchronization of a wide class of chaotic or hyperchaotic systems via a scalar signal. By exploiting this result, we propose a hyperchaos-based cryptosystem scheme that combines the conventional cryptographic methods and the lag synchronization of chaotic circuits. The computer simulation results show that the lag synchronization scheme and the cryptosystem proposed in this paper are both feasible.     

Cardinal rank metric codes over Galois rings

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application.     

Reducing the Elliptic Curve Cryptosystem of Meyer-Müller to the Cryptosystem of Rabin-Williams

At Eurocrypt '96, Meyer and Müller presented a new Rabin-type cryptosystem based on elliptic curves. In this paper, we will show that this cryptosystem may be reduced to the cryptosystem of Rabin-Williams.     

Cryptanalysis of a chaos-based cryptosystem on DSP

In this work, we cryptanalyse a recently chaos-based cryptosystem on DSP by proposing three different attacks to break it. We report the weakness of this cryptosystem and hence demonstrate that in its actual design, it cannot be used in the real world applications and it needs to be first enhanced by avoiding the design drawbacks reported in this work.     

Improvement of cryptosystem based on iterating chaotic map

In this letter we demonstrate that the improvement of cryptosystem based on iterating chaotic map proposed by Yong in 2007 are weak and this cryptosystem can be easily broken using chosen plaintext attack. Then, we give novel improvements to the proposed chaotic cryptosystem. We choose image as plaintext, some experimental tests like sensitivity on initial condition and correlation between two adjacent pixels are presented to show the performances of the new cryptosystem.     

A new chaotic cryptosystem

Based on the study of some previously proposed chaotic encryption algorithms, we found that it is dangerous to mix chaotic state or iteration number of the chaotic system with ciphertext. In this paper, a new chaotic cryptosystem is proposed. Instead of simply mixing the chaotic signal of the proposed chaotic cryptosystem with the ciphertext, a noise-like variable is utilized to govern the encryption and decryption processes. This adds statistical sense to the new cryptosystem. Numerical simulations show that the new cryptosystem is practical whenever efficiency, ciphertext length or security is concerned.     

Modified Niederreiter type of GPT cryptosystem based on reducible rank codes

GPT public key cryptosystem was proposed by Gabidulin, Paramonov and Tretjakov in 1991. This cryptosystem is based on rank error correcting codes. The main advantage of using rank codes in cryptography is that, it has smaller key size as compared to other code based public key cryptosystems. Several attacks against this system were published and some modifications were also proposed withstanding these attacks. In this paper, we have proposed a modified Niederreiter type GPT cryptosystem based on reducible rank codes by properly choosing the column scrambler matrix to withstand these attacks. Although, the idea of choosing column scrambler matrix from extension field is not new but the approach proposed in this paper, provides more elements of column scrambler matrix from extension field as compared to any previous modifications which makes system more secure against attacks.     

Cryptanalysis of the GGH Cryptosystem

In this correspondence, we show that partial information of plaintext can be used to simplify the decryption problem in the case of the GGH cryptosystem. Combined with Nguyen’s previous attack, we solve the numerical GGH challenge of the highest dimension 400, proposed on the Internet by the authors of the cryptosystem. We also discuss how to avoid this attack.     

Prior Learning and Convex-Concave Regularization of Binary Tomography

In our previous work, we introduced a convex-concave regularization approach to the reconstruction of binary objects from few projections within a limited range of angles. A convex reconstruction functional, comprising the projections equations and a smoothness prior, was complemented with a concave penalty term enforcing binary solutions. In the present work we investigate alternatives to the smoothness prior in terms of probabilistically learnt priors encoding local object structure. We show that the difference-of-convex-functions DC-programming framework is flexible enough to cope with this more general model class. Numerical results show that reconstruction becomes feasible under conditions where our previous approach fails.     

Multivariate public key cryptosystems from diophantine equations

Wang et al. introduced in (A medium-field multivariate public-key encryption scheme. Topics in Cryptology—CTRSA 2006: The Cryptographers’ Track at the RSA Conference, 2006) a multivariate public key cryptosystem, called MFE cryptosystem, and it is appealing as it is based on a simple polynomial identity. Their system, however, was subsequently broken by Ding et al. in (High order linearization equation (hole) attack on multivariate public key cryptosystems. Public key cryptography—PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007a, ?-Invertible cycles for multivariate quadratic public key cryptography. Public key cryptography—PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007b). Inspired by their work, we present a more general framework for multivariate public key cryptosystems, which combines ideas from both triangular and oil-vinegar schemes. Within this framework, we propose a new public key cryptosystem based on a solution of a Diophantine equation over polynomial rings.     

An exact penalty global optimization approach for mixed-integer programming problems

In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily define an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed-integer problems and we report computational results on some MINLP problems.     

New methods for computing inferences in first order logic

Recent improvements in satisfiability algorithms for propositional logic have made partial instantiation methods for first order predicate logic computationally more attractive. Two such methods have been proposed, one by Jeroslow and a hypergraph method for datalog formulas by Gallo and Rago. We show that they are instances of two general approaches to partial instantiation, and we develop these approaches for a large decidable fragment of first order logic (the fragment).Working Paper 1991-11. Supported in part by the Air Force Office of Scientific Research, Grant number AFOSR-87-0292.     

A note on the security of MST 3

In this paper, we study the recently proposed encryption scheme MST ₃, focusing on a concrete instantiation using Suzuki-2-groups. In a passive scenario, we argue that the one wayness of this scheme may not, as claimed, be proven without the assumption that factoring group elements with respect to random covers for a subset of the group is hard. As a result, we conclude that for the proposed Suzuki 2-groups instantiation, impractical key sizes should be used in order to prevent more or less straightforward factorization attacks.     

Cryptosystem using chaotic keys

According to Kerchoff's principle, the secrecy of a cryptosystem must reside entirely on the secret keys. In this paper, a new cryptosystem is presented and one of its secret keys is generated by a chaotic map, we call it chaotic key. Some experimental results are given and the security of our cryptosystem is discussed.     

An efficient diffusion approach for chaos-based image encryption

One of the existing chaos-based image cryptosystems is composed of alternative substitution and diffusion stages. A multi-dimensional chaotic map is usually employed in the substitution stage for image pixel permutation while a one-dimensional (1D) chaotic map is used for diffusion purpose. As the latter usually involves real number arithmetic operations, the overall encryption speed is limited by the diffusion stage. In this paper, we propose a more efficient diffusion mechanism using simple table lookup and swapping techniques as a light-weight replacement of the 1D chaotic map iteration. Simulation results show that at a similar security level, the proposed cryptosystem needs about one-third the encryption time of a similar cryptosystem. The effective acceleration of chaos-based image cryptosystems is thus achieved.     

Improving Approximate Bayesian Computation via Quasi-Monte Carlo

ABC (approximate Bayesian computation) is a general approach for dealing with models with an intractable likelihood. In this work, we derive ABC algorithms based on QMC (quasi-Monte Carlo) sequences. We show that the resulting ABC estimates have a lower variance than their Monte Carlo counter-parts. We also develop QMC variants of sequential ABC algorithms, which progressively adapt the proposal distribution and the acceptance threshold. We illustrate our QMC approach through several examples taken from the ABC literature.