Переход с неравенством маркова.

[error420]

Здравствуйте.

Я разбирался с доказательством леммы 2 в статье https://iacr.org/archive/eurocrypt2009/ ... 790461.pdf .
Если есть желание - можно посмотреть там, но здесь я постораюсь кратко изложить проблемму.

Пусть у нас есть функция $F: \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^m$. $\{0,1\}^k$ - данное множество будем называть множеством ключей. Пусть ключ $k$ генерируется в соответствии с распределением $K_\lambda$. Мин-энтропия данного распределения равна $k-\lambda$. Предположим что есть некий алгоритм который получает на выходе единицу с вероятностью больше, чем $\varepsilon$, если ключ сгенерирован в соответствии с распределением $K_\lambda$. Иначе мы можем написать $ \sum_{k \in K_\lambda} \Pr[k]\cdot \varepsilon_k > \varepsilon$, где $\varepsilon_k$ вероятность, что алгоритм выдаст единицу для ключа $k$. Далее в статье утверждается, что в соответствии с неравенством маркова и на основе нашего предположения мы получаем, что $\Pr_{k \leftarrow K_\lambda}[\varepsilon_k \geq \varepsilon/2] \geq \varepsilon/2$. Что значит, если мы генерируем случайный ключ в соответствии с распределением $K_\lambda$, то вероятность, что $\varepsilon_k \geq \varepsilon/2$ больше, чем $\varepsilon/2$. Данный переход мне не ясен. У меня не получилось с помощью неравенства маркова получить данную оценку.

По сути в неравенстве Маркова мы берем $X={K_\lambda}$, а значения $X$ это $\varepsilon_k$. Тогда мы получаем, что $E(X) > \varepsilon$. Затем с помощью неравенства Маркова мы получаем $\Pr_{k \leftarrow K_\lambda}[\varepsilon_k>\varepsilon/2] \leq E(X)/(\varepsilon/2) < 2$. Это вообще не то, что нам нужно.