Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Рассмотрим вторую стратегию (первая стратегия приводит к тем же самым оценками вероятности непротиворечивости — см. упражнение 4.9). Если Ева правильно настроила свой приемник е*, т.е. = Pi, то она правильно распознает состояние Pi(aj) и, следовательно, бит <ц. Это означает, что Боб также получит правильный бит. Таким образом, в этом случае присутствие Евы останется незамеченным. Поскольку вероятность того, что Ева правильно настроит г-й приемник, равна 1/2, вероятность не обнаружить перехват в г-й позиции также равна 1/2.
Если Ева настроила г-й приемник неправильно, то г-е состояние фотонов окажется неверным, и она перешлет Бобу неправильный бит. Несмотря на это, приемник Боба изменит неверное состояние на ±45°, причем вероятность каждого направления равна 1/2. Следовательно, вероятность того, что Боб получит правильный или неправильный бит, в обоих случаях равна 1/2. Если Боб правильно распознал бит, Ева останется незамеченной. Обратите внимание на то, что эта ситуация представляет собой частный случай, когда Ева передала неверный бит,
154
Часть II. Математические основы
но, тем не менее, осталась нераскрытой. Вероятность последнего события также равна 1 /2. Следовательно, поскольку приемники Евы и Боба настраиваются независимо друг от друга, вероятность того, что Ева останется незамеченной после передачи неверного бита, равна | х | =
Суммируя вероятности, вычисленные выше, приходим к выводу, что вероятность не заметить перехват на г-й позиции равна \ + \ = §¦ Поскольку для того, чтобы завладеть распределенным ключом, Ева должна прослушивать все просеянные состояния, Алиса и Боб сравнивают ? случайных тестовых битов и любое несовпадение считают сигналом опасности (это правило представляет собой критерий "единогласного голосования", в котором не допускается ни одного несовпадения). Вероятность не заметить перехват на всех позициях равна Эта величина является вероятностью ошибки, связанной со стойкостью. Она очень быстро стремится к нулю.
Вероятность ошибки, связанной с неполнотой
Оценим вероятность ошибки, связанной с неполнотой протокола. Пусть настройки т поляризаторов Алисы задаются случайным двоичным вектором V = = (vi, г>2, • • • > vm)t а настройки приемников Боба — вектором W = (w\, W2,..., гит). Ошибка, связанная с неполнотой протокола, возникает, когда вектор
V © W = (Vi © Wl, Vi © W2, ¦ ¦ ¦, vm © wm)
содержит меньше m/10 нулей. Поскольку настройки Алисы и Боба независимы и равновероятны, вектор V©W должен быть случайным равномерно распределенным вектором, состоящим из т бит. Вероятность того, что вектор У©W содержит г нулей, имеет биномиальное распределение для т испытаний и г успехов, где вероятность успеха равна 0,5. Очевидно, что наиболее вероятное количество нулей в векторе V © W равно т/2. Иначе говоря, центральный член биномиального распределения находится в точке [^^J. Следовательно, точка ^ расположена далеко слева от точки L*2^] * Итак, вероятность ошибки, связанной с неполнотой протокола, равна
Prob Jzeroes_in(V © W) <
и представляет собой площадь фигуры, ограниченной левым хвостом биномиального распределения. Учитывая оценки левого хвоста биномиального распределения (3.5.8), получим оценку вероятности ошибки, связанной с неполнотой протокола.
Prob [zeroes infV © W) < ^1 < °'5 (m + 1—ig) < А для m ^ 2. L !0J (0,5(m + l)-^)2 rn
Следовательно, вероятность того, что Алиса и Боб не завершат протокол на тре-т см этапе, равна 1 — ^.
Глава 4. Вычислительная сложность
155
Вероятности двусторонних ошибок
Итак, вероятности двусторонних ошибок протокола 4 1 оцениваются следующим образом. Вероятность ошибки, связанной с неполнотой протокола, удовлетворяет следующему неравенству.
[771 Количество просеянных битов ^ — |
1 3
Среди тп распределенных состояний фотонов > 1--.
J тп
Вероятность ошибки, связанной с противоречивостью протокола, удовлетворяет следующему неравенству.
Prob [Ева не обнаружена | Алиса и Боб проверили I тестовых битов] ^
Следует отметить, что оценка левого хвоста величиной ^, полученная по неравенству (3.5.8), является слишком грубой. Левый хвост стремится к нулю быстрее, чем (см. упражнение 3.9).
Оценки вероятностей ошибок протокола QKD показывают, что он вполне приемлем для практики. В реальных приложениях условленный канал, по которому Алиса и Боб ведут открытый обмен информацией, должен обеспечивать аутентификацию. Это необходимо для того, чтобы секретный ключ был распределен среди полномочных партнеров. Проблемы аутентификации рассматриваются в части IV.
Появление коммерческих QKD протоколов ожидалось в 2004 году [268].
4.4.6 Эффективные алгоритмы
Изучая классы полиномиальных алгоритмов и подклассы вероятностных полиномиальных алгоритмов (РРТ), мы установили следующие включения.
^ _ W (Монте-Карло) __„
PCZPPC 4 v ' <ZBWC\W.
РР(Лас-Вегас)
Алгоритмы, способные решать задачи из этих классов, называются эффективными.
Определение 4.6 (Эффективный алгоритм). Эффективным называется детерминированный или рандомизированный алгоритм, время выполнения которого полиномиально зависит от размера исходных данных.
