On new key exchange multivariate protocols based on pseudorandom walks on incidence structures

A new key exchange protocol formulated in terms of multivariate cryptography and based on the elaboration of a common walk in the linguistic graph by correspondents is proposed. This algorithm is described in details in the case of a known family of graphs of large girth given by nonlinear equations over a finite field.