On a necessary condition for the matching cryptosystem stability

On a necessary condition for the matching cryptosystem stability Aleksey I. Bolotnikov and Anwar A. Irmatov

arXiv:2607.23843v1 [cs.CR] 26 Jul 2026

Abstract The article contains a description of a possible attack on a matching cryptosystem and a defense with limited noise. A public key of a matching cryposystem consists of a graph and a weight vector-function on the edges of the graph with values from a finite field, where a private key contains another weight function, for which the corresponding alternating weighted path problem can be solved in polynomial time. There is a specific family of these secret weight functions that is considered in this article, for which some of the coordinates of its vector values are described as limited noise. We suggest a necessary condition for the matching cryptosystem stability in terms of dimensions of spans of weight vectors that correspond to specific sets of edges of the graph from the public key.

The representation of the maximum matching problem in a graph as a linear programming problem on a matching polyhedron, introduced by J. Edmonds in 1965 [1], is well known. Using the one-to-one correspondence between the matchings of a graph G and the vertices of the matching polyhedron P (G), one can define the weight of a vertex of P (G) as the weight of the corresponding matching from G. Then a weight function on the edges of the graph with values in a finite-dimensional space over a finite field Fp , where p is a prime, can be characterized as ”proper” or ”improper” using the following property of the matching polyhedron. Two vertices of P (G) are connected by an edge if and only if the symmetric difference of the matchings corresponding to these vertices consists of exactly one simple path of arbitrary length or one simple cycle of even length. Then we call the original weight function W on the edges of G ”proper” if, for the constructed weight function on the vertices of P (G), it is true that any two vertices of P (G) connected by an edge have different weights. We call W ”improper” in the opposite case, that is, when there are at least two adjacent vertices in P (G) with the same weight. In this case, a simple path or a simple cycle of even length (ei1 , ..., eid ), such that W (ei1 ) − W (ei2 ) + W (ei3 ) + ... + (−1)d−1 W (eid ) = 0 ∈ Fkp , will be the symmetric difference of two matchings corresponding to vertices of P (G) with the same weight. This allows us to formulate the alternating weighted path problem. Definition 1. The alternating weighted path problem: given a graph G, a prime number p, a positive integer number k, a weight function W : E → Fkp and a vector (a1 , ..., ak ) ∈ Fkp , the problem is to determine, if there is a sequence 1

of edges (ei1 , ..., eid ) in graph G that forms either a simple path of arbitrary length or a simple cycle of even length, such that W (ei1 ) − W (ei2 ) + ... + (−1)d+1 W (eid ) = (a1 , ..., ak ). In [2], the alternating weighted path problem was proven to be NP-complete. The authors of [2] proposed a new knapsack-type public-key encryption system in which the NP-completeness of the alternating weighted path problem is used to prove its security. Definition 2. A matching cryptosystem is an encryption system with the following scheme: • Public Key: Graph G(V, E), prime number p, natural number k, and weight function W : E → Fkp . • Private Key: A weight function Ŵ , for which the corresponding alternating weighted path problem can be solved in polynomial time, and an invertible linear operator M : Fkp → Fkp that transforms weights on edges, such that W is transformed into Ŵ . If any additional objects were used in the construction of Ŵ , they are considered a part of the private key as well. • Message Space: Simple paths and simple even cycles of G. • Encryption: For a path or an even cycle (ei1 , ..., eid ), compute (a1 , ..., ak ) = W (ei1 ) − W (ei2 ) + ... + (−1)d+1 W (eid ). • Decryption: Apply operator M to the received message A = (a1 , ..., ak ) and solve the easy alternating weighted path problem with weight function Ŵ (e) = M (W (e)) and the alternating sum of weights B = M (A). Consider the following family of quickly solvable alternating weighted path problems. Let G be a complete graph Km . Let p be a big enough prime number, p > 2 · 3m−2 . Let the dimension of the space of weights be k = m. Function Ŵ is defined as follows. We fix a numbering of vertices of the graph G : V = {v1 , ..., vm }. For an arbitrary pair of vertices vi , vj , i < j, let the weight of the edge (vi , vj ) be denoted as Ŵi,j = (ŵi,j,1 , ..., ŵi,j,k ). For each 1 ≤ i ≤ m−1 the sequence Ci = (ŵi,i+1,i , ŵi,i+2,i , ..., ŵi,m,i ) is a rapidly growing sequence: 3 · ŵi,j,i ≤ ŵi,j+1,i . In total, m(m − 1)/2 of elements ŵi,j,t are used as elements of rapidly growing sequences. Other elements ŵi,j,t are used as noise to improve the system’s resistance to attacks. Since there is m2 (m − 1)/2, of elements ŵi,j,t in general and m(m − 1)/2 of them used in rapidly growing sequences, m(m − 1)2 /2 of elements ŵi,j,t are used as noise. An algorithm that solves problems from this family, when Ci = (1, 3, ..., 3m−i−1 ), ŵi,j,t = 0, t ̸= i, t ̸= j, and ŵi,j,t = 1, t = j, in polynomial time, is described in [2]. The algorithm works as follows. If a path of arbitrary length or a cycle of even length (ei1 , ..., eid ), that satisfies Ŵ (ei1 ) − Ŵ (ei2 ) + ... + (−1)d+1 Ŵ (eid ) = (a1 , ..., ak ), passes through the first vertex, then a1 from (a1 , ..., ak ) can take one of the following values: 2

• 3i , 0 ≤ i ≤ m − 2, • p − 3i , 0 ≤ i ≤ m − 2, • 3j − 3i , 0 ≤ i < j ≤ m − 2, • p − (3j − 3i ), 0 ≤ i < j ≤ m − 2. There are m(m − 1) of these values in total. And if (ei1 , ..., eid ) does not pass through the first vertex, a1 = 0. By determining, if a1 is equal to any of those m(m − 1) + 1 values, we can discover edges on (ei1 , ..., eid ) that are adjacent to the first vertex. After weights of discovered edges are subtracted from (a1 , ..., ak ) with correct signs, the procedure is repeated for the second vertex, then for the third vertex, etc. Elements ŵi,j,t of the weight function can be divided into three categories. Elements ŵi,j,t with i = t are used in rapidly increasing sequences. Elements ŵi,j,t with i < t have the following property: values of these elements do not affect the functioning of the algorithm described above. These elements will be referred to as arbitrary noise. Elements ŵi,j,t with i > t, will be reffered to as limited noise, since aribtrary values of these elements can affect the ability of the algorithm to find a distinct solution in polynomial time. The following is an example of an alternating weighted path problem with a non-zero limited noise that can be solved in polynomial time. Instead of Cj = (ŵj,j+1,j , ..., ŵj,m,j ) = (1, 3, 32 , ..., 3m−j−1 ), let Cj = (aj,1 , ..., aj,m−j ), where ∀i 3 · aj,i−1 ≤ aj,i and aj,1 ≥ 3, and let ŵi,j,t = 1, t < i. Such a modification makes it necessary for each ai to additionally check if ai is equal to any of ±(aj,i −1) or ±(aj,t −aj,i )±1, and the total number of value comparisons stays polynomial. The necessity of using non-zero limited noise is due to the following result. Theorem 1. There is an attack that operates in time polynomial to the public key size, to which all systems with zero limited noise from the described family are vulnerable. Proof. Assume that we know the complete graph G(V, E) = Km , the prime number p > 2·max1≤i<j≤m (ŵi,j,i ), the function W : E → Fkp with the dimension of weight vectors k = m, and the transmitted message A1 = (a1 , ..., ak ). Assume that we do not know the numbering of vertices that was used in the definition of Ŵ , and this numbering is not connected to the numbering of edges of G that is used in the description of public key. Let Ŵ have zero limited noise. The first iteration of the attack consists of the following steps: 1. Find all vertices v with a property that the dimension of the span of the set F (v) = {W (e)|e ∈ E, e is not incident to v} is less then k. 2. Keep those vertices v that satisfy all the following conditions: • for every edge e that is incident to v, W (e) does not belong to the span of F (v); 3

• for every two distinct edges ei and ej that are incident to v, W (ei ) − W (ej ) does not belong to the span of F (v); • for every three distinct edges ei , ej and ek that are incident to v, W (ei ) − (W (ej ) − W (ek )) does not belong to the span of F (v); • for every four distinct edges ei , ej ,ek and et that are incident to v, (W (ei ) − W (ej )) − (W (ek ) − W (et )) does not belong to the span of F (v). 3. Check for the transmitted message A1 and each remaining vertex v, that A1 belongs to the span of F (v). If it does not belong, then discover either an edge e that is incident to v, such that A1 ± W (e) belongs to the span of F (v), or a couple of edges ei and ej that are incident to v, such that A1 ± (W (ei ) − W (ej )) belongs to the span F (v). If A1 belongs to span of F (v), we conclude, that the initial message does not pass through the vertex v. Let u be the vertex of the graph that was the first vertex in the vertex numbering that was used in the construction of Ŵ . We will show that u satisfies conditions 1 an 2. Since Ŵ has zero limited noise, for every edge e that is not incident to u, the first coordinate of the vector Ŵ (e) is zero. Therefore, the dimension of the span of the set F̂ (u) = {Ŵ (e)|e ∈ E, e is not incident to v} is less then k. Since Ŵ is obtained from W by applying an invertible linear operator, span(F (u)) and span(F̂ (u)) have the same dimension. Change of numbering on edges of G during the description of public key does not affect the dimension of span(F (u)), therefore u satisfies condition 1, and we will find at least one vertex after step 1. First coordinates of values of vector-function Ŵ on edges, that are incident to u, are not equal to zero and form a rapidly increasing sequence. Therefore, for every edge e that is incident to u, Ŵ (e) does not belong to span(F̂ (u)), and for every two distinct edges ei and ej that are incident to u, Ŵ (ei ) − Ŵ (ej ) does not belong to span(F̂ (u)). Now we will show that for every three distinct edges ei , ej , ek that are incident to u, Ŵ (ei ) − (Ŵ (ej ) − Ŵ (ek )) does not belong to span(F̂ (u)). Let the first coordinate of Ŵ (ei ) be denoted as α, let the first coordinate of Ŵ (ej ) be denoted as β, and let the first coordinate of Ŵ (ek ) be denoted γ. The first coordinate of Ŵ (ei ) − (Ŵ (ej ) − Ŵ (ek )) is equal to α − (β − γ) = α − β + γ. Assume that α − β + γ ≥ 0. We will show that in this case the greatest of these three values is either γ or α. Assume that this is not the case. Let β be the greatest of these three values. Then β ≥ 3α and β ≥ 3γ. Therefore, 2β ≥ 3(γ + α), and so β ≥ 1.5(γ + α) > γ + α, and α − β + γ < 0, which is a contradiction to the original assumption. Next, without any loss in generality, let α be the greatest of these three values. Since α ≥ 3β, α − β + γ > α − β > 0, and since p > 2 · α, and α ≥ 3γ, α − β + γ < α + β + γ < 2α < p. Therefore, the first coordinate of Ŵ (ei ) − (Ŵ (ej ) − Ŵ (ek )) is not equal to 0 (mod p), and 4

Ŵ (ei ) − (Ŵ (ej ) − Ŵ (ek )) does not belong to span(F̂ (u)). The case, where α − β + γ ≤ 0, is resolved in a similar way. Now we will show, that for every four distinct edges ei , ej , ek and et that are incident to u, (Ŵ (ei )−Ŵ (ej ))−(Ŵ (ek )−Ŵ (et )) does not belong to span(F̂ (u)). Let the first coordinate of Ŵ (ei ) be denoted as α, let the first coordinate of Ŵ (ej ) be denoted as β, let the first coordinate of Ŵ (ek ) be denoted as γ, and let the first coordinate of Ŵ (et ) be denoted as ϕ. The first coordinate of (Ŵ (ei )− Ŵ (ej ))−(Ŵ (ek )− Ŵ (et )) is equal to (α−β)−(γ −ϕ)) = ϕ+α−β −γ. Assume that ϕ + α − β − γ ≥ 0. We will show that in this case the greatest of these four values is either ϕ or α. Assume that this is not the case. Without any loss in generality, let β be the greatest of these four values. Then β ≥ 3α and β ≥ 3ϕ. Therefore, 2β ≥ 3(ϕ + α), and so β ≥ 1.5(ϕ + α) > ϕ + α, and ϕ + α − β − γ < 0, which is a contradiction to the original assumption. Next, without any loss in generality, let ϕ be the greatest of these four values. Since ϕ ≥ 3β, ϕ ≥ 3γ, ϕ + α − β − γ > ϕ − (β + γ) > 0, and since p > 2 · ϕ and ϕ ≥ 3α, ϕ + α − β − γ < ϕ + α + β + γ ≤ 2ϕ < p. Therefore, the first coordinate of (Ŵ (ei ) − Ŵ (ej )) − (Ŵ (ek ) − Ŵ (et )) is not equal to 0 (mod p), and (Ŵ (ei ) − Ŵ (ej )) − (Ŵ (ek ) − Ŵ (et )) does not belong to span(F̂ (u)). The case, where ϕ + α − β − γ ≤ 0, is resolved in a similar way. Because of the conditions on step 1 and 2, for every vertex v that passed these steps, we will correctly recover a single set of edges that are incident to v and belong to the initial message, as well as the signs of their weights in the computation of A1 , on step 3. After the third step, we obtain A2 from A1 by subtracting the weights of the reconstructed edges with the reconstructed signs, and then remove from graph G all vertices v remaining after step 2, along with all their adjacent edges. The i-th iteration of the attack consists of the same steps as the first, but is applied to the graph remaining after the (i − 1)-th iteration and the vector Ai , also remaining after the (i − 1)-th iteration. Note that after step 2 of the i-th iteration, a vertex ui is guaranteed to remain, which, when defining the function Ŵ , had the smallest index t among the indices of the vertices remaining in the graph after the (i − 1)-th iteration. For ui and each edge e remaining after the (i − 1)-th iteration, the t-th coordinate of Ŵ (e) is 0 if e is not incident with ui , and is not 0 if e is incident with ui . Thus, all the arguments for u also apply to ui , meaning that at each iteration we will delete at least one vertex. If at some point Ai = (0, 0, ..., 0), then instead of the next iteration, we collect the original message from all the edges recovered during the algorithm’s iterations. Note that at the first iteration step, the dimension of the linear span (m − 1)(m − 2)/2 of vectors of length m is calculated m times, at the second iteration step, no more than m − 1 + (m − 1)(m − 2) + (m − 1)(m − 2)(m − 3) + (m − 1)(m − 2)(m − 3)(m − 4) checks are performed to determine whether a vector of length m belongs to the linear span (m − 1)(m − 2)/2 of vectors of length m, and at the third iteration step, no more than (m − 1)(m − 2) + 2m + 1 checks are performed to determine whether a vector of length m belongs to the linear 5

span (m − 1)(m − 2)/2 of vectors of length m. When moving from one iteration to the next, at most three vectors of length m are added together, and some graph vertices and their adjacent edges are removed. In the original graph of m vertices, at least one vertex is removed after each iteration, so the algorithm will have at most m iterations. Thus, the algorithm runs in polynomial time in m. End of the proof. Non-zero limited noise is a necessary condition for a defense against such an attack, but not a sufficient one. A sufficient condition is to have dim(span(F (v))) = k for every vertex v. Here is a draft of a possible defense against this attack. 1. Let ŵi,j,i be elements of rapidly increading sequences (aj,1 , ..., aj,m−j ), where ∀i 3 · aj,i−1 ≤ aj,i and aj,1 ≥ 3. 2. For 1 ≤ t < i < j ≤ m, let ŵi,j,t = 1. 3. To set values for ŵi,j,t , 1 ≤ i < j ≤ m, i < t, we will choose D = (ei1 , ..., eik ) – a cycle of length k. 4. We complete the definition of Ŵ on D, such that the dimension of span({Ŵ (ei1 ), ..., Ŵ (eik )}) is equal to k. 5. For every vertex v we choose two edges, e1 (v) and e2 (v), that are not incident to v and are not a part of D, and complete the definition of Ŵ (e1 (v)) and Ŵ (e2 (v)), such that the dimension of the span of the set {Ŵ (ei1 ), ..., Ŵ (eik ), Ŵ (e1 (v)), Ŵ (e2 (v))} \ {Ŵ (e)|e ∈ D, e is incident to v} is equal to k. After that we have at least k(k − 7)/2 edges, whose weight Ŵ is not completely defined, with the remaining ŵi,j,t being an arbitrary noise. There is around Ω(k 3 ) of these undefined arbitrary noise elements ŵi,j,t that we can define in any way we need.

References [1] J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices // Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics. 1965. 69B, №1-2.125–130. [2] A. I. Bolotnikov, A. A. Irmatov. On the Matching Arrangement of a Graph, Improper Weight Function Problem and Its Application // Lobachevskii Journal of Mathematics. 2025. 46, № 3.1025–1039.

6