This article is cited in
2 papers
Theoretical Backgrounds of Applied Discrete Mathematics
The solution of some classes of matrix games
A. Yu. Zubov Lomonosov Moscow State University, Moscow, Russia
Abstract:
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$.
Keywords:
matrix game, optimal mixed strategy, authentication code, probabilities of success of impersonate and substitute.
UDC:
519.7,
519.832
DOI:
10.17223/20710410/34/2
Fulltext:
PDF file (684 kB)