Keyed hash function from large girth expander graphs

MaRDI QIDQ5086121zbMATH OpenFDO

Authors Monika Polak, Eustrat Zhupa

Publication date 1 July 2022

Full work available at URL https://arxiv.org/abs/1903.06267, http://albanian-j-math.com/archives/2022-02.pdf

zbMATH Keywords

authenticationexpander graphskeyed hash functionlarge girth graphs

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

Cited in

(5)

• Cryptographic hash functions from sequences of lifted Paley graphs
• scientific article; zbMATH DE number 1737506 (Why is no real title available?)
• Cryptographic hash functions from expander graphs
• Collisions for the LPS Expander Graph Hash Function
• scientific article; zbMATH DE number 177615 (Why is no real title available?)

Describes a project that uses

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)