LPS-type Ramanujan graphs

Ramanujan graph is an optimal combinatorial structure of expander graph in a sense of random walks on graphs. In general, it is difficult to find explicit constructions of Ramanujan graphs. There are only a few explicit Ramanujan graphs so far such as Cayley-type by Lubotzky-Phillips-Sarnak (LPS) in '88, Morgenstern in '94, Chiu in '92 and non-Cayley-type by Pizer in '90. From Cayley-type Ramanujan graphs, we can construct a cryptographic hash functions called Cayley hash functions. Cayley hash function may be a good foundation for post-quantum cryptography, since its security reduction based on well-defined mathematical problem involves non-Abelian groups. Four particular parameter sets for Cayley hash functions have been proposed in the past, and so far dedicated preimage algorithms have been found for all of them. The most powerful and critical tool against these Cayley hash function is a lifting attack, which crucial part is related to find the specific solution of each structures' norm equation with well-chosen random variables. These algorithms do however not seem to extend to generic parameters, and as a result it is still an open problem to determine the security of Cayley hash functions in general. In this paper, we recall the constructions of LPS and Chiu's Ramanujan graphs and then show a general construction of such graph from the view point of quaternion algebras. One of the advantage of our graph is that it can resist variants of a lifting attack in general because its norm equation has much larger coefficients than LPS and Chiu's. We suggest how to construct a new family of LPS-type Ramanujan and appeal these graphs as prominent candidates for secure Cayley hash functions. Our results contribute to a better understanding of the hard problems underlying the security of Cayley hash functions.