Система неравенств и аутентификация

Для всех p ∈ (0;1) найдите минимальное значение выражения (x₁ + x₂) ·p + x₃ ·(1−p) при условии, что

1) 0 < x₁ < 1; 0 < x₂ < 1; 0 < x₃ < 1,

2) x₁+x₂+x₃=1,

3) x₁ ≤ x₂; x₃ ≤ x₂; x₂·(1−p) ≤ x₁ ·p.



---

• Решение

Решение

Предварим решение этой задачи небольшим отступлением о кодах аутентификации, поясняющим происхождение ее формулировки.

При передаче информации по незащищенному (общедоступному) каналу связи возникает задача защиты от активных атак со стороны злоумышленника. Под активными атаками понимают попытки фальсификации (имитации) и модификации (подмены) сообщения.

Цель активных атак - дезинформация получателя. Не вдаваясь в детали, сообщим, что сегодня имеется техническая возможность проведения подобных атак.

Для противодействия активным атакам используются так называемые коды аутентификации (кратко - A-коды). Они дают возможность получателю сообщения проверить его подлинность (или аутентичность). Проверка использует некий секрет, известный лишь отправителю и получателю сообщения, точно так же, как при обеспечении секретности используется секретный ключ шифрования. В общем виде код аутентификации представляет собой совокупность (S,E,M) трех конечных множеств, где S - множество состояний источника, E - множество правил кодирования, M - множество сообщений. Каждый элемент e &isn; E представляет собой отображение e:S® M. Правила кодирования « кодируют» состояния источника s &isn; S в сообщения m &isn; M. Таким образом, сообщения передают информацию о наблюдаемом отправителем состоянии источника. Таковыми могут быть, например, результаты подбрасывания монеты при проведении жребия по телефону или обычные текстовые сообщения. Отображение e &isn; E должно быть « обратимым», чтобы по данным m и e можно было однозначно восстановить s. Формально это требование записывается с помощью отображения f_ecolonM® S И{0}, где 0 - число нуль (не принадлежащее S) и

Так вот, в определении A-кода требуется, чтобы выполнялось равенство f_e(e(s))=s для любых s &isn; S и e О E. Как стороны A и B используют A-код для аутентификации передаваемой информации? Прежде всего, они сообща выбирают (втайне от злоумышленника) правило кодирования e &isn; E. Пусть A желает передать состояние источника s &isn; S. Тогда он вычисляет m = e(s) и посылает m к получателю B по каналу связи. Получив m, B использует то же правило кодирования e для вычисления f_e (m). Если f_e(m) № 0, то m принимается как аутентичное, в противном случае - нет. На практике используются лишь такие A-коды, для которых вычисление f_e (m) производится так же просто, как и e(s). При анализе надежности защиты от активных атак с помощью A-кодов предполагается, что злоумышленник знает об A-коде все, кроме секретного правила кодирования (ключа). Он (злоумышленник) проводит атаки на основе анализа свойств A-кода. При этом его действия являются наиболее целесообразными с точки зрения достижения успеха атаки. Приведем пример. Рассмотрим A-код, для которого S = {H,T} (сокращение от head - герб, tail - решка), E = {e₁ ,e₂ ,e₃ }, M = {m₁, m₂, m₃ }. Действие правил кодирования запишем в виде таблицы (матрицы кодирования): В этой таблице указано, например, что состояние источника H кодируется с помощью правила e₁ в сообщение m₁, итд Пусть состояние источника выбирается случайно (как при подбрасывании монеты). При этом одно из двух состояний появляется чаще другого (как при использовании несимметричной монеты). Пусть p - « доля» состояния H. Тогда (1 -p) - « доля» состояния T. Например, если при бросании монеты она в среднем в двух случаях из трех выпадает гербом, то p = 2/3. С целью уменьшения шансов на успех злоумышленника A и B выбирают правило кодирования случайно. Пусть при этом p(e_i) = x_i - « доля» e_i, i = ѕ1,3. Числа x_i лежат в интервале (0,1), и их сумма равна 1. Пусть P(E) = (x₁, x₂, x₃). Эта тройка чисел называется стратегией защиты. Эта стратегия выбирается стороной защиты с таким расчетом, чтобы минимизировать « шансы» злоумышленника на успех. Не вдаваясь в детали, укажем, что для данного A-кода при выбранной стратегии P(E) эти шансы злоумышленника характеризуются величиной


L( _ x   ) = max {px1;(1 - p)x2 } + max {(1 - p)x1 ;(1 - p)x3 } + max {px2 + px3 }.pagebreak

Сторона защиты выбирает оптимальную стратегию P⁽⁰⁾(E) так, чтобы минимизировать L(ѕx). Таким образом, возникает задача вычисления min_{ѕx О D} L(ѕx), где


D = {(x1 ,x2 ,x3 )colon 0 < xi < 1, x1 + x2 + x3 = 1}.

Этот минимум можно вычислить, разбивая область D на подмножества D_j, j = ѕ1,8, в которых раскрывается каждый максимум в выражении L(ѕx). Например, в случае, когда L(ѕx) имеет вид L(ѕx) = p(x₁ + x₂ ) + (1 - p)x₃. Как раз эта задача была предложена на олимпиаде. Решается она, например, следующим образом. Заметим, прежде всего, что из условий следует неравенство p і 1/2. В самом деле,


x1 p і x2 (1 - p) і x1 (1 - p),

откуда p і 1 - p или 2p і 1. Выразив x₃ из условия x₁ + x₂ + x₃ = 1, получим следующее выражение:


L( _ x   ) = (x1 + x2 )(2p - 1) + 1 - p.

Легко видеть, что минимальное значение это выражение принимает при максимально большом значении x₃. Остается найти достижимую верхнюю границу для значения x₃. Из цепочки неравенств x₃ Ј x₂ Ј [(p)/(1 - p)]x₁ получаем


1 = x1 + x2 + x3 і 1 - p p x3 + x3 + x3 ,

откуда следует, что x₃ Ј [(p)/(p + 1)]. Ясно, что равенство x₃ = [(p)/(p + 1)] достигается лишь в случае, когда в указанной цепочке неравенств выполняются равенства, те если x₃ = x₂ = [(p)/(1 - p)]x₁. Мы нашли максимальное значение x₃. Отсюда получаем, что


min L( _ x   ) = ж и 1 - p p + 1 + p p + 1 ц ш p + p p + 1 (1 - p) = p(2 - p) p + 1 .