We apply methods and techniques of tropical optimization to develop a new theoretical and computational framework for the implementation of the Analytic Hierarchy Process in multi-criteria problems ...of rating alternatives from pairwise comparison data. In this framework, we first consider the minimax Chebyshev approximation of pairwise comparison matrices by consistent matrices in the logarithmic scale. Recasting this approximation problem as a problem of tropical pseudo-quadratic programming, we then write out a closed-form solution to it. This solution might be either a unique score vector (up to a positive factor) or a set of different score vectors. To handle the problem when the solution is not unique, we develop tropical optimization techniques of maximizing and minimizing the Hilbert seminorm to find those vectors from the solution set that are the most and least differentiating between the alternatives with the highest and lowest scores, and thus are well representative of the entire solution set.
Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion ...of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: "Given that
for a unique t and matrices A, V, F of appropriate dimensions, find this t." We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.
Since the existing tropical cryptographic protocols are either susceptible to the Kotov-Ushakov attack and its generalization, or to attacks based on tropical matrix periodicity and predictive ...behavior, several attempts have been made to propose protocols that resist such attacks. Despite these attempts, many of the proposed protocols remain vulnerable to attacks targeting the underlying hidden problems, one of which we call the tropical two-sided discrete logarithm with shift. An illustrative case is the tropical Stickel protocol, which, when formulated with a single monomial instead of a polynomial, becomes susceptible to attacks based on solutions of the above mentioned tropical version of discrete logarithm. In this paper we will formally introduce the tropical two-sided discrete logarithm with shift, discuss how it is solved, and subsequently demonstrate an attack on a key exchange protocol based on the tropical semiring of pairs. This particular protocol is compromised due to the existence of efficient (albeit heuristic) solution of the tropical two-sided logarithm problem, and this highlights the ongoing challenges in search of a "good" key exchange protocol in tropical cryptography.
We present necessary and sufficient criteria for a max-algebraic supereigenvector, i.e., a solution of the system A⊗x≥x with A∈R‾n×n in max-plus algebra, to be an extremal. We also show that the ...suggested extremality criteria can be verified in O(n2) time for any given solution x.
(K,L)-eigenvectors in max-min algebra Gavalec, Martin; Němcová, Zuzana; Sergeev, Sergeĭ
Fuzzy sets and systems,
05/2021, Letnik:
410
Journal Article
Recenzirano
Odprti dostop
Using the concept of (K,L)-eigenvector, we investigate the structure of the max-min eigenspace associated with a given eigenvalue of a matrix in the max-min algebra (also known as fuzzy algebra). In ...our approach, the max-min eigenspace is split into several regions according to the order relations between the eigenvalue and the components of x. The resulting theory of (K,L)-eigenvectors, being based on the fundamental results of Gondran and Minoux, allows to describe the whole max-min eigenspace explicitly and in more detail.
A tropical version of Stickel’s key exchange protocol was suggested by Grigoriev and Shpilrain (2014) and successfully attacked by Kotov and Ushakov (2018). We suggest some modifications of this ...scheme that use commuting matrices in tropical algebra and discuss some possibilities of attacks on these new modifications. We suggest some simple heuristic attacks on one of our new protocols, and then we generalize the Kotov and Ushakov attack on tropical Stickel’s protocol and discuss the application of that generalized attack to all our new protocols.
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T
1
, T
2
}, where T
1
is the ...weak CSR threshold and T
2
is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T
1
and T
2
, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T
1
, which are generalizations of the bounds of Wielandt and Dulmage-Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.
PDF
