The solution of some classes of matrix games

A. Yu. Zubov

Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 17-37.

Résumé

The approach of G. Simmons to estimating an authentication code ($\mathrm{A}$-code) security is used for solving matrix games. The approach simulates the behavior of the information sender and receiver and an attacker (opponent) as players in matrix games. The imitation attack is represented by a game, the matrix of which coincides with the incidence matrix of $\mathrm{A}$-code. The step of player 1 is the choice of a matrix line (an encoding rule), the step of player 2 is the choice of a matrix column (the simulated message). The substitution attack is represented by a game in which the step of player 1 is the choice of encoding rule ($e$), the step of player 2 is the choice of a mapping ($\varphi$) without immovable points which maps the set of $\mathrm{A}$-code messages to itself. The element $\sigma(e,\varphi)$ of the game matrix equals the probability that, for given $e,\varphi$ and randomly selected state of a source $s$, the message $n = \varphi(m)$ replacing an actual message $m = e(s)$ is taken as an authentic one. In theorems 1 and 2, it is proven that, for given $\mathrm{A}$-code and probability distribution on the set of encoding rules, the values of the corresponding games are equalled to the least probabilities for success of imitation or substitution. For games corresponding to $\mathrm{A}$-code with two source states, $N$ encoding rules and $N$ messages, $N > 2$, the solutions are obtained with the help of these theorems. In theorems 3 and 5, the values $v_1$ and $v_2$ of games with the matrices in sizes $N\times N$ and $N\times(N-1)^N$ respectively, representing the imitation and substitution attacks, as well as the optimum mixed strategies of players, are obtained. The value $v_2$ is expressed through the probability of choosing one of two source states and $v_1 = 2/N$. Theorem 4 generalizes the result of theorem 3 for $\mathrm{A}$-code with $k$ states of source, $2\leq k\leq N$.

Détail

Mots-clés : matrix game
Keywords: optimal mixed strategy, authentication code, probabilities of success of impersonate and substitute.

Bibliographie

[1] Zubov A. Yu., Can combination of the active attacks to bring about greater damage for system of protection to information, than each of attacks separately?, Moscow State Forest University Bulletin — Lesnoy Vestnik, 2008, no. 4(61), 144–148 (in Russian)

[2] Zubov A. Yu., “The decision of one matrix game”, Moscow State Forest University Bulletin — Lesnoy Vestnik, 2008, no. 6(63), 173–179 (in Russian) | MR

[3] Zubov A. Yu., “On the game-theoretical approach to the analysis of authentication codes”, Diskr. Mat., 21:3 (2009), 45–72 (in Russian) | DOI | Zbl

[4] Zubov A. Yu., “On the choice of the defence strategy for an authentication code with two-state source”, Diskr. Mat., 21:4 (2009), 135–147 (in Russian) | DOI | MR | Zbl

[5] Simmons G. J., “A game theoretical model of digital message authentication”, Congressus Numerantium, 34 (1982), 413–424 | MR | Zbl

[6] Simmons G. J., “Authentication theory”, Coding theory, LNCS, 196, 1984, 411–431

[7] Zubov A. Yu., Authentication Codes Mathematics, Gelios ARV Publ., M., 2007 (in Russian)

[8] Vorob'ev N. N., Game Theory, Nauka Publ., M., 1985 (in Russian) | MR