Abstract
We propose two new classes of hash functions which are motivated by Maximum Rank Distance (MRD) codes. We analise the security of these schemes. The system setup phase is computationally expensive for general field extensions. To overcome this limitation we derive an algebraic solution which avoids computations in special extension fields in the intended operational range of the hash functions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. L. Carter M. N. Wegman (1979) ArticleTitleUniversal class of hash functions J. Comput. Syst. Sci. 18 IssueID2 143–154 Occurrence Handle10.1016/0022-0000(79)90044-8
K. Chen (1995) A new identification algorithm E. Dawson J. Golic (Eds) Cryptography: Policy and Algorithms Conference Vol 1029 (LNCS) Springer-Verlag Berlin 244–249
E. Gabidulin (1985) ArticleTitleTheory of codes with maximum rank distance Probl. Information Transm. 21 IssueID1 1–12
T. Johansson (1995) ArticleTitleAuthentication codes for nontrusting parties obtained from rank metric codes Des., Codes Cryptogr. 6 205–218
Krawczyk H., LFSR-based hashing and authentication. In Y. G. Desmedt (ed.) Advances in Cryptology, Proceedings of CRYPTO’94 Vol. 839 (LNCS), Springer-Verlag, (1994) pp. 129–139.
Krawczyk H., New hash functions for message authentication, In L. C. Guillou and J. J. Quisquater (eds.) Advances in Cryptology, Proceedings of EUROCRYPTO’95, Vol. 921 (LNCS), Springer-Verlag, (1995) pp. 301–310.
R. Lidl H. Niedereiter (1994) Introduction to Finite Fields and their Applications Cambridge University Press
F. J. MacWilliams N. J. A. Sloane (1977) The Theory of Error Correcting Codes North-Holland Amsterdam
B. Preneel, Analysis and Design of Cryptographic Hash Functions, Ph.D. Thesis. Katholieke University Leuven, January 1993.
Preneel B., van Oosschot P.C. (1996) On the security of two MAC algorithms. In U. Maurer (ed.) Advances in Cryptology, Proceedings of EUROCRYPTO’96 Vol. 1070 (LNCS), Springer-Verlag, Berlin pp. 19–32.
R. Safavi-Naini, S. Bakhtiari and C. Charnes, Fast software encryption. In S. Vaudenay (ed.) Proceedings of the 5th International Workshop FSE’98, Paris, France, March 1998, Vol. 1324 (LNCS), Springer-Verlag, Berlin (1998) pp. 134–149.
P. Rogaway, Bucket hashing and its application to fast message authentication. In D. Coppermith (ed.) Advances in Cryptology, Proceedings of CRYPTO’95, Vol. 963 (LNCS), Springer-Verlag, Berlin (1995) pp. 29–42.
V. Shoup, On fast and provably secure message authentication based on universal authentication. In N. Koblitz (ed.) Advances in Cryptology, Proceedings of CRYPTO’96, Vol. 1109 (LNCS), Springer-Verlag, Berlin (1996) pp. 321–331.
D.R. Stinson (1994) ArticleTitleUniversal hashing and authentication codes Des. Codes Cryptogr. 4 369–380 Occurrence Handle10.1007/BF01388651
R. Taylor, Near optimal unconditionally secure authentication, In W. Wolfowicz and A. de Santis (eds.) Advances in Cryptology, Proceedings of EUROCRYPTO’94, Vol. 765 (LNCS), Springer-Verlag, (1994) pp. 245–255.
M. N. Wegman J. L. Carter (1981) ArticleTitleNew hash functions and their use in authentication and set equality J. Comput. Syst. Sci. 22 265–279 Occurrence Handle10.1016/0022-0000(81)90033-7
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Safavi-naini, R., Charnes, C. MRD Hashing. Des Codes Crypt 37, 229–242 (2005). https://doi.org/10.1007/s10623-004-3988-y
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-004-3988-y