Low-density attack revisited

The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density <0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.’s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.      

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.     

Public-key cryptography and invariant theory

We suggest public-key cryptosystems based on groups invariants. We also give an overview of known cryptosystems that involve groups. Bibliography: 33 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 26–38.This revised version was published online in April 2005 with a corrected cover date and article title.     

Goppa codes over the p-adic integers and integers modulo pe

Goppa codes were defined by Valery D. Goppa in 1970. In 1978, Robert J. McEliece used this family of error-correcting codes in his cryptosystem, which has gained popularity in the last decade due to its resistance to attacks from quantum computers. In this paper, we present Goppa codes over the p-adic integers and integers modulo $p^e$. This allows the creation of chains of Goppa codes over different rings. We show some of their properties, such as parity-check matrices and minimum distance, and suggest their cryptographic application, following McEliece's scheme.     

The State of Elliptic Curve Cryptography

Since the introduction of public-key cryptography by Diffie and Hellman in 1976, the potential for the use of the discrete logarithm problem in public-key cryptosystems has been recognized. Although the discrete logarithm problem as first employed by Diffie and Hellman was defined explicitly as the problem of finding logarithms with respect to a generator in the multiplicative group of the integers modulo a prime, this idea can be extended to arbitrary groups and, in particular, to elliptic curve groups. The resulting public-key systems provide relatively small block size, high speed, and high security. This paper surveys the development of elliptic curve cryptosystems from their inception in 1985 by Koblitz and Miller to present day implementations.     

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.     

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.     

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).     

关于陷门背包公开钥密码系统的注记

利用不定方程理论及中国剩余定理,我们设计了一类陷门背包公开钥密码系统,它们具有更好的安全性.     

Co-Orthogonal Codes

We define, construct and sketch possible applications of a new class of non-linear codes: co-orthogonal codes, with possible applications in cryptography and parallel processing. We also describe a fast and general method for generating (non-linear) codes with prescribed dot-products with the help of multi-linear polynomials.     

An explicit class of codes with good parameters and their duals

We study a class of codes with good parameters and their duals explicitly. We give direct constructions of the dual codes and obtain self-orthogonal codes with good parameters.     

A formula on the weight distribution of linear codes with applications to AMDS codes

The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with small Singleton's defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations.     

Binary permutation sequences as subsets of Levenshtein codes,spectral null codes,run-length limited codes and constant weight codes

We investigate binary sequences which can be obtained by concatenating the columns of (0,1)-matrices derived from permutation sequences. We then prove that these binary sequences are subsets of a surprisingly diverse ensemble of codes, namely the Levenshtein codes, capable of correcting insertion/deletion errors; spectral null codes, with spectral nulls at certain frequencies; as well as being subsets of run-length limited codes, Nyquist null codes and constant weight codes. This paper was presented in part at the IEEE Information Theory Workshop, Chengdu, China, October, 2006.     

Cyclic Codes Over\mathbb{Z}_{4} of Even Length

We determine the structure of cyclic codes over for arbitrary even length giving the generator polynomial for these codes. We determine the number of cyclic codes for a given length. We describe the duals of the cyclic codes, describe the form of cyclic codes that are self-dual and give the number of these codes. We end by examining specific cases of cyclic codes, giving all cyclic self-dual codes of length less than or equal to 14. San Ling - The research of the second named author is partially supported by research Grants MOE-ARF R-146-000-029-112 and DSTA R-394-000-011-422.     

Some families of -cyclic codes

We introduce and solve several problems on -cyclic codes.We study the link between -linear cyclic codes and -cyclic codes (not necessarily linear) obtained by using two binary linear cyclic codes. We use these results to present a family of -self-dual linear cyclic codes.     

On Hermitian LCD codes and their Gray image

We provide methods and algorithms to construct Hermitian linear complementary dual (LCD) codes over finite fields. We study existence of self-dual basis with respect to Hermitian inner product, and as an application, we construct Euclidean LCD codes by projecting the Hermitian codes over such a basis. Many optimal quaternary Hermitian and ternary Euclidean LCD codes are obtained. Comparisons with classical constructions are made.     

On non-Abelian homomorphic public-key cryptosystems

An important problem of modern cryptography concerns secret public-key computations in algebraic structures. We construct homomorphic cryptosystems, which are (secret) epimorphisms f : G H, where G and H are (publically known) groups and H is finite. A letter of a message to be encrypted is an element h H, while its encryption is an element g G such that f(g) = h. A homomorphic cryptosystem allows one to perform computations (in the group G) with encrypted information (without knowing the original message over H).In this paper, homomorphic cryptosystems are constructed for the first time for non-Abelian groups H (earlier, homomorphic cryptosystems were known only in the Abelian case). In fact, we present such a system for any (fixed) solvable group H. Bibliography: 24 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 39–58.This revised version was published online in April 2005 with a corrected cover date and article title.     

Some New Results on Optimal Codes Over F5

We present some results on almost maximum distance separable (AMDS) codes and Griesmer codes of dimension 4 over over the field of order 5. We prove that no AMDS code of length 13 and minimum distance 5 exists, and we give a classification of some AMDS codes. Moreover, we classify the projective strongly optimal Griesmer codes over F₅ of dimension 4 for some values of the minimum distance.