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.     

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.     

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.     

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.     

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.     

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.     

Automorphism groups of polycyclic-by-finite groups and arithmetic groups

We show that the outer automorphism group of a polycyclic-by-finite group is an arithmetic group. This result follows from a detailed structural analysis of the automorphism groups of such groups. We use an extended version of the theory of the algebraic hull functor initiated by Mostow. We thus make applicable refined methods from the theory of algebraic and arithmetic groups. We also construct examples of polycyclic-by-finite groups which have an automorphism group which does not contain an arithmetic group of finite index. Finally we discuss applications of our results to the groups of homotopy self-equivalences of K(Γ,1)-spaces and obtain an extension of arithmeticity results of Sullivan in rational homotopy theory.     

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.

     

Limit groups as limits of free groups

We give a topological framework for the study of Sela'slimit groups: limit groups are limits of free groups in a compact space of marked groups. Many results get a natural interpretation in this setting. The class of limit groups is known to coincide with the class of finitely generated fully residually free groups. The topological approach gives some new insight on the relation between fully residually free groups, the universal theory of free groups, ultraproducts and non-standard free groups.     

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.      

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     

A modified method of a class of recently presented cryptosystems

In this paper, a modified method of a class of recently proposed cryptosystems is presented. As a remedy, the piecewise linear chaotic map (PLCM) which has a uniform distribution is adopted in our method. The experimental results demonstrate that the application of PLCM can not only ensure the feasibility but also promote the encryption speed of these cryptosystems. Moreover, a new design of dynamical look-up table is used as an efficient way to ensure the security of our cryptosystem.     

Characterization of generalized Chernikov groups among groups with involutions

The class of generalized Chernikov groups is characterized, i.e., the class of periodic locally solvable groups with the primary ascending chain condition. The name of the class is related to the fact that the structure of such groups is close to that of Chernikov groups. Namely, a Chernikov group is defined as a finite extension of a direct product of finitely many quasi-cyclic groups, and a generalized Chernikov group is a layer-finite extension of a direct productA of quasi-cyclicp-groups with finitely many factors for each primep such that each of its elements does not commute elementwise with only finitely many Sylow subgroups ofA. A theorem that characterizes the generalized Chernikov groups in the class of groups with involution is proved. Translated fromMatematicheskie Zametki, Vol. 62, No 4, pp. 577–587, October, 1997. Translated by A. I. Shtern     

Geometry for palindromic automorphism groups of free groups

We examine the palindromic automorphism group , of a free group F _n , a group first defined by Collins in [5] which is related to hyperelliptic involutions of mapping class groups, congruence subgroups of , and symmetric automorphism groups of free groups. Cohomological properties of the group are explored by looking at a contractible space on which acts properly with finite quotient. Our results answer some conjectures of Collins and provide a few striking results about the cohomology of , such as that its rational cohomology is zero at the vcd. Received: January 17, 2000.     

Holonomy groups of five dimensional Bieberbach groups

Let Γ be a Bieberbach group—that is a torsion free crystallographic group. In this paper we give a list of the isomorphism types of all holonomy groups of five-dimensional Bieberbach groups. An application to the problem of estimating the covolume of a discrete group of orientation-preserving isometries of hyperbolic 6-space is also given. This work was supported by Polish grant nr.0627/P3/93/04     

Covering groups of almost simple groups as Galois groups over ℚab(t)

In this paper we construct Galois extensions with the rigidity method and apply a criterion [15] for solving central embedding problems over ?^ab(t) to realize regularly the covering groups of most of the classical groups and the sporadic groups as Galois groups over ?^ab(t).     

Automorphism groups of nilpotent groups

We construct a full class of nilpotent groups of class 2 of an arbitrary infinite cardinality . Their centers, commutator subgroups and factors modulo the center will be the same and a homogeneous direct sum of a group of rank 1 or 2. Their automorphism groups will coincide and the factor group modulo the stabilizer could be an arbitrary group of size $\leqq$ .     

Surgery groups of the fundamental groups of hyperplane arrangement complements

Using a recent result of Bartels and Lück (The Borel conjecture for hyperbolic and CAT(0)-groups (preprint) \({{\tt arXiv:0901.0442v1}}\)) we deduce that the Farrell–Jones Fibered Isomorphism conjecture in \({L^{\langle -\infty \rangle}}\)-theory is true for any group which contains a finite index strongly poly-free normal subgroup, in particular, for the Artin full braid groups. As a consequence we explicitly compute the surgery groups of the Artin pure braid groups. This is obtained as a corollary to a computation of the surgery groups of a more general class of groups, namely for the fundamental group of the complement of any fiber-type hyperplane arrangement in \({{\mathbb C}^n}\).     

An image encryption scheme using reverse 2-dimensional chaotic map and dependent diffusion

In recent years, a variety of chaos-based image cryptosystems have been studied. Most of them adopt the traditional confusion–diffusion architecture, which is considered insecure upon chosen/known plain-image attacks. In this paper, a nonlinear traverse on the plain-image using dependent diffusion and reverse cat map is proposed to replace the traditional linear traverse performed in the confusion phase. Two cryptosystems are designed and are implemented by software means. Simulation results and numerical analysis justify their high efficiency and sufficient strength.