[Submitted on 26 Jul 2026]

View PDF HTML (experimental)

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.

Submission history

From: Aleksey Bolotnikov [view email]
[v1] Sun, 26 Jul 2026 21:14:12 UTC (6 KB)