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.     

An RSA based public-key cryptosystem for secure communication

A new cryptosystem that uses modulo arithmetic operations is proposed. It is based on Rivest-Shamir-Adleman’s public key cryptosystem. A feature of the proposed system is that the encryption and decryption procedures are computationally less intensive, and hence the system is amenable for high data bit rate communications.     

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.     

The number of public keys in the McEliece-Sidel’nikov cryptosystem

The McEliece-Sidel’nikov cryptosystem is a modification of the McEliece cryptosystem, which is one of the oldest public-key cryptosystems. It was proposed by V.M. Sidel’nikov in 1994 and is based on the u-fold application of Reed-Muller codes RM(r, m). The lower bound is obtained for the power of the set of public keys of the McEliece-Sidel’nikov cryptosystem using an arbitrary number of blocks (u).     

Towards generating secure keys for braid cryptography

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this article, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.      

A non-commutative cryptosystem based on quaternion algebras

We propose BQTRU, a non-commutative NTRU-like cryptosystem over quaternion algebras. This cryptosystem uses bivariate polynomials as the underling ring. The multiplication operation in our cryptosystem can be performed with high speed using quaternions algebras over finite rings. As a consequence, the key generation and encryption process of our cryptosystem is faster than NTRU in comparable parameters. Typically using Strassen’s method, the key generation and encryption process is approximately 16 / 7 times faster than NTRU for an equivalent parameter set. Moreover, the BQTRU lattice has a hybrid structure that makes inefficient standard lattice attacks on the private key. This entails a higher computational complexity for attackers providing the opportunity of having smaller key sizes. Consequently, in this sense, BQTRU is more resistant than NTRU against known attacks at an equivalent parameter set. Moreover, message protection is feasible through larger polynomials and this allows us to obtain the same security level as other NTRU-like cryptosystems but using lower dimensions.     

Cryptosystems in automorphism groups of group rings of Abelian groups

We introduce a new class of public-key cryptosystems generalizing ElGamal cryptosystems to automorphism groups of group rings of Abelian groups. A scheme of the basic variant of such a cryptosystem is presented and some types of attacks to it are considered. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 3, pp. 157–164, 2007.     

Weak Keys in MST 1

The public key cryptosystem MST₁ has been introduced by Magliveras et al. [12] (Public Key Cryptosystems from Group Factorizations. Jatra Mountain Mathematical Publications). Its security relies on the hardness of factoring with respect to wild logarithmic signatures. To identify ‘wild-like’ logarithmic signatures, the criterion of being totally-non-transversal has been proposed. We present tame totally-non-transversal logarithmic signatures for the alternating and symmetric groups of degree ≥ 5. Hence, basing a key generation procedure on the assumption that totally-non-transversal logarithmic signatures are ‘wild like’ seems critical. We also discuss the problem of recognizing ‘weak’ totally-non-transversal logarithmic signatures, and demonstrate that another proposed key generation procedure based on permutably transversal logarithmic signatures may produce weak keys. Communicated by: P. Wild     

Cryptanalysis of a new substitution–diffusion based image cipher

This paper introduces two different types of attacks on a recently proposed cryptosystem based on chaotic standard and logistic maps. In the two attacks, only a pair of (plaintext/ciphertext) was needed to totally break the cryptosystem.     

Extension of Overbeck’s attack for Gabidulin-based cryptosystems

Cryptosystems based on codes in the rank metric were introduced in 1991 by Gabidulin, Paramanov, and Tretjakov (GPT) and have been studied as a promising alternative to cryptosystems based on codes in the Hamming metric. In particular, it was observed that the combinatorial solution for solving the rank analogy of the syndrome decoding problem appears significantly harder. Early proposals were often made with an underlying Gabidulin code structure. Gibson, in 1995, made a promising attack which was later extended by Overbeck in 2008 to cryptanalyze many of the systems in the literature. Improved systems were then designed to resist the attack of Overbeck and yet continue to use Gabidulin codes. In this paper, we generalize Overbeck’s attack to break the GPT cryptosystem for all possible parameter sets, and then extend the attack to cryptanalyze particular variants which explicitly resist the attack of Overbeck.     

Improved distinguishers for HC-128

HC-128 is an eSTREAM final portfolio stream cipher. Several authors have investigated its security and, in particular, distinguishing attacks have been considered. Still, no one has been able to provide a distinguisher stronger than the one presented by Wu in the original HC-128 paper. In this paper we first argue that the keystream requirement in Wu’s original attack is underestimated by a factor of almost 2⁸. Our revised analysis shows that the keystream complexity of Wu’s original attack is 2^160.471 32-bit keystream blocks. We then go on to investigate two new types of distinguishers on HC-128. One of them, a distinguisher counting the number of zeros in created blocks of bits, gives a biased distribution that requires 2^143.537 such constructed block samples (2^152.537 32-bit keystream blocks). For fairness, the same metric is used to compare our attack to Wu’s, and our improvement is significant compared to Wu’s original result. Furthermore, the vector-based methodology used is general and can be applied to any cryptographic primitive that reveals a suitable probability distribution.     

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.     

A synthetic indifferentiability analysis of some block-cipher-based hash functions

At ASIACRYPT’06, Chang et al. analyzed the indifferentiability of some popular hash functions based on block ciphers, namely, the twenty collision resistant PGV, the MDC2 and the PBGV hash functions, etc. In particular, two indifferentiable attacks were presented on the four of the twenty collision resistant PGV and the PBGV hash functions with the prefix-free padding. In this article, a synthetic indifferentiability analysis of some block-cipher-based hash functions is considered. First, a more precise definition is proposed on the indifferentiability adversary in block-cipher-based hash functions. Next, the advantage of indifferentiability is separately analyzed by considering whether the hash function is keyed or not. Finally, a limitation is observed in Chang et al.’s indifferentiable attacks on the four PGV and the PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-free padding, the NMAC/HMAC and the chop construction.      

Attacking a public key cryptosystem based on tree replacement

We point out several security flaws in the cryptosystem based on tree replacement systems proposed by Samuel, Thomas, Abisha and Subramanian at INDOCRYPT 2002. Due to the success of (among others) very simple ciphertext-only attacks, we evidence that this system does not, in its present form, offer acceptable security guarantees for cryptographic applications.     

Global well-posedness for a coupled modified KdV system

We prove the sharp global well-posedness result for the initial value problem (IVP) associated to the system of the modified Korteweg-de Vries (mKdV) equation. For the single mKdV equation such result has been obtained by using Mirura’s Transform that takes the KdV equation to the mKdV equation [8]. We do not know the existence of Miura’s Transform that takes a KdV system to the system we are considering. To overcome this difficulty we developed a new proof of the sharp global well-posedness result for the single mKdV equation without using Miura’s Transform. We could successfully apply this technique in the case of the mKdV system to obtain the desired result.     

The Lagrange-D’Alembert-Poincaré equations and integrability for the Euler’s disk

Nonholonomic systems are described by the Lagrange-D’Alembert’s principle. The presence of symmetry leads, upon the choice of an arbitrary principal connection, to a reduced D’Alembert’s principle and to the Lagrange-D’Alembert-Poincaré reduced equations. The case of rolling constraints has a long history and it has been the purpose of many works in recent times. In this paper we find reduced equations for the case of a thick disk rolling on a rough surface, sometimes called Euler’s disk, using a 3-dimensional abelian group of symmetry. We also show how the reduced system can be transformed into a single second order equation, which is an hypergeometric equation.     

A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Iwasawa theory for elliptic curves at supersingular primes

We give a new formulation in Iwasawa theory for elliptic curves at good supersingular primes. This formulation is similar to Mazur’s at good ordinary primes. Namely, we define a new Selmer group, and show that it is of Λ-cotorsion. Then we formulate the Iwasawa main conjecture as that the characteristic ideal is generated by Pollack’s p-adic L-function. We show that this main conjecture is equivalent to Kato’s and Perrin-Riou’s main conjectures. We also prove an inequality in the main conjecture by using Kato’s Euler system. In terms of the λ- and the μ-invariants of our Selmer group, we specify the numbers λ and μ in the asymptotic formula for the order of the Tate-Shafarevich group by Kurihara and Perrin-Riou. Oblatum 17-VI-2002 & 2-IX-2002?Published online: 18 December 2002     

Index Calculation Attacks on RSA Signature and Encryption

At Crypto ’85, Desmedt and Odlyzko described a chosen-ciphertext attack against plain RSA encryption. The technique can also be applied to RSA signatures and enables an existential forgery under a chosen-message attack. The potential of this attack remained untapped until a twitch in the technique made it effective against two very popular RSA signature standards, namely iso/iec 9796-1 and iso/iec 9796-2. Following these attacks, iso/iec 9796-1 was withdrawn and ISO/IEC 9796-2 amended. In this paper, we explain in detail Desmedt and Odlyzko’s attack as well as its application to the cryptanalysis of iso/iec 9796-2. AMS Classification: 11T71, 14G50, 94A60