Keyed hash function from large girth expander graphs

zbMATH Open1497.94112arXiv1903.06267MaRDI QIDQ5086121FDOQ5086121

Monika Polak, Eustrat Zhupa

Publication date: 1 July 2022

Abstract: In this paper we present an algorithm to compute keyed hash function (message authentication code MAC). Our approach uses a family of expander graphs of large girth denoted $D(n,q)$, where $n$ is a natural number bigger than one and $q$ is a prime power. Expander graphs are known to have excellent expansion properties and thus they also have very good mixing properties. All requirements for a good MAC are satisfied in our method and a discussion about collisions and preimage resistance is also part of this work. The outputs closely approximate the uniform distribution and the results we get are indistinguishable from random sequences of bits. Exact formulas for timing are given in term of number of operations per bit of input. Based on the tests, our method for implementing DMAC shows good efficiency in comparison to other techniques. 4 operations per bit of input can be achieved. The algorithm is very flexible and it works with messages of any length. Many existing algorithms output a fixed length tag, while our constructions allow generation of an arbitrary length output, which is a big advantage.

Full work available at URL: https://arxiv.org/abs/1903.06267

Recommendations

• Cryptographic hash functions from expander graphs
• Cryptographic hash functions from sequences of lifted Paley graphs
• scientific article
• From graphs to keyed quantum hash functions
• Fast pseudorandom functions based on expander graphs

zbMATH Keywords

authenticationexpander graphskeyed hash functionlarge girth graphs

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62) Expander graphs (05C48)

Cites Work

• Expander graphs and their applications
• Ramanujan graphs
• Explicit constructions of graphs without short cycles and low density codes
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit construction of graphs with an arbitrary large girth and of large size
• Graphs of prescribed girth and bi-degree
• A new series of dense graphs of high girth
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Note on the girth of Ramanujan graphs
• Cryptographic hash functions from expander graphs
• Polarities and \(2k\)-cycle-free graphs
• Title not available (Why is that?)
• Hash functions and Cayley graphs
• Constructions for cubic graphs with large girth
• Explicit construction of regular graphs without small cycles
• Collisions for the LPS Expander Graph Hash Function
• The sextet construction for cubic graphs
• Girths of bipartite sextet graphs
• Title not available (Why is that?)
• Ramanujan graphs and Hecke operators
• Title not available (Why is that?)
• On the extremal graph theory for directed graphs and its cryptographical applications
• On the comparison of cryptographical properties of two different families of graphs with large cycle indicator
• On some properties of graph based public keys
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Title not available (Why is that?)
• Cryptographic hash functions from expander graphs
• Collisions for the LPS Expander Graph Hash Function
• Title not available (Why is that?)
• Cryptographic hash functions from sequences of lifted Paley graphs

Uses Software

• Diehard

This page was built for publication: Keyed hash function from large girth expander graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5086121)