Cryptographic Hash Functions from Expander Graphs

Denis Charles1, Kristin Lauter1, Eyal Z. Goren2
1Microsoft Research, Redmond, WA, 98052, USA
2McGill University, Montréal, Canada, H3A 2K6

Tóm tắt

Từ khóa


Tài liệu tham khảo

K.S. Abdukhalikov, C. Kim, On the security of the hashing scheme based on SL2. In Fast Software Encryption 1998. Lecture Notes Computer Science, vol. 1372 (Springer, Berlin, 1998), pp. 93–102.

N. Alon, Eigenvalues and expanders. Combinatorica 6, 83–98 (1986).

I. Blake, G. Seroussi, N. Smart, Elliptic Curves in Cryptography. Lond. Math. Soc., Lecture Note Series, vol. 265 (Cambridge University Press, Cambridge, 1999).

A. Bostan, F. Morain, B. Salvy, E. Schost, Fast algorithms for computing isogenies between elliptic curves, http://arxiv.org/abs/cs/0609020 .

J.M. Cerviño, On the correspondence between supersingular elliptic curves and maximal quaternionic orders, http://arxiv.org/abs/math/0404538 .

D. Charles, K. Lauter, Computing modular polynomials. Lond. Math. Soc. J. Comput. Math. 8, 195–204 (2005).

C. Charnes, J. Pieprzyk, Attacking the SL2 hashing scheme. In Advances in Cryptology—ASIACRYPT’94, ed. by J. Pieprzyk, R. Safavi-Naini. Lecture Notes in Computer Science, vol. 917 (Springer, Berlin, 1995), pp. 322–330.

S. Contini, A.K. Lenstra, R. Steinfeld, VSH, an efficient and provable collision resistant hash function. In Eurocrypt 2006. Lecture Notes in Computer Science, vol. 4004 (Springer, Berlin, 2006), pp. 165–182.

M. Eichler, Quaternäre quadratische Formen und die Riemannsche Vermutung für die Kongruenzzetafunktion. Arch. Math. 5, 355–366 (1954).

S. Galbraith, Constructing isogenies between elliptic curves over finite fields. Lond. Math. Soc. J. Comput. Math. 2, 118–138 (1999).

O. Goldreich, Randomized methods in computation, Lecture Notes, http://www.wisdom.weizmann.ac.il/~oded/rnd-sum.html .

B.H. Gross, Heights and the special values of L-series. In Number Theory, Montreal, Que. 1985. CMS Conf. Proc., vol. 7 (Am. Math. Soc., Providence, 1987), pp. 115–187.

J.L. Hafner, K.S. McCurley, A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2, 837–850 (1989).

S. Hamdy, B. Möller, Security of cryptosystems based on class groups of imaginary quadratic orders. In Advances in Cryptology ASIACRYPT 2000, ed by T. Okamoto. Lecture Notes in Computer Science, vol. 1976 (Springer, Berlin, 2000), pp. 234–247.

A.K. Lenstra, D. Page, M. Stam, Discrete logarithm variants of VSH. In Proceedings Vietcrypt 2006. Lecture Notes in Computer Science, vol. 4341 (Springer, Berlin, 2006), pp. 229–242.

A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs. Combinatorica 8(3), 261–277 (1988).

A.K. Pizer, An algorithm for computing modular forms on Γ0(N). J. Algebra 64(2), 340–390 (1980).

A.K. Pizer, Ramanujan graphs and Hecke operators. Bull. AMS 23(1) (1990).

P. Sarnak, Some Applications of Modular Forms. Cambridge Tracts in Mathematics, vol. 99 (Cambridge University Press, Cambridge, 1990).

G. Shimura, Correspondances modulaires et les fonctions zeta de courbes algébriques. J. Math. Soc. Jpn. 10, 1–28 (1958).

C.L. Siegel, Uber die Classenzahl quadratischer Zahlkorper. Acta Arith. 1, 83–86 (1935).

J.H. Silverman, The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106 (Springer, Berlin, 1986).

R. Steinwandt, M. Grassl, W. Geiselmann, Beth, T., Weaknesses in the $\mathrm{SL}_{2}(\mathbb{F}_{2^{n}})$ hashing scheme. In CRYPTO 2000. Lecture Notes Computer Science, vol. 1880 (Springer, Berlin, 2000), pp. 287–299.

J. Vélu, Isogénies entre courbes elliptiques. C. R. Acad. Sc. Paris 273, 238–241 (1971).

G. Zémor, Hash functions and Cayley graphs. Des. Codes Cryptogr. 4, 381–394 (1994).

G. Zémor, J.-P. Tillich, Group theoretic hash functions. In The First French-Israeli Workshop on Algebraic Coding. Lecture Notes in Computer Science, vol. 781 (Springer, Berlin, 1993).

G. Zémor, J.-P. Tillich, Hashing with SL2. In Advances in Cryptology, Crypto’94. Lecture Notes in Computer Science, vol. 839 (Springer, Berlin, 1994).