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.     

How to Choose Secret Parameters for RSA-Type Cryptosystems over Elliptic Curves

Recently, and contrary to the common belief, Rivest and Silverman argued that the use of strong primes is unnecessary in the RSA cryptosystem. This paper analyzes how valid this assertion is for RSA-type cryptosystems over elliptic curves. The analysis is more difficult because the underlying groups are not always cyclic. Previous papers suggested the use of strong primes in order to prevent factoring attacks and cycling attacks. In this paper, we only focus on cycling attacks because for both RSA and its elliptic curve-based analogues, the length of the RSA-modulus n is typically the same. Therefore, a factoring attack will succeed with equal probability against all RSA-type cryptosystems. We also prove that cycling attacks reduce to find fixed points, and derive a factorization algorithm which (most probably) completely breaks RSA-type systems over elliptic curves if a fixed point is found.     

G-Perfect nonlinear functions

Perfect nonlinear functions are used to construct DES-like cryptosystems that are resistant to differential attacks. We present generalized DES-like cryptosystems where the XOR operation is replaced by a general group action. The new cryptosystems, when combined with G-perfect nonlinear functions (similar to classical perfect nonlinear functions with one XOR replaced by a general group action), allow us to construct systems resistant to modified differential attacks. The more general setting enables robust cryptosystems with parameters that would not be possible in the classical setting. We construct several examples of G-perfect nonlinear functions, both -valued and -valued. Our final constructions demonstrate G-perfect nonlinear planar permutations (from to itself), thus providing an alternative implementation to current uses of almost perfect nonlinear functions.      

Counting isomorphism classes of pointed hyperelliptic curves of genus 4 over finite fields with odd characteristic

This paper is devoted to computing the number of isomorphism classes of pointed hyperelliptic curves over finite fields. We deal with the genus-4 case and the finite fields are of odd characteristic. The number of isomorphism classes is computed. This number can be represented as a polynomial in q of degree 7, where q is the order of the finite field. The results have applications in the classification problems and in the hyperelliptic curve cryptosystems.     

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.     

The Round Functions of Cryptosystem PGM Generate the Symmetric Group

S. S. Magliveras et al. have described symmetric and public key cryptosystems based on logarithmic signatures (also known as group bases) for finite permutation groups. In this paper we show that if G is a nontrivial finite group which is not cyclic of order a prime, or the square of a prime, then the round (or encryption) functions of these systems, that are the permutations of G induced by the exact-transversal logarithmic signatures (also known as transversal group bases), generate the full symmetric group on G. This answers a question of S. S. Magliveras, D. R. Stinson and Tran van Trung. AMS Classification:94A60, 20B15, 20B20     

Applications to cryptography of twisting commutative algebraic groups

We give an overview on twisting commutative algebraic groups and applications to discrete log-based cryptography. We explain how discrete log-based cryptography over extension fields can be reduced to cryptography in primitive subgroups. Primitive subgroups in turn are part of a general theory of tensor products of commutative algebraic groups and Galois modules (or twists of commutative algebraic groups), and this underlying mathematical theory can be used to shed light on discrete log-based cryptosystems. We give a number of concrete examples, to illustrate the definitions and results in an explicit way.     

On <Emphasis Type="Italic">τ</Emphasis>-adic representations of integers

Elliptic curve cryptosystems (ECCs) have become increasingly popular due to their efficiency and the small size of the keys they use. Particularly, the anomalous curves introduced by Koblitz allow a complex representation of the keys, denoted τNAF, that make the computations over these curves more efficient. In this article, we propose an efficient method for randomizing a τNAF to produce different equivalent representations of the same key to the same complex base τ. We prove that the average Hamming density of the resulting representations is 0.5. We identify the pattern of the τNAFs yielding the maximum number of representations and the formula governing this number. We also present deterministic methods to compute the average and the exact number of possible representations of a τNAF.      

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.     

How to Mask the Structure of Codes for a Cryptographic Use

In this paper we show how to strengthen public-key cryptosystems against known attacks, together with the reduction of the public-key. We use properties of subcodes to mask the structure of the codes used by the conceiver of the system. We propose new parameters for the cryptosystems and even a modified Niederreiter cryptosystem in the case of Gabidulin codes, with a public-key size of less than 4000 bits.Communicated by: P. WildAMS Classification: 11T71     

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

Rédei-Funktionen für Zweierpotenzen

L. Rédei has introduced in 1946 a class of rational functions over finite fields of orderp ^t –p being an odd prime — and has proved some interesting results on permutations which are induced by these functions. Recently, similar results have been found for factor rings of the integers of orderp ^t ; moreover, these functions have been applied to construct public key cryptosystems. In this paper we consider functions of Rédei type over finite fields and factor rings of the integers of order 2 ^t . We show that most of the results for oddp also hold in this case.

     

Computation of discrete logarithms in prime fields

The presumed difficulty of computing discrete logarithms in finite fields is the basis of several popular public key cryptosystems. The secure identification option of the Sun Network File System, for example, uses discrete logarithms in a field GF(p) with p a prime of 192 bits. This paper describes an implementation of a discrete logarithm algorithm which shows that primes of under 200 bits, such as that in the Sun system, are very insecure. Some enhancements to this system are suggested.     

Counting isomorphism classes of pointed hyperelliptic curves of genus 4 over finite fields with even characteristic

This paper is devoted to counting the number of isomorphism classes of pointed hyperelliptic curves over finite fields. We deal with the genus 4 case and the finite fields are of even characteristics. The number of isomorphism classes is computed and the explicit formulae are given. This number can be represented as a polynomial in q of degree 7, where q is the order of the finite field. The result can be used in the classification problems and it is useful for further studies of hyperelliptic curve cryptosystems, e.g. it is of interest for research on implementing the arithmetics of curves of low genus for cryptographic purposes. It could also be of interest for point counting problems; both on moduli spaces of curves, and on finding the maximal number of points that a pointed hyperelliptic curve over a given finite field may have.     

Pell hyperbolas in DLP–based cryptosystems

We present a study on the use of Pell hyperbolas in cryptosystems with security based on the discrete logarithm problem. Specifically, after introducing the group structure over generalized Pell hyperbolas (and also giving the explicit isomorphisms with the classical Pell hyperbolas), we provide a parameterization with both an algebraic and a geometrical approach. The particular parameterization that we propose appears to be useful from a cryptographic point of view because the product that arises over the set of parameters is connected to the Rédei rational functions, which can be evaluated in a fast way. Thus, we exploit these constructions for defining three different public key cryptosystems based on the ElGamal scheme. We show that the use of our parameterization allows to obtain schemes more efficient than the classical ones based on finite fields.     

Towards Minimal Addition Chains Using Ant Colony Optimisation

Modular exponentiation is one of the most important operations in almost all modern cryptosystems. It is performed using a series of modular multiplications. This operation is time consuming for large operands as is always the case in cryptography. Hence fast public-key cryptography software or hardware requires optimisation of the time consumed by a single modular multiplication and/or the reduction of the total number of modular multiplications required. This paper introduces a novel idea based on the principles of ant colony optimisation for finding a minimal addition chain that allows one to reduce the number of modular multiplications so that modular exponentiation can be implemented efficiently. The best addition chain reached by the ant system is compared to the one used in the m-ary and sliding window methods as well as with the best addition chain evolved by genetic algorithms. We demonstrate that the ant system significantly outperforms all these methods for any exponent size. ^★★ Research supported by FAPERJ () and CNPq ().     

Pseudorandom number generators based on random covers for finite groups

Random covers for finite groups have been introduced in Magliveras et?al. (J Cryptol 15:285–297, 2002), Lempken et?al. (J Cryptol 22:62–74, 2009), and Svaba and van Trung (J Math Cryptol 4:271–315, 2010) for constructing public key cryptosystems. In this article we describe a new approach for constructing pseudorandom number generators using random covers for large finite groups. We focus, in particular, on the class of elementary abelian 2-groups and study the randomness of binary sequences generated from these generators. We successfully carry out an extensive test of the generators by using the NIST Statistical Test Suite and the Diehard battery of tests. Moreover, the article presents argumentation showing that the generators are suitable for cryptographic applications. Finally, we include performance data of the generators and propose a method of using them in practice.     

Computing discrete logarithms in real quadratic congruence function fields of large genus

The discrete logarithm problem in various finite abelian groups is the basis for some well known public key cryptosystems. Recently, real quadratic congruence function fields were used to construct a public key distribution system. The security of this public key system is based on the difficulty of a discrete logarithm problem in these fields. In this paper, we present a probabilistic algorithm with subexponential running time that computes such discrete logarithms in real quadratic congruence function fields of sufficiently large genus. This algorithm is a generalization of similar algorithms for real quadratic number fields.

     

Pairing-Based Cryptography on Elliptic Curves

We give a brief overview of a recent branch of Public Key Cryptography, the so called Pairing-based Cryptography or Identity-based Cryptography. We describe the Weil pairing and its applications to cryptosystems and cryptographic protocols based on pairings as well as the elliptic curves suitable for the implementation of this kind of cryptography, the so called pairing-friendly curves. Some recent results of the authors are included.