\documentclass[12pt,a4paper]{article}

\textheight 22cm \textwidth 14.5cm \oddsidemargin 1cm \topmargin
-0.5cm

\begin{document}

\title{On the $PSL_2(q)$, Ramanujan graphs and key exchange protocols}

\author{ U. Romanczuk, V. Ustimenko}

\date{University of Maria Curie Sklodowska, Lublin, Poland}

\maketitle

We consider the following scheme for the key exchange between two correspondents
(Alice and Bob in cryptographical slang). They choose two commuting matrices $C$ and $D$ from the
group $GL_n(F_q)$ ( two elements of $PGL_n(F_q)$ or PSL_n(F_q)$) and the vector $d \in {F_q}^n$
(totality of  projective points of P({F_q}^n)).  We assume that $A$, $B$ and $d$ are known for
the adversary.

Alice and Bob chose polynomials in two variables $f_A(x,y)$ and $g_A(x, y)$ from $F_q[x, y]$,
respectively.
Alice and Bob compute $T_A=F_A(C, D)$ and $T_B=F_B(C, D)$ apply this linear transformation to $d$
and exchange vectors $T_A(d)$ and $T_B(d)$. Finaly Alice computes $T_A(T_B(d))$ and Bob obtaines
T_B(T_A(d))$. So they are getting common vector.

In case of $A=h(D)$, $h(x) \in F_q[x]$ and $D$ is diagonalisable the adversary can computes
$T_A(T_B(d))$  easily.

But in general case this protocol  is supported by the complexity of known "wild"
problem:

Whether or not two pairs of matrices $(C, D)$ and $(C, D)$ are conjagete (see [1]).

The problem is still "wild" when we have $CD=DC$ additionaly ( see [1]).
In case of finite field we can change "wilderness"  on $NP$ completness ([2]).

For the practical use of the protocol we have to generate commuting pair $C, D$,
 such that the order $C$ is large by some supporting algorithm. In the case of small simple group
$PSL_2(F_p)$, where $p$ is prime, we will use famous Ramanujan graphs  (se [4], [3]) for the
development of the
 appropriate pair
of commuting elements of the group.

\renewcommand{\refname}{\vspace{-12mm}}
\begin{thebibliography}{99}
\small\itemsep=0pt

\bibitem{1} Yu. Drozd, {\em Tame and Wild matrix problems},
 Lecture Notes in Mathematics, vol. 832/1980, Springer, 2006.

\bibitem{2} D. Grigoriev, {\em On the complexity of the ``wild'' matrix problems},
 of the
isomorphism of algebras and graphs, 
Notes of Scientific Seminars of LOMI, 1981, vol.105, p.10-17
(in Russian)
(English translation in J.Soviet Math., vol.22, 1983, p.1285-1289).

\bibitem{3} A. Lubotsky, R. Philips, P. Sarnak, {\em Ramanujan
graphs}, J. Comb. Theory}, 115, N 2., (1989), 62-89.

\bibitem{4} G. Margulis, {\em Explicit group-theoretical constructions of
combinatorial schemes  and their application to desighn of
expanders and concentrators}, Probl. Peredachi Informatsii., 24,
N1,1988,  51-60. English translation publ. Journal of Problems of
Information transmission (1988), 39-46.

\end{thebibliography}
\noindent
\end{document}