Wyniki wyszukiwania - BazTech

1

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

2

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.

3

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.

4

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.

5

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.