CRYPTIM: Graphs as tools for symmetric encryption. A combinatorial method of encryption is presented. The general idea is to treat vertices of a graph as messages and walks of a certain length as encryption tools. We study the quality of such an encryption in the case of graphs of high girth by comparing the probability to guess the message (vertex) at random with the probability to break the key, i.e. to guess the encoding walk. In fact the quality is good for graphs which are close to the Erdős bound, defined by the even cycle theorem. We construct special linguistic graphs of affine type whose vertices (messages) and walks (encoding tools) could be both naturally identified with vectors over GF(q), and neighbors of the vertex defined by a system of linear equations. For them the computation of walks has a strong similarity with the classical scheme of linear coding. The algorithm has been implemented and tested.

References in zbMATH (referenced in 21 articles , 1 standard article )

Showing results 1 to 20 of 21.
Sorted by year (citations)

1 2 next

  1. Polak, Monika; Ustimenko, Vasyl: On stream cipher based on a family of graphs $\widetildeD(n, q)$ of increasing girth (2014)
  2. Ustimenko, Vasyl: On multivariate cryptosystems based on computable maps with invertible decomposition (2014)
  3. Klisowski, Michał; Ustimenko, Vasyl: On the comparison of cryptographical properties of two different families of graphs with large cycle indicator (2012)
  4. Romańczuk, Urszula; Ustimenko, Vasyl: On families of graphs of large cycle indicator, matrices of large order and key exchange protocols with nonlinear polynomial maps of small degree (2012)
  5. Romańczuk, Urszula; Ustimenko, Vasyl: On the key exchange with matrices of large order and graph based nonlinear maps (2010)
  6. Ustimenko, Vasyl Alex: Schubert cells in Lie geometries and key exchange via symbolic computations (2010)
  7. Wroblewska, Aneta; Ustimenko, Vasyl: On the key exchange with nonlinear polynomial maps of degree 4 (2010)
  8. Shaska, T.; Ustimenko, V.: On the homogeneous algebraic graphs of large girth and their applications (2009)
  9. Ustimenko, V. A.: Algebraic groups and small world graphs of high girth (2009)
  10. Shaska, Tanush; Ustimenko, V.: On some applications of graphs to cryptography and turbocoding (2008)
  11. Wroblewska, Aneta: On some properties of graph based public keys (2008)
  12. Futorny, Vyacheslav; Ustimenko, Vasyl: On small world semiplanes with generalised Schubert cells (2007)
  13. Ustimenko, V. A.: On graph-based cryptography and symbolic computations (2007)
  14. Ustimenko, V. A.: On the extremal graph theory for directed graphs and its cryptographical applications (2007)
  15. Ustimenko, V. A.: On the extremal regular directed graphs without commutative diagrams and their applications in coding theory and cryptography (2007)
  16. Ustimenko, V. A.: On linguistic dynamical systems, families of graphs of large girth, and cryptography (2005)
  17. Ustimenko, V. O.; Touzene, A.: CRYPTALL: System to encrypt all types of data (2004)
  18. Ustimenko, Vasyl A.: On a group theoretical construction of expanding graphs (2003)
  19. Faybusovich, Leonid: On Nesterov’s approach to semi-infinite programming (2002)
  20. Ustimenko, Vasiliy A.: Graphs with special arcs and cryptography (2002)

1 2 next