Several new families of graph-based key-dependent message authentication codes are proposed. The method allows for the generation of sensitive digests of electronic documents. Computer simulation justifies a high level of corresponding avalanche effect. Algorithms are based on walks on special algebraic graphs defined by equations over the arithmetic ring Zq, q = 2r, r ≥ 8. The cryptographic stability of proposed key-dependent message authentication codes is connected with a hard algebraic problem in investigating the systems of algebraic equalities in n variables of linear degree cn for some positive constant c. Growth of n increases the cryptographic stability. If the file is presented in the form of word in alphabet Zq of length n and length of the walk in the graph is fixed then the execution is a linear function of size O(n). Proposed algorithms can work with data in the form of texts, audio and video files, and files with various extensions such as .avi, .tif, .pdf, etc. The speed for constant m is linearly dependent on variable n. Growth of n increases the cryptographic stability. Algorithms can generate a digest of a prescribed size for a potentially infinite digital document.
A simplified model of the global information space can be imagined as a large, time-growing network of registered virtual users (individuals or institutions) who exchange information and can store it in electronic repositories located in the network or isolated from it. The size of files for exchange (electronic documents) tends to increase. An important category of the information space is the trust in documents. Users can use a symmetric algorithm with a private key to encrypt documents and a key exchange protocol to maintain the security of the encoding procedure. Certified public key algorithms can also be used to change the key. These methods ensure the security of the exchange channels.
It is easy to see that even using reliable encryption tools does not ensure complete trust in documents. The above justifies the importance and relevance of the following questions. Has the original document already been damaged? Hash function generation technologies are used to answer these questions. A hash function is needed to generate a compensated form of the original document. Note that the general hash function does not require a key or password.
For document verification and authentication tasks, so-called key hash functions (key hash functions, message authentication codes, or MACs) are required that are password-dependent.
In this paper, we propose new graph-based fast algorithms for creating digests of electronic files to detect cyberattacks, computer viruses, or other corruptions and verify data integrity. The cryptographic stability of several graph-based key-dependent hash functions is related to studying the navigation problem of finding the path between two graph vertices. In the case of the Cayley graph of the group G this is about decomposing the group element into a composition of known generators. Research on the message authentication codes based on Cayley graphs started from the case of Ramanujan graphs constructed by Lubotzky-Philips-Sarnak and Margulis [1, 2] and Pizer [3]. Charles, Lauter, and Goren [4] gave a construction of a hash function based on these graphs. This work was motivated by the successful use of Cayley Ramanujan graphs to construct lowdensity parity Check codes for satellite communications. Petit, Lauter, and Quisquater [5], Tillich and Zémor [6] investigated the properties of Message Authentication Codes. These results gave a full cryptanalysis of the scheme. Carvalho Pinto and Petit [7] also developed an improved pathfinding algorithm for these graphs.
Cayley-Ramanujan graphs form a family of graphs of large girth. Another family CD(n, q) of graphs with the fast growth of girth was suggested by Lazebnik, Ustimenko, and Woldar [ 8] (see also [9] where graphs D(n, q) with connected components isomorphic to CD(n, q) were introduced). Guinand and Lodge [10, 11] and other researchers used corresponding graphs to construct LDPC codes. Accordingly, McKay and Postol CD(n, q) based graphs have better properties than Cayley graphs of large girth [12].
The first message authentication codes based on CD(n, q) graphs were proposed by Polak and Zhupa [13] and Ustimenko and Pustovit [14]. In fact, the last paper uses a more general family of graphs CD(n, K) defined over an arbitrary commutative ring K. If K = Fq, then CD(n, K) = CD(n, q) and D(n, K) = D(n, q).
Ustimenko [15] proves that the girth of D(n, K) is at least n + 5 if K is an integral domain.
Message authentication codes of [14] are defined in terms of infinite graphs D(n, K[x1, x2, …, xm]) where K is a finite commutative ring. The cryptographical stability of these codes rests not only on the complexity of the corresponding navigation problem but also on the complexity of the general problem of solving a nonlinear system of algebraic equations.
In this paper, the authors present a family of new robust MACs based on several families of algebraic graphs, such as generalised Wenger graphs W(n, K), D(n, K), A(n, K), and other graphs.
All graphs under consideration are so-called linguistic graphs of type (1, 1, n – 1) (see [15] and further references) introduced as bipartite graphs with partition sets isomorphic to affine spaces Kn over a commutative ring K with unity for which the incidence relation triangular equations give me. In fact points and lines of the linguistic graph are tuples of kind (x) = (x1, x2, …, xn) and [y] = [y1, y2, …, yn] and (x) and [y] are incident if and only if aixi – bixi = fi(x1, x2, …, xi – 1, y1, y2, …, yi – 1), i = 2, 3, …, n where ai and bi are elements of multiplicative group K* of the K and fi ϵ K[x1, x2, …, xi – 1, y1, y2, …, yi – 1]. The first coordinates ϱ(x) = x1 and ϱ(y) = y1 define the colours of the point and line. The path in the graph formed by distinct vertices is the walk v0Iv1Iv2…vk – 1Ivk such that the colours of all points and lines are different.
If Fm(K) is a family of linguistic graphs, then the growth of m to infinity defines the projective limit F(K).
If Fm(K) is one of the families of graphs investigated in [16], then the walk v0Iv1Iv2…vk – 1Ivk of F(K) such that ϱ(vi)-ϱ(vi + 2) ϵ K* for I = 0, 1, …, k – 2 is the path.. Cayley-Ramanujan graphs form a family of graphs of large girth. Another family CD(n, q) of graphs with the fast growth of girth was suggested by Lazebnik, Ustimenko, and Woldar [8] (see also [9] where graphs D(n, q) with connected components isomorphic to CD(n, q) were introduced). Guinand and Lodge used corresponding graphs.
In this paper, we select the case when K = Zq, q = 2m, m ≥ 2, and the aforementioned linguistic graphs to define new families of message authentication codes. In Section 1, we introduce an algorithm for converting an arbitrary word (α1 α2, …, αn) written in the alphabet Zq into the digest (d1, d2, …, dk), which is the word of length k, k < n. These algorithms are defined in terms of arbitrary linguistic graphs. The complexity estimates are given in the Jordan-Gauss graphs defined in [16]. Section 2 is dedicated to the requirements on the cryptographical stability of message authentication codes. We discuss the general complexity of investigating a nonlinear system of equations, which justifies the security of the presented MACs. Section 3 introduces our algorithms regarding arbitrary linguistic graphs of type (1, 1, n – 1). Section 4 describes our selected algebraic graphs defined by the sparce quadratic system of equations and discusses their complexity and parameters of the corresponding algebraic systems of equations. Section 5 is dedicated to implementing MACs described in the previous section. Section 6 contains conclusive remarks.
The cryptographically stable hash function f must provide the practical impossibility of selecting a pair of links x and z with the same hash function value. The digest of a document created with a key-dependent hash function (MAC) uses the HMAC symbol. When users want to exchange correspondence secretly, verifying the author of the letter and the absence of changes when forwarding, they choose a shared MAC. Additionally, they use a standard symmetric encryption scheme.
In addition to cryptographical stability, the execution speed and a high indicator of avalanche effect are important. The avalanche effect can be measured in the following way. The HMAC of the generated file has to be computed. After this step, a chosen character of the original file has to be changed to another symbol, and HMAC for the new file has to be computed.
Finally, a comparison of the characters of two HMACs has to be made, and the percentage of changed characters has to be computed. For practical usage of HMAC, it is necessary to show that a change of an arbitrarily used character leads to a change of at least 40% of bits independently of the size of the tested files.
The introduced approach of using walks on algebraic graphs defined over a finite commutative ring K is helpful for the development of stream ciphers of Symmetric Cryptography (see, for instance, [17], [18], and further references) and constructions of HMACs. Other applications of graph theory to Symmetric Cryptography are considered in [19]. The method of generation of nonlinear transformations of free modules over commutative rings described in terms of special graphs defined by algebraic equations (so-called linguistic graphs) can be used in Non-commutative Cryptography instead of methods of generators and equations [20].
Studies of message authentication codes and НMACs are a hot topic. A complete list of all published papers within this direction is impossible; we only refer to some recent papers [21–29].
Recall that non-commutative cryptography is an active field of cryptology that explores cryptographic primitives and systems based on algebraic structures such as groups, semigroups, and non-commutative rings.
One of the earliest applications of non-commutative algebraic structure for cryptographic purposes was using groups to develop cryptographic protocols.
Noteworthy that arbitrary hash functions such as MD5 or SHA1 can be used to compose HMACs corresponding to MD5 and SHA-1 message authentication codes, which are known as HMAC-MD5 and HMAC-SHA-1, respectively. HMAC’s cryptographic performance depends on the cryptographic performance of the underlying hash function, the size of its hash output, and the size and quality of the key.
q = 2m Let us assume that q = 2m and nI is a bipartite linguistic graph with the partition sets formed by points (x) = (x1, x2, …, xn), xi ϵ Zq and lines [y1, y2, …, yn], yi ϵ Zq. Recall that (x)nI[y] if and only if the following equations hold
a2x2 – b2x2=f2(x1, y1), a3x3 – b3x3=f3(x1, x2, y1, y2),
… anxn – bnxn = fi(x1, x2, …, xn – 1, y1, y2, …, yn – 1).
We define the operator Na(v) of taking the neighbour of colour a via the following rule. If vertex v is the point (p) then Na(p) is the neighbouring line of this point with the colour a, i. e line [l] = [a, l2, …, ln] where li, i = 2, 3, …, n are defined recurrently from the equations a2p2 – b2l2 = p1a, a3p3 – b3l3 = f3(p1, p2, l1, l2), …, aipi – bili = fi(p1, p2, …, pi – 1, l1, l2, …, li – 1). If vertex v is the line [l] then Na(l) is the neighbouring point of the line with the colour a, i.e., point (p) = (a, p2, …, pn) where pi, i = 2, 3, …, n are defined recurrently from the equations a2p2 – b2l2 = al1, a3p3 – b3l3 = f3(p1, p2, l1, l2), …, aipi – bili = fi(p1, p2, …, pi – 1, l1, l2, …, li – 1).
In the following algorithms, we assume that the commutative ring K = Zq and the graph nI(K) internal parameters are among the input data. So, the operations of addition and multiplication of the ring are given by the loaded addition and multiplication tables. So we have embedded functions x + y and xꞏy where x and y are taken from the set of residues mod q. We will use another embedded power function xy, where x is from the domain of all odd residues and y is the residue modulo 2m – 1, which is the order of the multiplicative group K*. Parameters give the graph nI(K) ai, bi, i = 2, 3, …, n, and a list of polynomials fi is given in their standard forms, i.e., lists of monomial terms of fi, i = 2, 3, …, n shown in the lexicographical order. The data described above is public. The input tuple of our algorithm is of the kind (x1, x2, …, xn), xi ϵ K = Zq, q = 28s, s ≥ 1. So we can treat each xi as a tuple (z1, z2, …, zs) from Zb, b = 256 corresponding to the residue z1 + z2b + … + zsbs – 1 from Zq, and use the standard one-to-one correspondence between elements of Zb and ASCII codes of binary alphabet. So we can partition the text in binary alphabet into words of length s and treat each word as an element of the ring K = Zq.
The passive password of our secret key of our key dependent message authentication codes is
the tuples (α2, α3, …, αn), (γ2, γ3, …, γn) where αj ϵ (Zq)* and (λ2, λ3, …, λn) where λi are even residues
together with the tuple ((a(
The active password is formed by depth parameter m of size O(
We consider bijective transformations L of kind x1 → x1 + α2x2 + … + anxn, xj → xj, j = 2, 3, …, n
and the value of multivariate polynomial Q(x1, x2, …, xn) = x1(λ2x2 + γ2)a(
To control the speed of computation of Q we assume that ‘’almost all’’ parameters a(i), I ≥ 2, coincide with 1, i.e., the sum of parameters a(i) which are distinct from 1 is the selected constant d.
HMAC algorithm 1 (two versions)
Let (x1, x2, …, xn) be the intermediate point of the graph. We assume that it is the input of the algorithm.
1. Compute y(
Compute NQ(y(
z(
z(
We continue this process with m-steps to get y(m) = Na + β(
We have two versions of the algorithm via selection of y(m) or z(m) as the intermediate output v = (v1, v2, …, vn).
Finally, we select parameter k = O(nt), k < n, where 0 < t ≤ 1, and announce that (vn – k, vn – k + 1, vn – k + 2, …, vn) is the output of the algorithm.
HMAC algorithm 2.
The first step is the same as the first computation of the previous algorithm. So we get y(
2. y(
Similarly, we have two versions of the algorithm via the selection of y(m) or z(m) as the intermediate output v = (v1, v2, …, vn). Finally, we select parameter k = O(nt), k < n, where 0 < t ≤ 1, and announce that (vn – k, vn – k + 1, vn – k + 2, …, vn) is the output of the algorithm.
The multivariate maps (x1, x2, …, xn – k) → (vn – k(x1, x2, …, xn), vn – k + 1(x1, x2, …, xn), …, vn(x1, x2, …, xn)) for the computation of the outputs in the two algorithms presented above have different degrees and densities.
HMAC algorithm 3
This algorithms will use the map Q(x1, x2, …, xn) of Kn on Kn of kind x1 → x1(λ2x2 + γ2)a(
We take (x) = (x1, x2, …, xn) and compute Q(x) = (a, x2, x3, …, xn) = y(
Then we use recursive procedures of the MAC Algorithm 1 to compute recurrently y(
a. General Jordan-Gauss graphs
Accordingly to [16], we refer to the linguistic graph nI(K) given by equations of kind (
f2 = a2(
+ an(2, n – 1)x2yn – 1+ + ...+ + an(n – 1, n – 1)xn – 1yn – 1.
We refer to the graph as a dense Jordan-Gauss if all coefficients ai(k, l) as above are different from zero. If nI(K) is a dense Jordan-Gauss graph, we can keep it secret by adding the coefficients of the graph equations to the passive password. The theoretical complexity of the presented above algorithms is O(n2). b. Special Jordan-Gauss graphs We select for the implementation several well-known sparse Jordan-Gauss graphs for which the number of nonzero coefficients ai(k, l) is O(n).
Example 4.2.1. Generalised Wenger graph.
This is a Jordan-Gauss graph with partition its isomorphic to Kn, such that point (x1, x2, …, xn) is incident to line [y1, y2, …, yn] if and only if the following equations hold x2 – y2 = x1y1, x3 – y3 = x1y2,
… xn – yn = x1yn – 1.
Wenger introduced this family of graphs in [30] for the case of K = Zp where p is prime. Example 4.2.2.
Let K stand for an arbitrary commutative ring with unity. We consider the graph D(K) with
points and lines which are infinite tuples over K of kind (p) = (p1, p2, …, pi, pi + 1, …), [l] = [l1, l2, …, li,
(
Graphs D(n, K), n ≥ 2, were introduced in [15]. In fact, they are homomorphic images of D(K) under a homomorphism sending (p) into (p1, p2, …, pn) and [l] into [l1, l2, …, ln]. So the incidence Jordan-Gauss graph D(n, K) is defined by the first n – 1 equations in the list presented above.
The graph G’s girth g(G) is the size of its minimal cycle. The forest is the graph without a cycle. The connected forest is called the tree [31]. If K is an integrity domain, i.e., K does not contain zero divisors, then the girth D(n, K) of is at least n + 5 [15]. These facts were established in [9] for the case of finite fields.
Example 4.2.3.
Infinite Jordan-Gauss graph A(K) with points (p) = (p1, p2, …, pi, pi + 1, …) and lines [l] = [l1, l2, …, li, li + 1, …] with coordinates from commutative ring K is defined by equations
Graphs A(n, K), n ≥ 2 introduced in [15] are homomorphic images of A(K) under a homomorphism sending (p) into (p1, p2, …,pn) and [l] into [l1, l2,…, ln]. So the incidence of JordanGauss graph A(n, K) is defined by the first n – 1 equations presented above.
If K is an integrity domain, then A(K) is the forest (see [16] and further references), the girth of A(n, K) is ≥ [(n + 2) / 2].
We can see that the quadratic monomial term on the right-hand side of the equations uniquely defines each equation of D(K). Let D be the set of monomial terms of the equation of D(K), and A be the set of monomial terms of the A(K) equations. Note that the deletion of equations of D(K) with monomial terms from D – A, together with corresponding equations, defines the homomorphism of the forest D(K) onto A(K).
Example 4.2.4
The equations of the graph D(K) and corresponding quadratic monomial terms are ordered
accordingly to the list (
In the case of Examples 4.2.1–4.2.4, the complexity of the generating procedure of the message authentication codes is O(n).
In cases 4.2.1–4.2.3, we assume that the graphs are known to the public. In the case of the graph
of Example 4.2.4, we can add the parameter n to the passive password.
(
We investigate our algorithms in the commutative ring Z256, which is the same size as the binary
alphabet. We select the cases of sparse graphs described in Examples 4.2.1–4.2.4 for the
implementation. We choose the parameters of the passive password as follows. Only O(
We refer to d = 2m as the length of the walk. In the cases of 4.2.2–4.2.4, the change of active password leads to the shift in intermediate output v = (v1, v2, …, vn). The walk’s computation speed is the same in all cases 4.2.1–4.2.4 because Jordan-Gauss graphs have equations with the single quadratic monomial terms in each equation. Note that the time execution does not depend on parameter k, which defines the digest size.
Computer simulations demonstrate a high level of the avalanche effect. We can see that a single change of the character of the initial file or a single shift in the character of the active password leads to a change of 98% of the characters of the output. Not that this is essentially better than in the case of HMAC [32] when the change of characters of the initial file leads to the change of 47-50 characters of the output.
Our software is written in C++; therefore, it is portable and runs on many platforms, such as Unix/Windows. To evaluate our algorithm’s performance, we use files of different sizes. We measure the time (Fig. 1) needed to produce the digest in milliseconds. And the file size of files in kilobytes for passwords of length d. We use an average PC with a Pentium 3.00 GHz, 2GB of RAM, and Windows 7. The following diagram presents the time of the algorithm’s execution in the case of graphs 4.2.2. on in the case of graphs 4.2.2.
The paper proposes new fast graph-based algorithms for creating sensitive digests of electronic files to detect cyberattacks, computer viruses, or other damages and check data integrity. These tools can be used to defend a virtual organization and audit all files after a registered intervention. Cryptographic stability of new key-dependent hash functions is associated with complex algebraic problems, such as the study of systems of algebraic equations of a considerable degree and the decomposition of a nonlinear transformation into the composition of given generators. These facts justify resistance of digests against adversary attacks with the use of algorithms in terms of a Turing machine or the theory of Quantum Computation.
Algorithms of digest generation use the idea of presentation of files in the form of sequences (words) of elements of the arithmetical ring modulo 2m. The presented families of graphs form sequences that define the projective limit of finite graphs given by equations.
Affine transformations and polynomial maps of high degree are used to hide the transformation induced by the walk on the graph. This scheme is new,
Implemented according to this scheme, a family of fast algorithms was investigated via computer simulations on large real data sets. Changing a single document character in the binary alphabet causes the change of most characters of the produced digest (≥98%). This property and the evaluation of the time execution of software programs justify the potential of practical usage of the implemented algorithm for cybersecurity tasks.
Declaration on Generative AI While preparing this work, the authors used the AI programs Grammarly Pro to correct text grammar and Strike Plagiarism to search for possible plagiarism. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content.