Wyniki wyszukiwania - BazTech

1

Algorithms for generation of Ramanujan graphs, other Expanders and related LDPC codes

Polak M., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2015

|

Vol. 15, no. 2

14--21

EN

Expander graphs are highly connected sparse finite graphs. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. For practical applications it is very important to construct expander and Ramanujan graphs with given regularity and order. In general, constructions of the best expander graphs with a given regularity and order is no easy task. In this paper we present algorithms for generation of Ramanujan graphs and other expanders. We describe properties of obtained graphs in comparison to previously known results. We present a method to obtain a new examples of irregular LDPC codes based on described graphs and we briefly describe properties of this codes.

2

On New Examples of Families of Multivariate Stable Maps and their Cryptographical Applications

Wróblewska A., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2014

|

Vol. 14, no. 1

19--36

EN

Let K be a general finite commutative ring. We refer to a family gn, n = 1, 2, . . . of bijective polynomial multivariate maps of Kn as a family with invertible decomposition gn = gn1 gn2 . . . g gnk, such that the knowledge of the composition of gni allows computation of gni for O(ns) (s > 0) elementary steps. A polynomial map g is stable if all non-identical elements of kind gt, t > 0 are of the same degree. We construct a new family of stable elements with invertible decomposition. This is the first construction of the family of maps based on walks on the bipartite algebraic graphs defined over K, which are not edge transitive. We describe the application of the above mentioned construction for the development of stream ciphers, public key algorithms and key exchange protocols. The absence of edge transitive group essentially complicates cryptanalysis.

3

On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition

Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2014

|

Vol. 14, no. 1

7--17

EN

Let K be a commutative ring and K^n be a space over K of dimension n. We introduce the concept of a family of multivariate maps f(n) of K^n into itself with invertible decomposition.If f(n) is computable in polynomial time then it can be used as the public rule and the invertible decomposition provides a private key in f(n) based public key infrastructure. Requirementsof polynomial ity of degree and density for f(n) allow to estimate the complexity of encryption procedurefor a public user. The concepts of a stable family and a family of increasing order are motivatedby the studies of discrete logarithm problem in the Cremona group. The statement on the existenceof families of multivariate maps of polynomial degree and polynomial density of increasing order with the invertible decomposition is proved. The proof is supported by explicite construction which canbe used as a new cryptosystem. The presented multivariate encryption maps are induced by special walks in the algebraically dened extremal graphs A(n;K) and D(n;K) of increasing girth.

4

On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree

Ustimenko V., Wroblewska A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2013

|

Vol. 13, no. 1

63--80

EN

We say that the sequence gn, n≥3, n→∞ of polynomial transformation bijective mapsof free module Kgn over commutative ring K is a sequence of stable degree if the order of gn is growing with n and the degree of each nonidentical polynomial map of kind gkn is an independent constant c. Transformation b = τgnkτ−1, where τ is the affine bijection, n is large and k is relatively small, can be used as a base of group theoretical Diffie-Hellman key exchange algorithm for the Cremona group C(Kn) of all regular automorphisms of Kn. The specific feature of this method is that the order of the base may be unknown for the adversary because of the complexity of its computation. The exchange can be implemented by tools of Computer Algebra (symbolic computations). The adversary can not use the degree of right handside in bx = d to evaluate unknown x in this form for the discrete logarithm problem. In the paper we introduce the explicit constructions of sequences of elements of stable degree for the cases c = 3 and c = n+2/4 for each commutative ring K containing at least 3 regular elements and discuss the implementation of related key exchange and multivariate map algorithms.

5

On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2

Romańczuk U., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 3

89--106

EN

The family of algebraic graphs A(n;K) defined over the finite commutative ring K were used for the design of different multivariate cryptographical algorithms (private and public keys, key exchange protocols). The encryption map corresponds to a special walk on this graph. We expand the class of encryption maps via the use of an automorphism group of A(n;K). In the case of characteristic 2 the encryption transformation is a Boolean map. We change finite field for the commutative ring of characteristic 2 and consider some modifications of algorithm which allow to hide a ground commutative ring.

6

LDPC codes based on algebraic graphs

Polak M., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 3

107--119

EN

In this paper we investigate correcting properties of LDPC codes obtained from families of algebraic graphs. The graphs considered in this article come from the infinite incidence structure. We describe how to construct these codes, choose the parameters and present several simulations, done by using the MAP decoder. We describe how error correcting properties are dependent on the graph structure. We compare our results with the currently used codes, obtained by Guinand and Lodge [1] from the family of graphs D(k; q), which were constructed by Ustimenko and Lazebnik [2].

7

Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography

Ustimenko V., Wroblewska A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 3

65--74

EN

Let K be a finite commutative ring and f = f(n) a bijective polynomial map f(n) of the Cartesian power K^n onto itself of a small degree c and of a large order. Let f^y be a multiple composition of f with itself in the group of all polynomial automorphisms, of free module K^n. The discrete logarithm problem with the pseudorandom base f(n) (solvef^y = b for y) is a hard task if n is sufficiently large. We will use families of algebraic graphs defined over K and corresponding dynamical systems for the explicit constructions of such maps f(n) of a large order with c = 2 such that all nonidentical powers f^y are quadratic polynomial maps. The above mentioned result is used in the cryptographical algorithms based on the maps f(n) – in the symbolic key exchange protocols and public keys algorithms.

8

The implementation of cubic public keys based on a new family of algebraic graphs

Klisowski M., Romańczuk U., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 2

127--141

EN

Families of edge transitive algebraic graphs defined over finite commutative rings were used for the development of stream ciphers, public key cryptosystems and key exchange protocols. We present the results of the first implementation of a public key algorithm based on the family of algebraic graphs, which are not edge transitive. The absence of an edge transitive group of symmetries means that the algorithm can not be described in group theoretical terms. We hope that it licates cryptanalysis of the algorithm. We discuss the connections between the security of algorithms and the discrete logarithm problem.The plainspace of the algorithm is Kn, where K is the chosen commutative ring. The graph theoretical encryption corresponds to walk on the bipartite graph with the partition sets which are isomorphic to Kn. We conjugate the chosen graph based encryption map, which is a composition of several elementary cubical polynomial automorphisms of a free module Kn with special invertible affine transformation of Kn. Finally we compute symbolically the corresponding cubic public map g of Kn onto Kn. We evaluate time for the generation of g, and the number of monomial expression in the list of corresponding public rules.

9

Performance of algebraic graphs based stream-ciphers using large finite fields

Touzene A., Ustimenko V., AlRaissi M., Boudeliou I.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 2

81--93

EN

Algebraic graphs D(n, q) and their analog graphs D(n, K), where K is a finite commutative ring were used successfully in Coding Theory (as Tanner graphs for the construction of LDPC codes and turbo-codes) and in Cryptography (stream-ciphers, public-keys and tools for the key-exchange protocols. Many properties of cryptography algorithms largely depend on the choice of finite field Fq or commutative ring K. For practical implementations the most convenient fields are F and rings modulo Z modulo 2m. In this paper the reader can find the first results about the comparison of D(n, 2m) based stream-ciphers for m = 8, 16, 32 implemented in C++. They show that performance (speed) of algorithms gets better when m is increased.

10

On the key expansion of D(n, K)-based cryptographical algorithm

Ustimenko V., Wróblewska A.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 2

95--111

EN

The family of algebraic graphs D(n, K) defined over finite commutative ring K have been used in different cryptographical algorithms (private and public keys, key exchange protocols). The encryption maps correspond to special walks on this graph. We expand the class of encryption maps via the use of edge transitive automorphism group G(n, K) of D(n, K). The graph D(n, K) and related directed graphs are disconnected. So private keys corresponding to walks preserve each connected component. The group G(n, K) of transformations generated by an expanded set of encryption maps acts transitively on the plainspace. Thus we have a great difference with block ciphers, any plaintexts can be transformed to an arbitrarily chosen ciphertex by an encryption map. The plainspace for the D(n, K) graph based encryption is a free module P over the ring K. The group G(n, K) is a subgroup of Cremona group of all polynomial automorphisms. The maximal degree for a polynomial from G(n, K) is 3. We discuss the Diffie-Hellman algorithm based on the discrete logarithm problem for the group τ-1Gτ, where τ is invertible affine transformation of free module P i.e. polynomial automorphism of degree 1. We consider some relations for the discrete logarithm problem for G(n, K) and public key algorithm based on the D(n, K) graphs.

11

On the key exchange with new cubical maps based on graphs

Romańczuk U., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 4

11--19

EN

Families of edge transitive algebraic graphs Fn(K), over the commutative ring K were used for the graph based cryptographic algorithms. We introduce a key exchange protocol defined in terms of bipartite graph An(K), n ≥ 2 with point set Pn and line set Ln isomorphic to n-dimensional free module Kn. Graphs A(n, K) are not vertex and edge transitive. There is a well defined projective limit lim A(n, K) = A(K), n → ∞ which is an infinite bipatrtite graph with point set P = lim Pn and line set L = limLn. Let K be a commutative ring contain at least 3 regular elements (not zero divisors). For each pair of (n, d), n ≥ 2, n ≥ 1 and sequence of elements α1, α2, …, α2d, such that α1, αi+αi+1, i = 1, 2, …, 2d, i = 1, 2, … 2d-1 and α2d+α1 are regular elements of the ring K. We define polynomial automorphism hn = hn (d, α1, α2, …, α2d) of variety Ln (or Pn). The existence of projective limit lim An(K) guarantees the existence of projective limit h = h(d, α1, α2, …, α2d) = lim hn, n → ∞ which is cubical automorphism of infinite dimensional varieties L (or P). We state that the order of h is an infinity. There is a constant n0 such that hn, n ≥ n0 is a cubical map. Obviously the order of hn is growing with the growth of n and the degree of polynomial map (hn)k from the Cremona group of all polynomial automorphisms of free module Kn with operation of composition is bounded by 3. Let τ be affine automorphism of Kn i.e. the element of Cremona group of degree 1. We suggest symbolic Diffie Hellman key exchange with the use of cyclic subgroup of Cremona group generated by τ-1hnτ. In the case of K = Fp, p is prime, the order of hn is the power of p. So the order is growing with the growth of p. We use computer simulation to evaluate the orders in some cases of K = Zm, where m is a composite integer.

12

On LDPC codes corresponding to affine parts of generalized polygons

Polak M., Ustimenko V.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 2

143--152

EN

In this paper we describe how to use special induced subgraphs of generalized m-gons to obtain the LDPC error correcting codes. We compare the properties of codes related to the affine parts of q-regular generalised 6-gons with the properties of known LDPC codes corresponding to the graphs D(5, q).