Безопасная аутентификация по слабому ключу без утечки информации — Национальная библиотека им. Н. Э. Баумана

Основная конструкция

Теперь обратимся к нашей конструкции протокола аутентификации сообщений с секретным долгосрочным ключом (Определение 5). В конструкции мы будем использовать DW-MAC как строительный блок. Говоря неформально, основная идея в том, чтобы зашифровать аутентификационную метку DW-MAC используя одноразовую запись, предотвращающую утечку ключа.

Такой ключ создаётся в последовательности вопросов-ответов, из смеси локальной и общей случайности. В дополнение к этому, мы используем DW-MAC протокол для аутентификации некоторых ядер экстракторов, которые появляются в конструкции, для предотвращения утечки из решений Боба.

Пусть laExt{0,1}n×{0,1}d→({0,1}l)t{displaystyle laExt^{{}0,1}^{n}times {0,1}^{d}to ({0,1}^{l})^{t}}
будет (kK,ϵK){displaystyle (k_{K},epsilon _{K})} предугадывающим экстрактором.

Пусть
Ext{0,1}n×{0,1}v→{0,1}q{displaystyle Ext^{{}0,1}^{n}times {0,1}^{v}to {0,1}^?} будет
(kZ,ϵZ){displaystyle (k_{Z},epsilon _{Z})}-сильным экстрактором. Пусть MAC:
({0,1}l)t×({0,1}m×{0,1}d×{0,1}v)→{0,1}s{displaystyle ({0,1}^{l})

^{t}times ({0,1}^{m}times {0,1}^{d}times {0,1}^{v})to {0,1}^{s}} будет (ϵ,λ ϵ){displaystyle (epsilon ,lambda epsilon )} предугадывающим защищённым MAC, для любого ϵ>0{displaystyle epsilon >0}.

Пусть
XW{displaystyle X_{W}} – сессионный ключ, общий для Алисы и Боба, и удовлетворяющий
Hmin(XW|WE0)>max(kK q,kZ){displaystyle H_{min}(X_{W}|WE_{0})>

max(k_{K} q,k_{Z})}. Символ ⊗{displaystyle otimes }
представляет побитовое сложение по модулю 2.

Умножение ⋅{displaystyle cdot } следует понимать как умножение в соответствующем конечном поле: GF(2s){displaystyle GF(2^{s})} или
GF(2q){displaystyle GF(2^?)}.

Мы пишем [b]q{displaystyle [b]_?} для q наиболее значимых бит битовой строки b{displaystyle b}. Протокол AUTH показан ниже.

1 На пути к конфиденциальности ключа

Здесь мы приведём некие размышления на тему того, как преодолеть проблемы безопасности DW-MAC по отношению к долгосрочному ключу W{displaystyle W}.

Аналогично нашим обозначениям, TA{displaystyle T_{A}}
и TB{displaystyle T_{B}} отличаются от ярлыков, вычисленных Алисой и Бобом соответственно, мы записываем RA{displaystyle R_{A}} и RB{displaystyle R_{B}}, отличные от значений R{displaystyle R} Алисы и Боба, которые могут различаться, если Ева активно манипулирует передаваемыми сообщениями.

Первой попыткой предотвратить утечку через TA{displaystyle T_{A}} было одноразовое шифрование TA{displaystyle T_{A}}.

Ключ для шифрования добывается средствами сильного экстрактора Ext из XW{displaystyle X_{W}}, где Алиса выбрала ядро:
Alice(XW,μA)

Bob(XW,μB){displaystyle Alice(X_{W},mu _{A})

Bob(X_{W},mu _{B})}S∈R{0,1}k{displaystyle Sin _{R}{0,1}^{k}}Z:=Ext(XW;

S){displaystyle Z:=Ext(X_{W};S)}Q:=TA×Z{displaystyle Q:

=T_{A}times Z}Z:

=Ext(XW;S){displaystyle Z:=Ext(X_{W};S)}acceptif:Q=TB×Z{displaystyle acceptif:

Q=T_{B}times Z}В приведённом выше протоколе (а также ниже), мы понимаем, что TA{displaystyle T_{A}} и TB{displaystyle T_{B}} вычисляется как в DW-MAC.

Заметим, что как только Алиса выбирает ядро S{displaystyle S} и Hmin(XW|WE){displaystyle H_{min}(X_{W}|WE)} ограничено снизу, ZA{displaystyle Z_{A}} гарантированно близко к случайному независимому W{displaystyle W} (и E{displaystyle E}), и потому скрывает всю информацию, которая может просочиться через TA{displaystyle T_{A}} о W{displaystyle W}.

Однако, эта модификация делает безопасность схемы недействительной. Например, мы не можем исключить то, что модифицируя ядро S{displaystyle S} соответственно, Ева может привязать ZB=TB{displaystyle Z_{B}=T_{B}}, поэтому ей достаточно послать Q=0{displaystyle Q=0}, чтобы убедить Боба.

Произведение C⋅Z{displaystyle Ccdot Z} следует понимать в соответствующем бинарном поле.

Утечка из TA{displaystyle T_{A}} по прежнему предотвращается, поскольку ненулевой составной одноразовый ключ по-прежнему хороший одноразовый ключ.

Более того, для безопасности, мы можем интуитивно рассуждать следующим образом. Рассмотрим этап выполнения протокола после того, как было S{displaystyle S} сообщено.

Теперь мы даём Еве значение TA{displaystyle T_{A}} просто так; это делает её только сильнее.

Безопасностью лежащего в основе DW-MAC, мы знаем, что для Евы трудно угадать значение TB{displaystyle T_{B}}.

Теперь, предполагая, что существует два различных значения C{displaystyle C}, для каждого из которых Ева может предугадать соответствующее значение QB=TB⊗C⋅ZB{displaystyle Q_{B}=T_{B}otimes Ccdot Z_{B}}, следует, что Ева действительно может предугадать TB{displaystyle T_{B}}, получаем противоречие.

Однако, может быть не более одного значения выбора C{displaystyle C} Боба, для которого Ева достаточно хорошо может предугадать QB{displaystyle Q_{B}}.

Отметим, что приведённые выше интуитивные соображения включают перемотку; в обычном случае это нормально, но в квантовом случае не проходит (см. [11]). Таким образом, в неформальном доказательстве безопасности мы позволяем Еве поддерживать квантовое состояние.

Как следствие, в качестве протокола, Q{displaystyle Q} считается несколько иным образом.

Остаётся нерешённой проблема, что решение Боба, принять или отклонить, может также пропускать информацию о W{displaystyle W} когда μa=μB{displaystyle mu _{a}=mu _{B}} и Ева модифицирует одно или оба ядра R{displaystyle R} или S{displaystyle S}.

Отметим, что проблемы нет в случае μa≠μB{displaystyle mu _{a}neq mu _{B}}, потому что тогда Боб отклоняет с полной уверенностью.

Например, может случиться так, что изменение первого бита S{displaystyle S} меняет или не меняет Z{displaystyle Z}, зависит от XW{displaystyle X_{W}}.

Таким образом, изменяя первый бит S{displaystyle S} и получая решения Боба, Ева может узнать первый бит XW{displaystyle X_{W}}, что может дать ей один бит информации о W{displaystyle W}.

Решение о преодолении этой проблема напрашивается интуитивно: использовать MAC не только для аутентификации сообщения, но и двух ядер S{displaystyle S} и R{displaystyle R}.

Затем, как в случае μa≠μB{displaystyle mu _{a}neq mu _{B}}.

если Ева меняет одно из ядер, решение Боба – отклонить. Отметим, что данная модификация представляет некую рекурсию: ключ K{displaystyle K}, используемый для аутентификации ядра R{displaystyle R} получается из XW{displaystyle X_{W}} средствами ядра R{displaystyle R}. Однако, оказывается, что мы можем с этим справиться.

Protocol auth

Alice(XW,μA)Bob(XW,μB){displaystyle Alice(X_{W},mu _{A})Bob(X_{W},mu _{B})}
R∈R{0,1}d{displaystyle Rin _{R}{0,1}^{d}}
K:=laExt(XW;R)K:=laExt(XW;R){displaystyle K:=laExt(X_{W};R)K:=laExt(X_{W};R)}
S∈S{0,1}v{displaystyle Sin _{S}{0,1}^{v}}
Z:=Ext(XW;S)Z:=Ext(XW;S){displaystyle Z:=Ext(X_{W};S)Z:=Ext(X_{W};S)}
TA:=MACK(μA,R,S)TB:=MACK(μB,R,S){displaystyle T_{A}:=MAC_{K}(mu _{A},R,S)T_{B}:=MAC_{K}(mu _{B},R,S)}
U∈R{0,1}s,V∈R{0,1}q∖{0}q{displaystyle Uin _{R}{0,1}^{s},Vin _{R}{0,1}^?setminus {0}^?}
ifU,V=0:abort{displaystyle ifU,V=0:abort}
Q:=[U⋅TA]q⊗V⋅Z{displaystyle Q:=[Ucdot T_{A}]_?otimes Vcdot Z}
acceptif:Q=[U⋅TB]q⊗V⋅Z{displaystyle acceptif:Q=[Ucdot T_{B}]_?otimes Vcdot Z}
else:abort{displaystyle else:abort}

В полной версии статьи [6] мы показываем как проиллюстрировать строительные блоки
(из-за ограничений пространства мы включили только части, иллюстрирующие MAC в настоящей версии, в дополнении A). для получения схемы с разумными параметрами.

В этом процессе мы используем технику из [1], кроме того мы заменяем сильные экстракторы, которые являются частями предугадывающего экстрактора, что доказало безопасность от квантовой сторонней информации ([12]).
В зависимости от параметров конкретизации AUTH И количества бит μA{displaystyle mu _{A}},
может быть выгодно, или даже необходимо, аутенцифицировать хэш тройки (μa,R,S){displaystyle (mu _{a},R,S)}, вместо аутентификации самой тройки.

В этом случае, мы позволим Алисе выбрать малый источник для почти универсальной хэш-функции и применить MACK{displaystyle MAC_{K}} к этому источнику, и хэш тройки
(μa,R,S){displaystyle (mu _{a},R,S)} (по отношению к этому источнику).

Мы на самом деле воспользуемся предложенной модификацией для установки AUTH.
Перед тем, как перейти к доказательству безопасности AUTH, мы разрешим рекурсивную проблему, полученную из аутентификации источника R{displaystyle R}, использовавшегося для получения аутентификационного ключа K{displaystyle K}.

Доказательство секретности и безопасности

В этом разделе мы покажем, что протокол AUTH удовлетворяет свойствам, приведённым в Определении 5. Для начала отметим, что легко увидеть из описания протокола, что свойство корректности соблюдено, и мы не будем рассматривать это в дальнейшем.
На протяжении доказательств, пусть E0{displaystyle E_{0}} – квантовая сторонняя информация Евы до выполнения AUTH. Ei{displaystyle E_{i}}, где i∈{1,…,4}{displaystyle iin {1,…

,4}}, представляет квантовую сторону информации Евы после i-го раунда коммуникации, и следовательно включает связанные случайные величины до этого раунда. E{displaystyle E} представляет информацию на стороне Евы после выполнения AUTH, включая решение Боба (E4{displaystyle E_{4}} не включает это решение).

В дальнейшем, как в секции 3.1, мы пишем RA,RB{displaystyle R_{A},R_{B}} и т.д. для соответствующих значений R{displaystyle R}.

Лемма 2.

Рассматривая MAC как (ϵ,λ ϵ){displaystyle (epsilon ,lambda epsilon )}-предугадывающе-безопасный для любого ϵ{displaystyle epsilon }.

Пусть K,K′,MA,MB{displaystyle K,K’,M_{A},M_{B}} – произвольные случайные величины и E – квантовое состояние, и пусть упорядоченная пара K,K′∈({0,1}l)2t{displaystyle K,K’in ({0,1}^{l})

^{2t}} удовлетворяет предугадывающему свойству с параметром ϵ{displaystyle epsilon }, обусловленным MA,MB,E{displaystyle M_{A},M_{B},E} и событие MA≠MB{displaystyle M_{A}neq M_{B}}.

Тогда, Guess(MACK(MB)|MAKK′(MA)MAMBE,MA≠MB)<λ tϵ.{displaystyle Guess(MAC_{K}(M_{B})

|MAK_{K’}(M_{A})M_{A}M_{B}E,M_{A}neq M_{B})<lambda tepsilon .}
Доказательство. Мы ставим условия на MA=mA{displaystyle M_{A}=m_{A}} и MB=mB{displaystyle M_{B}=m_{B}} и предположим, что mA≠mB{displaystyle m_{A}neq m_{B}}.

Потому как (K,K′){displaystyle (K,K’)} может зависеть от
(MA,MB){displaystyle (M_{A},M_{B})}, обуславливаясь фиксированными значениями, последнее предполагает, что (K,K′){displaystyle (K,K’)} не обязательно ϵ{displaystyle epsilon }-предугадывающее.

Пусть
ϵma,mB{displaystyle epsilon _{m_{a},m_{B}}} будет максимальным на i∈[t]{displaystyle iin [t]} следующего выражения
ϵma,mB,i:=d(Ki 1…KT|k1′…Ki′E,MA=mA,MB=mB).{displaystyle epsilon _{m_{a},m_{B},i}:=d(K_{i 1}…K_{T}|k’_{1}…

K’_{i}E,M_{A}=m_{A},M_{B}=m_{B}).}Следовательно, из определения 6, (K,K′){displaystyle (K,K’)} есть
ϵma,mB{displaystyle epsilon _{m_{a},m_{B}}}-предыгадывающий обусловленный на E{displaystyle E} и сообщениях MA=mA,MB=mB{displaystyle M_{A}=m_{A},M_{B}=m_{B}}.

Заметим, что усреднение ϵma,mB,i{displaystyle epsilon _{m_{a},m_{B},i}} над mAmB{displaystyle m_{A}m_{B}} результируется в
ϵi=d(Ki 1…Kt|K1′…Ki′MAMBE,MA≠MB)≤ϵ.{displaystyle epsilon _{i}=d(K_{i 1}…K_{t}|K’_{1}…

K’_{i}M_{A}M_{B}E,M_{A}neq M_{B})leq epsilon .}Более того, отметим что обуславливанием фиксированных и отдельных значений MA,MB{displaystyle M_{A},M_{B}}, мы удовлетворяем требованиям MAC-предугадывающей безопасности для определения 8. Т.е. мы делаем вывод о том, что
Guess(MACK(MB)|MACK′(MA)

E,MA=mA,MB=mB)<λ ϵmA,mB.{displaystyle Guess(MAC_{K}(M_{B})

|MAC_{K’}(M_{A})E,M_{A}=m_{A},M_{B}=m_{B})<lambda epsilon _{m_{A},m_{B}}.}
Теперь следует, что
Guess(MACK(MB)|MACK′(MA)MAMBE,MA≠MB)={displaystyle Guess(MAC_{K}(M_{B})

|MAC_{K’}(M_{A})M_{A}M_{B}E,M_{A}neq M_{B})=}∑mA,mBPMAMB|MA≠MB(mA,mB)⋅Guess(MACK(MB)|MACK′(MA)

E,MA=mA,MB=mB){displaystyle sum _{m_{A},m_{B}}P_{M_{A}M_{B}|M_{A}neq M_{B}}(m_{A},m_{B})

cdot Guess(MAC_{K}(M_{B})|MAC_{K’}(M_{A})E,M_{A}=m_{A},M_{B}=m_{B})}<∑mA,mBPMAMB|MA≠MB(mA,mB)(λ maxi∈[t]ϵmA,mB,i){displaystyle <

sum _{m_{A},m_{B}}P_{M_{A}M_{B}|M_{A}neq M_{B}}(m_{A},m_{B})(lambda max _{iin [t]}epsilon _{m_{A},m_{B},i})}≤λ ∑mA,mBPMAMB|MA≠MB(mA,mB)∑i∈[t]ϵmA,mB,i{displaystyle leq lambda sum _{m_{A},m_{B}}P_{M_{A}M_{B}|M_{A}neq M_{B}}(m_{A},m_{B})sum _{iin [t]}epsilon _{m_{A},m_{B},i}}=λ ∑i∈[t]∑mA,mBPMAMB|MA≠MB(mA,mB)ϵmA,mB,i=λ ∑i∈[t]ϵi≤λ ∑i∈[t]ϵ=λ |tϵ.{displaystyle =lambda sum _{iin [t]}sum _{m_{A},m_{B}}P_{M_{A}M_{B}|M_{A}neq M_{B}}(m_{A},m_{B})

epsilon _{m_{A},m_{B},i}=lambda sum _{iin [t]}epsilon _{i}leq lambda sum _{iin [t]}epsilon =lambda |tepsilon .}Это завершает доказательство.

Литература

Наш подход

Наш подход к достижению защищённости от атак man-in-the-middle без ключа с высокой энтропией теперь просто проводит аутентификацию классической коммуникации с применением протокола AUTH Секции 4, используя
xω{displaystyle x_{omega }} как слабый сессионный ключ.

Наше свойство секретности гарантирует, что такая аутентификация не допускает утечки информации о пароле
ω{displaystyle omega }.

Подчёркиваем, что прошлые схемы аутентификации на основе слабых ключей будут (потенциально) пропускать информацию об
ω{displaystyle omega }.

Существует пара тонкостей, о которых следует позаботиться в нашем подходе. Если квантовая коммуникация содержит шум (как бывает в реалистичных сценариях), или если злоумышленник man-in-the-middle модифицирует некоторые кубиты (довольно небольшое количество, чтобы не обнаружить себя), то версии
xω{displaystyle x_{omega }} для U и S не идентичны.

Поэтому мы имеем нечёткий случай. Как обсуждалось в Секции 6, это не является проблемой, как только корректирующая ошибки информация отправляется от Боба к Алисе, т.е от U к S в условиях идентификации, и как только мы имеем нижние границы
xω{displaystyle x_{omega }} версий U и S (с точки зрения злоумышленника).

О первом требовании легко позаботиться, мы просто отправляем коррекцию ошибок в нужном направлении; от S к U. В попытке гарантировать, что обе версии
xω{displaystyle x_{omega }} имеют соответствующую min-энтропию (анализ Дамгарда и др. только гарантирует min-энтропию U), мы модифицируем схему следующим образом.

Вместо того, чтобы измерять BB84 кубиты в базисе
c(ω){displaystyle c(omega )},
S измеряет ихх в случайном базисе
θ{displaystyle theta }
и объявляет разницу
r=ω⊗θ{displaystyle r=omega otimes theta }.

Затем, U и S обновляют код c сдвигая каждое кодовое слово на r так, что по отношению к новому коду c’, S имеет измеренные BB84 кубиты в базисе
c′(ω){displaystyle c'(omega )}.

Этот трюк также был использован в
[16]
, но по другой причине, и не оказал существенного влияния на анализ схемы. Тем не менее, как мы покажем ниже, это заставляет нас согласиться с тем, что версия c(ω){displaystyle c(omega )} S имеет ограниченную снизу min-энтропию, и потому аутентификация классических сообщений гарантированно работает, что обеспечивает безопасность парольной идентификационной схемы.

Напомним, что защита от злоумышленного U или S требует, чтобы злоумышленная группировка могла исключить хотя бы одну возможность пароля
ω{displaystyle omega } (за одно выполнение атаки); действительно, это лучшее, на что мы можем надеяться, потому что злоумышленники всегда могут попытаться угадать
ω{displaystyle omega }.

Для парольной man-in-the-middle защиты мы требуем, чтобы злоумышленник мог исключить не более двух возможностей пароля. И снова это лучшее, на что мы можем надеяться, потому что в атаке man-in-the-middle атакующий может (но не обязан) индивидуально атаковать U и S, и в обеих атаках может попытаться угадать
ω{displaystyle omega }.

Такую безопасность мы достигаем с помощью нашей схемы.
Вначале наметим нашу схему ниже, а потом будем утверждать (неформально), почему она защищена. Отсюда, мы будем использовать заглавные буквы для случайных величин, которые описывают значения
x,θ,ω{displaystyle x,theta ,omega }
и т.д. в чистом исполнении протокола. это следует из анализа
Q−ID {displaystyle Q-ID^{ }} в [5]
(который до сих пор применяется для сдвига кодового слова, описанного выше)
и что существует
W′{displaystyle W’} (независимое от W) такое, что если
W=W′{displaystyle W=W’}, существует min-энтропия в
X{displaystyle X},ограниченная до
IW{displaystyle I_{W}}, с точки зрения Евы.

Для
X′{displaystyle X’} рассуждаем следующим образом.

Рассмотрим две возможности для W:
ω1{displaystyle omega _{1}} и
ω2{displaystyle omega _{2}}.

Фокусируемся на позициях, где
c(ω1)≠c(ω2){displaystyle c(omega _{1})neq c(omega _{2})} (которые будут теми же позициями, если c заменить на c’).

Теперь фиксируем
θ{displaystyle theta }; следующее будет выполняться для любого
θ{displaystyle theta } (выбранного пользователем).

Из соотношения неопределённостей [15] следует (приблизительно):
Hmin(X12′|Θ)≥d/2,{displaystyle H_{min}(X’_{12}|Theta )

X12′{displaystyle X'_{12}} - распределение 

X′{displaystyle X’} по позициям, где
c(ω1)≠c(ω2){displaystyle c(omega _{1})neq c(omega _{2})}, и следует помнить, что
d{displaystyle d} представляет собой кодовое расстояние c.

Из того, что X′{displaystyle X’} и
Θ{displaystyle Theta } независимы от
W{displaystyle W}, и в свою очередь
R{displaystyle R} определяется
Θ,W{displaystyle Theta ,W}, имеем, что

Обозначения

Докажем безопасность нашей схемы в присутствии квантового противника с частичной информацией и введем некоторые подходящие обозначения. Однако подчеркнём, что большинство заметок и доказательств можно почерпнуть из классической информационно-теоретической точки зрения.
ρ{displaystyle rho }X{displaystyle X}E{displaystyle E} =
∑{displaystyle sum }x{displaystyle x}P(x{displaystyle x})|x{displaystyle x}⟩{displaystyle rangle }⟨{displaystyle langle }x{displaystyle x}| ⊗{displaystyle otimes }ρ{displaystyle rho }E{displaystyle E}|X{displaystyle X}=x{displaystyle x}, где Px{displaystyle x} – возможное распределение, формы ортонормального базиса H{displaystyle {mathcal {H}}}x{displaystyle x} и ρ{displaystyle rho }E{displaystyle E}|X{displaystyle X}=x{displaystyle x}∈P(H{displaystyle in {mathcal {P}}({mathcal {H}}}E{displaystyle E}){displaystyle )}.

В этом случае X{displaystyle X} можно понимать как случайную величину, и система E{displaystyle E} в состоянии ρ{displaystyle rho }E{displaystyle E}|X{displaystyle X}=x{displaystyle x}, особенно если X{displaystyle X} принимает значение x{displaystyle x}.

Поэтому мы также говорим о случайной величине x{displaystyle x} и квантовой системе E{displaystyle E}.

Чтобы упростить обозначения, мы часто пишем ρ{displaystyle rho }E{displaystyle E}x{displaystyle x} вместо ρ{displaystyle rho }E{displaystyle E}|x{displaystyle x}=x{displaystyle x}.

Читатели, не знакомые с частью информации, могут смело принимать E{displaystyle E} как классическое, в этом случае ρ{displaystyle rho }E{displaystyle E}|x{displaystyle x}=x{displaystyle x} все являются диагональными с вероятностями условных распределений
PE{displaystyle E}|X{displaystyle X}(⋅{displaystyle cdot }|x{displaystyle x}) как диагональные элементы.

Расстояние между двумя состояниями ρ{displaystyle rho }x{displaystyle x}, σ{displaystyle sigma }x{displaystyle x}∈P(H{displaystyle in {mathcal {P}}({mathcal {H}}}x{displaystyle x}){displaystyle )} измеряется по длине пути 12{displaystyle {frac {1}{2}}}||ρ{displaystyle rho }x{displaystyle x} – σ{displaystyle sigma }x{displaystyle x}||1, где ||⋅||{displaystyle ||cdot ||}1 – норма L1.

В случае классических состояний, т.е. ρ{displaystyle rho }x{displaystyle x} и σ{displaystyle sigma }x{displaystyle x} соответствуют распределениям P{displaystyle P}x{displaystyle x} и Q{displaystyle Q}x{displaystyle x}, длина пути совпадает со статическим расстоянием 12∑{displaystyle {frac {1}{2}}sum }x{displaystyle x}|P{displaystyle P}X{displaystyle X}(x{displaystyle x}) – Q{displaystyle Q}X{displaystyle X}(x{displaystyle x})|.

В следующем приближении мы рассмотрим двудольную систему X{displaystyle X}E{displaystyle E} с классическим X{displaystyle X}. X{displaystyle X} называют случайной и независимой, если ρ{displaystyle rho }X{displaystyle X}E{displaystyle E} = ρ{displaystyle rho }U⊗{displaystyle otimes }ρ{displaystyle rho }E{displaystyle E}, где ρ{displaystyle rho }U – полностью смешанное состояние на H{displaystyle {mathcal {H}}}X{displaystyle X} (т.е.

U – классическое, с равномерным распределением). В случае классического E{displaystyle E} это эквивалентно
P{displaystyle P}X{displaystyle X}E{displaystyle E} = P{displaystyle P}U{displaystyle U}⋅{displaystyle cdot }P{displaystyle P}E{displaystyle E} (в том смысле, что P{displaystyle P}X{displaystyle X}E{displaystyle E}(x{displaystyle x},e{displaystyle e}) = P{displaystyle P}U{displaystyle U}(x{displaystyle x})⋅{displaystyle cdot }P{displaystyle P}E{displaystyle E}(e{displaystyle e})∀(x,e){displaystyle forall (x,e)}).

Следующее определение показыват, как далеко X{displaystyle X}E{displaystyle E} от идеальной ситуации.

Определение 1. (расстояние до формы)

Расстояние до формы X данного E определяется как d(X|E):=12||ρ{displaystyle d(X|E):

={frac {1}{2}}||rho }XE{displaystyle XE} – ρ{displaystyle rho }U{displaystyle U}⊗ρ{displaystyle otimes rho }U{displaystyle U}||{displaystyle ||}1.

Если E также классическое, d(X|E){displaystyle d(X|E)} упрощается до
d(X|E)=12∑x,e|PXE(x,e)−PU(x)PE(e)|=∑ePE(e)12∑x|PX|E(x|e)−PU(x)|.{displaystyle d(X|E)

={frac {1}{2}}sum _{x,e}|P_{XE}(x,e)-P_{U}(x)P_{E}(e)|=sum _{e}P_{E}(e){frac {1}{2}}sum _{x}|P_{X|E}(x|e)-P_{U}(x)|.}Нетрудно показать, что для трёхчастной системы XYE{displaystyle XYE} с классическими X{displaystyle X} и Y{displaystyle Y}d(X|YE)=∑y∈YPY(y)d(X|E,Y=y).{displaystyle d(X|YE)

Определение 3 (мин-энтропия).

Мин-энтропия X{displaystyle X} данного E{displaystyle E} определяется какHmin(X|E):=−log⁡Guess(X|E).{displaystyle H_{min}(X|E):

=-log Guess(X|E).}Это определение совпадает с определением, введённым Реннером [7], как показано в
[8]

в случае классического E, оно совпадает с классическим определением условной мин-энтропии ^[9].

=== Определение 4. === Функция Ext:{0,1}n×{0,1}d→{0,1}m{displaystyle Ext:

{0,1}^{n}times {0,1}^{d}to {0,1}^{m}} является (k,ϵ){displaystyle (k,epsilon )} – сильный экстрактор, если для любой двухчастной квантовой системы XE{displaystyle XE} с классическим X{displaystyle X} и Hmin(X|E)≥k,{displaystyle H_{min}(X|E)geq k,} и для равномерного и независимого источника Y{displaystyle Y} имеем
d(Ext(X,Y)|YE)≤ϵ.{displaystyle d(Ext(X,Y)|YE)leq epsilon .}Заметим, что мы находим термин “экстрактор квантовых противников” довольно громоздким; поэтому мы просто называем Ext (сильным) экстрактором, даже если он является более сильным, чем стандартный.

При необходимости, мы проводим различие между двумя понятиями, говоря, что экстрактор защищён или не защищен от дополнительной информации.
Хорошо известный пример сильного экстрактора (защищённого от квантов сторонней информации) – это двоично-универсальная хэш-функция h:{0,1}n×{0,1}d→{0,1}q.{displaystyle h:

{0,1}^{n}times {0,1}^{d}to {0,1}^?.}
Действительно, для любой XE{displaystyle XE} с классическим X{displaystyle X}, и для независимого источника Y{displaystyle Y}, равномерно распределённом на {0,1}d{displaystyle {0,1}^{d}} усиление приватности
[10]
гарантирует, что
d(h(X,Y)|YE)≤122q−Hmin(X|YE)=122qGuess(X|YE).{displaystyle d(h(X,Y)|YE)

Определение 5.

Пусть E0,E{displaystyle E_{0},E} обозначают соответствующий априори и апостериори кавтовые системы Евы, где последний включает решение Боба принять или отклонить. A(n,k,m,δ,ϵ){displaystyle A(n,k,m,delta ,epsilon )} – протокол аутентификации сообщений с конфиденциальностью долгосрочного ключа, должен удовлетворять следующим свойствам:

Корректность: если злоумышленник Ева не присутствует, то для любого сообщение μ∈{0,1}m{displaystyle mu in {0,1}^{m}} и μ′=μ{displaystyle mu ‘=mu }, и для любого (распределения) ключа Xw∈{0,1}n{displaystyle X_{w}in {0,1}^{n}}, Боб принимает с уверенностью.

Безопасность: Если Hmin(Xw|WE0>k{displaystyle H_{min}(X_{w}|WE_{0}>k}, то для любого μ,μ′∈{0,1}m,μ≠μ′{displaystyle mu ,mu ‘in {0,1}^{m},mu neq mu ‘} вероятность подтверждения почти δ{displaystyle delta }.

Конфиденциальность долгосрочного ключа:
если ρWE0=ρw⊗ρE0{displaystyle rho _{WE_{0}}=rho _{w}otimes rho _{E_{0}}} и Hmin(XW|WE0)>k,{displaystyle H_{min}(X_{W}|WE_{0})>k,} то
12||ρWE−ρW⊗ρE||1≤ϵ{displaystyle {frac {1}{2}}||rho _{WE}-rho _{W}otimes rho _{E}||_{1}leq epsilon }.

Определение 6.(эпсилон-предугадывание)

Пусть t,l{displaystyle t,l} – целые положительные.

Пусть A:=(A1,…,At),B:=(B1,…,Bt){displaystyle A:=(A_{1},…,A_{t}),B:=(B_{1},…,B_{t})} случайные величины в диапазоне ({0,1}l)t,{displaystyle ({0,1}^{l})^{t},}, и пусть ,math>E</math> – квантовая система.

Для любого i∈{0,…,t−1}{displaystyle iin {0,…

,t-1}} пусть ϵi{displaystyle epsilon _{i}} определяется как
ϵi:=D(Ai 1…At|B1…BiE).{displaystyle epsilon _{i}:=D(A_{i 1}…A_{t}|B_{1}…B_{i}E).}Упорядоченная пара (A,B) – ϵ−{displaystyle epsilon -}предугадывание, обусловленное E{displaystyle E} если ϵ≥maxiϵI.{displaystyle epsilon geq max_{i}epsilon _{I}.}

Определение 7.(предугадывающий экстрактор)

laExt:{0,1}n×{0,1}d→({0,1}l)t{displaystyle laExt:

{0,1}^{n}times {0,1}^{d}to ({0,1}^{l})^{t}} называют (k,ϵ){displaystyle (k,epsilon )}-предугадывающим экстрактором если для любой случайно величины X∈{0,1}n{displaystyle Xin {0,1}^{n}} и квантовой системы E{displaystyle E} c Hmin(X|E)≥k{displaystyle H_{min}(X|E)geq k} имеет место следующее.

Пусть S∈{0,1}d{displaystyle Sin {0,1}^{d}} – независимый и равномерно распределённый источник, и пусть S~∈{0,1}d{displaystyle {tilde {S}}in {0,1}^{d}} противоположно выбраны данные S и E, это может включать измерение E, в результате будет получено новое состояние E’.

Затем, упорядоченные пары (R,R~){displaystyle (R,{tilde {R}})}, где R=(R1,…,Rt):=laExt(X;

S){displaystyle R=(R_{1},…,R_{t}):=laExt(X;S)} и R~=(R~1,…,R~t):=laExt(X;S~)−ϵ{displaystyle {tilde {R}}=({tilde {R}}_{1},…

,{tilde {R}}_{t}):=laExt(X;{tilde {S}})-epsilon }-предугадывание обусловленное S,S~{displaystyle S,{tilde {S}}} и E′{displaystyle E’}.

Неформально, предугадывающий экстрактор имеет свойство, что даже если злоумышленник может модифицировать источник, получив первые >math>i</math> бит ключа, полученные с помощью модифицированного источника, оставшиеся блоки ключа, извлечённые корректным источником, по прежнему выглядят случайными.

Определение 8.(предугадывающая безопасность )

Семейство функций
{MACk:{0,1}m→{0,1}s}{displaystyle {MAC_{k}:

{0,1}^{m}to {0,1}^{s}}}индексируемые ключами k∈({0,1}l)t{displaystyle kin ({0,1}^{l})^{t}} являются предугадывающе-безопасными MAC если для любой пары фиксированных и отдельных сообщений μA,μB∈{0,1}m,μA≠μB{displaystyle mu _{A},mu _{B}in {0,1}^{m},mu _{A}neq mu _{B}}, и для любой упорядоченной пары случайных величин (K,K′)∈({0,1}l)2t{displaystyle (K,K’)

in ({0,1}^{l})^{2t}}, удовлетворяющей свойству с параметром ϵ{displaystyle epsilon }, определённым в системе E{displaystyle E},
Guess(MACK(μB)|MACK′(μA)

E)<δ{displaystyle Guess(MAC_{K}(mu _{B})|MAC_{K’}(mu _{A})E)<delta }.

Теперь мы готовы представить протокол аутентификации сообщений Додиса и Вичса – DW-MAC. Этот протокол немного модифицирован, мы предполагаем, что Алиса уже отправила Бобу сообщение μA{displaystyle mu _{A}}, а он получил его как сообщение μB{displaystyle mu _{B}} (возможно, μA≠μB){displaystyle mu _{A}neq mu _{B})}.

Модификация проведена для простоты, и потому, что нашей целью не является минимизация количества раундов. Функция laExt:{0,1}n×{0,1}d→({0,1}l)t{displaystyle laExt:

{0,1}^{n}times {0,1}^{d}to ({0,1}^{l})^{t}} есть
(k,ϵ){displaystyle (k,epsilon )}- предугадывающий экстрактор и MACk{0,1}m→{0,1}s{displaystyle MAC_{k}{0,1}^{m}to {0,1}^{s}} есть надёжный MAC.

DW-MAC
Alice(XW,μA)

Bob(XW,μB){displaystyle Alice(X_{W},mu _{A})

Bob(X_{W},mu _{B})}R∈R{0,1}d{displaystyle Rin _{R}{0,1}^{d}}K:=laExt(XW;

R)K:=laExt(XW;R){displaystyle K:=laExt(X_{W};R)K:=laExt(X_{W};R)}TA:=MACK(μA)TB:

=MACK(μB){displaystyle T_{A}:

=MAC_{K}(mu _{A})T_{B}:=MAC_{K}(mu _{B})}acceptif:TA=TB{displaystyle acceptif:

T_{A}=T_{B}}else:abort{displaystyle else:abort}Надёжность DW-MAC следует из определений основных блоков:

laExt обеспечивает, что версии ключа K Алисы и Боба удовлетворяют предугадывающему свойству, и в этом случае гарантируется, что MAC действует как надёжный MAC, даже когда ключ Алисы модифицирован.
Тем не менее, в нашем случае мы хотим дополнительно поддерживать конфиденциальность долгосрочного ключа W, который может произвольно зависеть от XW{displaystyle X_{W}}, DW-MAC не выглядит достаточно хорошим вариантом – пока Ева остается пассивной.

Действительно, если Ева не манипулирует связанным источником R{displaystyle R}, то из предполагаемой нижней границы Hmin(XW|WE),{displaystyle H_{min}(X_{W}|WE),} следует, что извлечённое K{displaystyle K} на стороне Боба близко к случайному и независимому W{displaystyle W} и E{displaystyle E}, и поэтому из T{displaystyle T} не происходит утечки информации о W{displaystyle W}.

Однако, если Ева манипулирует источником R{displaystyle R} (заменяя его значением по своему выбору), то больше не гарантируется отсутствие утечек информации о W.

Ещё одина, но более тонкая, потенциальная возможность для Евы добыть информацию о W{displaystyle W}, не меняя сообщение, т.е. оставляя μA=μB{displaystyle mu _{A}=mu _{B}}, но меняя источник R{displaystyle R} и пытаясь получить информацию о W{displaystyle W}, наблюдая, подтверждает Боб или нет.

Определение безопасности.

В масштабе этой статьи, протокол аутентификации понимается как классический протокол между двумя сторонами – Алисой и Бобом. Алиса вводит сообщение μ{displaystyle mu } и слабый сессионный ключ Xw{displaystyle X_{w}}, и Боб вводит сообщение μ′{displaystyle mu ‘} и тот же ключ Xw{displaystyle X_{w}}.

В конце протокола Боб объявляет булево решение – “принять” или “отклонить”. Слабый сессионный ключ Xw{displaystyle X_{w}} может зависеть произвольно от долгосрочного ключа X{displaystyle X}.

Применение: парольная идентификация в ограниченной квантовой модели хранения

Дамгардом и другими в [5] предложено две схемы парольной идентификации:
Q−ID{displaystyle Q-ID} и
Q−ID {displaystyle Q-ID^{ }}.

Первый по-настоящему имеет парольную основу, но не защищает от атаки man-in-the-middle, в то время как второй обеспечивает безопасность в таком случа, но не действительно парольный, потому что «Пользователь» U и «Сервер» S обязаны иметь секретный высоко-энтропийный ключ.

Мы набросаем, как наша аутентификационная схема приводит к к действительно-парольной схеме идентификации в ограниченной квантовой модели хранения, защищённой от атак man-in-the-middle.
ИдеяQ−ID{displaystyle Q-ID} и
Q−ID {displaystyle Q-ID^{ }} следующая.

U посылает n BB84 квантовых бит
Hθ|x⟩Hθ1|x1⟩⊗…⊗Hθn|xn⟩{displaystyle H^{theta }|xrangle H^{theta _{1}}|x_{1}rangle otimes …

S, который измеряет их в базисе
c(ω)∈{0,1}n,{displaystyle c(omega )

in {0,1}^{n},}
где
ω{displaystyle omega }
есть обычный пароль и c — подходящий код с большим кодовым расстоянием
d{displaystyle d}.

Затем, U объявляет базис
c(θ)∈{0,1}n,{displaystyle c(theta )

in {0,1}^{n},}, используемый для BB84 кубит. Это позволяет U и S вычислить строку
xω{displaystyle x_{omega }}, состоящую из всех позиций
x{displaystyle x} с
θi=c(ω)i{displaystyle theta _{i}=c(omega )_{i}}, т.

е где U и S использовали одинаковый базис. Затем, U необходимо убедить S в том, что он действительно знает (ту же самую) строку
xω{displaystyle x_{omega }}. Дамгард и др. показали способ сделать это, который гарантирует отсутствие утечки информации о
ω{displaystyle omega } для потенциального злоумышленника U или S.

Защита от злоумышленника U необходимо безоговорочно, в то время как защита от злоумышленника S осуществляется в ограниченной квантовой модели хранения (где S по предположению имеет ограниченное квантовое хранилище). В основе последнего доказательства — нижняя граница min-энтропии
xω{displaystyle x_{omega }} с точки зрения сервера-злоумышленника, что следует из неопределённого отношения
[15].
Чтобы защитить протокол от атак man-in-the-middle, можно защитить (классическую и квантовую) коммуникацию от подделки. В попытке обнаружить подмену передаваемых кубитов, U и S выбирают образец кубитов и убеждаются, что в нём не было подмены.

В попытке обнаружить подмену в классической коммуникации, Дамгард и др. предлагают использовать так назвываемый экстрактор MAC. Такой MAC проще, чем обычный информационно-теоретический MAC, и требует ключа с высокой энтропией, но также является экстрактором.

Способ, которым этот экстрактор MAC используется в
Q−ID {displaystyle Q-ID^{ }} позволяет использовать высоко-энтропийный ключ повторно.

Проблема

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

Конкретно, мы рассмотрим следующий сценарий. Алиса и Боб имеют долгосрочный ключ W. При необходимости Алиса и Боб могут извлечь слабый сессионный ключ Xw из вспомогательного источника случайных чисел с помощью W.

Свойствами такого источника гарантируется, что потенциальный злоумышленник Ева, не знающий W, имеет ограниченную информацию о слабом сессионном ключе Xw. Это формализуетс я требованием Hmin(Xw|W E) ≥ k для некоего параметра k, где E обозначает информацию на стороне Евы.

Примеры, в которых данный сценарий имеет место естественным образом, ограничены моделью хранения, где W определяет, какую часть огромной строчи читать, или частичной областью, где W определяет, в каком базисе измерять некое квантовое состояние.
Теперь стоит задача проверить подлинность сообщения μ от Алисы Бобу с помощью слабого сессионного ключа Xw, таким образом, чтобы (1)

Ева не могла исказить его, не будучи замеченной, и (2) Ева не узнала никакой информации о долгосрочном ключе W. Мы подчёркиваем, что свойство (2) жизненно необходимо Алисе и Бобу для того, чтобы в дальнейшем использовать ключ W. Заметим, что использовав аутентификацию слабым ключом, Алиса и Боб могут также заключить ключевое соглашение, просто стандартно случайным образом производя извлечение, где источник экстрактора связано подтверждённым образом.

Мы хотим подчеркнуть, что, по предположению, каждый новый Xw ключ сеанса для того же самого долгосрочного ключа W содержит новую случайность, обеспечиваемую вспомогательным источником. Следовательно, выше описанная задача не противоречит хорошо известной невозможности аутентификационного ключа без обновления.

Заметим также, что мы не указываем, как точно вспомогательный источник случайности создаёт Xw из W; вопреки этому мы хотим безопасности независимо от того, как Xw был получен, как только Xw содержит достаточно ми-энтропии (данной информацией злоумышленника и ключом W).

Раскрыт принцип работы теста, позволяющего определить достоверность сертификата о вакцинации

Глава Национального исследовательского центра эпидемиологии и микробиологии имени Гамалеи Александр Гинцбург рассказал о тесте, который позволяет выявить, действительно ли вакцинирован человек от COVID-19. 

В беседе с «Известиями» Гинцбург поделился информацией о разработанном исследовательским центром тесте на наличие антител в крови к мембранному белку аденовируса Ad26 ― именно он может точно определить, делал ли когда-нибудь человек вакцину от коронавируса.

Ad26 ― это одна из составляющих первого компонента вакцины «Спутник V», которая выполняет роль посредника генетического материала SARS-CoV-2 в клетки организма. Аденовирус кодирует информацию о структуре S-белка шипа вируса. По словам Гинцбурга, Ad26 крайне редко можно встретить в организме человека. 

«Это буквально десятые доли процента. Поэтому наличие антител к адено 26-му говорит, что люди вакцинированы. А вот если человек попадает в реанимацию и говорит, что провакцинирован, но у него при этом нет антител к оболочке адено 26-го, то, скорее всего, у него поддельный сертификат», — отметил руководитель НИЦЭМ им. Н. Ф. Гамалеи. 

Известно, что работа над тестом длится уже месяц, и его протестировали уже на 50-60 людях. 

Тест, определяющий достоверность сертификата о вакцинации, не будет выявлять вакцины «КовиВак» и «ЭпиВакКорона» из-за их малой распространенности. Кроме этого, главный научный сотрудник НИЦ эпидемиологии и микробиологии имени Гамалеи Анатолий Альтштейн отозвался об «ЭпиВакКороне» как о крайне малоэффективной альтернативе «Спутнику V». 

По словам Альтштейна, «ЭпиВакКорона» не вырабатывает иммунитет. Что касается «КовиВака», главный научный сотрудник не смог дать определенного ответа, поскольку вакцина сделана по всем стандартам, однако исследователи до сих пор не провели третью фазу испытаний, из-за чего у специалистов нет доказательств ее эффективности.

Альтштейн отмечает, что эти альтернативные вакцины не повлияют на ситуацию с поддельными сертификатами, так как препараты «КовиВак» и «ЭпиВакКорона» выпускаются в очень ограниченном количестве.

Схожая работа

Пусть n — битовый размер ключа (в нашем случае, ключа сессии) и k — его мин-энтропия (в битах). Додисом и Вичсом доказано, что неинтерактивная аутентификация невозможна, когда k ≤ n/2, даже в том случае, когда стороны имеют доступ к локальному источнику случайности, который мы будем предполагать.

Авторство первого протокола интерактивной аутентификации для произвольного слабого ключа принадлежит Реннеру и Вулфу. Требуется Θ{displaystyle Theta }(l) раундов взаимодействия для проверки подлинности сообщения длиной l –бит.

В случае
[1]
аутентификационный протокол для произвольного слабого ключа описан так, что требуется всего два раунда, что является оптимальным (с точки зрения количества раундов).

Чандран и другие
[2]
делают акцент на минимизации энтропийной потери и описывают протокол усиления конфиденциальности, оптимальной с точки зрения энтропийной потери (с точностью до констант).

Их конструкция требует линейного числа раундов (линейного в параметрах безопасности).
Случай, в котором Алиса и Боб имеют высоко-коррелированные, но возможно, неравные ключи – “нечёткий” случай – решён в [3] и улучшен Канукурти и Рейзином [4], но также покрывается [1] и [2].
Мы подчеркиваем, что ни одна из этих работ не может решить случай, когда слабый ключ получен из долгосрочного ключа и где сохранность долгосрочного ключа должна быть гарантирована.

Теорема 1. (безопасность)

Полагая, что
Hmin(XW|WE0)>kK q,{displaystyle H_{min}(X_{W}|WE_{0})>

k_{K} q,}
протокол AUTH удовлетворяет свойству безопасности в Определении 5 с
δ≤3⋅2−q 122q(λ tϵK).{displaystyle delta leq 3cdot 2^{-q} {frac {1}{2}}{sqrt {2^?(lambda tepsilon _{K}}}).}
По факту, мы докажем немного более сильное утверждение, которое будет использоваться в доказательстве приватности.

Пусть
MA:=(μA,RA,SA){displaystyle M_{A}:

=(mu _{A},R_{A},S_{A})}
и
MB:=(μB,RB,SB){displaystyle M_{B}:

=(mu _{B},R_{B},S_{B})}
Мы докажем, что в протоколе AUTH, если
Hmin(XW|WE0)>kK q,{displaystyle H_{min}(X_{W}|WE_{0})>

k_{K} q,}
и обусловленным на событии
MA≠MB{displaystyle M_{A}neq M_{B}},
Боб принимает решение отклонить, за исключением вероятности
δ′≤3⋅2−q 122q(λ tϵK/Pr[MA≠MB]).{displaystyle delta ‘leq 3cdot 2^{-q} {frac {1}{2}}{sqrt {2^?(lambda tepsilon _{K}/P_{r}[M_{A}neq M_{B}])}}.}Отметим, что это выражение сводится к простому выражению Теоремы 1 доказательства безопасности, потому что в этом случае
μA≠μB{displaystyle mu _{A}neq mu _{B}}
(по определению 5), которое предполагает, что
Pr[MA≠MB]=1{displaystyle P_{r}[M_{A}neq M_{B}]=1}.

Доказательство.
Рассмотрим этап протокола после второго раунда коммуникации. Полагаем, что
ZA{displaystyle Z_{A}} и TA{displaystyle T_{A}} назначены злоумышленником (это делает её только сильнее).

Пусть
KA:=laExt(XW;RA){displaystyle K_{A}:=laExt(X_{W};R_{A})} и
KB:=laExt(XW;RB).{displaystyle K_{B}:=laExt(X_{W};R_{B}).}Из цепного правила, и по использованию в дальнейшем
RB{displaystyle R_{B}} и
SA{displaystyle S_{A}}, отбираемых независимо, следует, что
Hmin(XW|ZAEE2)≥Hmin(XW|WE2)−q≥Hmin(XW|WE0)−q.{displaystyle H_{min}(X_{W}|Z_{A}EE_{2})

geq H_{min}(X_{W}|WE_{2})-qgeq H_{min}(X_{W}|WE_{0})-q.}По предполагаемым параметрам, т.е.
Hmin(XW|WE0)>kK q{displaystyle H_{min}(X_{W}|WE_{0})>

k_{K} q}
следует, что
(KB,KA)−ϵK{displaystyle (K_{B},K_{A})

-epsilon _{K}}-предугадывающий, определённый на
ZA,W,E2.{displaystyle Z_{A},W,E_{2}.}
Для того, чтобы применить лемму 2, мы дополнительно ставим условие
MA≠MB.{displaystyle M_{A}neq M_{B}.}
Лемма 1 гарантирует, что
ϵK{displaystyle epsilon _{K}} растёт не более чем на фактор
1/Pr[MA≠MB].{displaystyle 1/P_{r}[M_{A}neq M_{B}].} Теперь применим лемму 2 и получим:
Guess(TB|TAZAWE2,MA≠MB)≤λ tϵK/Pr]MA≠MB].{displaystyle Guess(T_{B}|T_{A}Z_{A}WE_{2},M_{A}neq M_{B})leq lambda tepsilon _{K}/P_{r}]M_{A}neq M_{B}].}Следующий шаг – рассмотреть
QV:=[UB⋅TB]q⊗VB⋅ZB{displaystyle Q_{V}:

=[U_{B}cdot T_{B}]_?otimes V_{B}cdot Z_{B}} как выход сильного экстрактора с источником
(UB,VB).{displaystyle (U_{B},V_{B}).} На самом деле, легко проверить, что
h:{0,1}s×{0,1}q×{0,1}q→{0,1}q,{displaystyle h:

{0,1}^{s}times {0,1}^?times {0,1}^?to {0,1}^?,} которая отображает
(t,z,u,v){displaystyle (t,z,u,v)}
на
[u⋅t]q⊗v⋅z,{displaystyle [ucdot t]_?otimes vcdot z,} является универсальной хэш-функцией со случайным источником
(u,v).{displaystyle (u,v).}
Таким образом, можно применить усиление приватности.

Одна тонкость в том, что в протоколе AUTH VB есть случайное из
{0,1}q{displaystyle {0,1}_?} 0q.{displaystyle {0}^?.}
Тем не менее, это влияет на общее состояние не более чем на
2−q{displaystyle 2^{-q}}, следовательно, по неравенству треугольника, расстояния до формы не более
2⋅2−q:{displaystyle 2cdot 2^{-q}:}d(QB|UBVBTAZAWE2,MA≠MB){displaystyle d(Q_{B}|U_{B}V_{B}T_{A}Z_{A}WE_{2},M_{A}neq M_{B})}≤122qGuess(TBZB|TAZAWE2,MA≠MB) 2⋅2−q{displaystyle leq {frac {1}{2}}{sqrt {2^?Guess(T_{B}Z_{B}|T_{A}Z_{A}WE_{2},M_{A}neq M_{B})

}} 2cdot 2^{-q}}≤122qGuess(TB|TAZAWE2,MA≠MB) 2⋅2−q{displaystyle leq {frac {1}{2}}{sqrt {2^?Guess(T_{B}|T_{A}Z_{A}WE_{2},M_{A}neq M_{B})

}} 2cdot 2^{-q}}≤122q(λ tϵK/Pr[MA≠MB]) 2⋅2−q.{displaystyle leq {frac {1}{2}}{sqrt {2^?(lambda tepsilon _{K}/P_{r}[M_{A}neq M_{B}])

}} 2cdot 2^{-q}.}Наконец, имеем
δ′=Guess(QB|QAWE3,MA≠MB){displaystyle delta ‘=Guess(Q_{B}|Q_{A}WE_{3},M_{A}neq M_{B})}≤Guess(QB|UBVBTAZAWE2,,MA≠MB){displaystyle leq Guess(Q_{B}|U_{B}V_{B}T_{A}Z_{A}WE_{2},,M_{A}neq M_{B})}≤2−q d(QB|UBVBTAZAWE2,,MA≠MB){displaystyle leq 2^{-q} d(Q_{B}|U_{B}V_{B}T_{A}Z_{A}WE_{2},,M_{A}neq M_{B})}≤3⋅2−q 122q(λ tϵK/Pr[MA≠MB]) 2⋅2−q.{displaystyle leq 3cdot 2^{-q} {frac {1}{2}}{sqrt {2^?(lambda tepsilon _{K}/P_{r}[M_{A}neq M_{B}])

Теорема 2. (секретность долгосрочного ключа)

Если предположить, что
Hmin(XW|WE0)>max(q kK,kZ),{displaystyle H_{min}(X_{W}|WE_{0})>

max(q k_{K},k_{Z}),}
протокол AUTH удовлетворяет свойству 5 приватности долгосрочного ключа
ϵ≤6⋅2−q 2q(λ tϵK) ϵK 2ϵZ{displaystyle epsilon leq 6cdot 2^{-q} {sqrt {2^?(lambda tepsilon _{K})

}} epsilon _{K} 2epsilon _{Z}}.
Доказательство.

Вначале докажем, что ни одно из сообщений, передаваемых протоколом, не пропускает информации о W. Затем мы покажем, что

Случай нечёткости.
До этого момента мы предполагали сценарий, в котором Алиса и Боб имеют общие идентичные копии сессионного ключа
XW{displaystyle X_{W}}.

Теперь мы рассмотрим «нечёткий» случай, в котором Алиса и Боб сожержат ключи, которые близки по значению в некотором смысле, но не обязательно идентичны. Такой тип сценария обычно возникает, когда Алиса и Боб получают свои сессионные ключи с присутствием шума.

Для простоты и с нашим приложением (Секция 6) в уме, мы используем расстояние Хэмминга для измерения близости ключей.
Рассмотрим следующий простой подход. Пусть ключ Боба называется
XW{displaystyle X_{W}}.

Перед выполнением процедуры аутентификации, Боб посылает некую корректирующую ошибки информацию (например, синдром
XW{displaystyle X_{W}}
по отношению к некоему коду, исправляющему ошибки)

Алисе, чтобы она могла скорректировать ошибки в своём ключе
XW′{displaystyle X’_{W}}, или наоборот.

К сожалению, Ева может модифицировать эту корректировочную информацию так, что Алиса не сможет восстановить правильно исходный ключ, и в этом случае работа нашей схемы не гарантируется. Тем не менее, как доказано в [1], этот подход работает в случае, если один из них использует переменное извлечение на основе предугадывающих экстракторов.

Для работы этого решения необходимо, чтобы оба ключа
XW{displaystyle X_{W}} и
XW′{displaystyle X’_{W}} имели достаточную min-энтропию, и чтобы Боб посылал корректировочную информацию Алисе (т.е информация должна быть послана в том же направлении, что и ядро экстрактора).

Тоже самое выполняется в том случае, когда Еве позволяется иметь квантовую стороннюю информацию.
Тонкость заключается в том, что корректирующая информация не должна пропускать информации о
W{displaystyle W}, чтобы соблюсти свойство секретности.

Подробно эта проблема раскрыта в
[13], и обобщена для квантового случая в [14]. Заметим, что для верхней границы min-энтропии потери в
XW{displaystyle X_{W}} и
XW′{displaystyle X’_{W}} из-за коррекции ошибок: по правилу цепи это самый большой размер в битах корректирующей ошибки информации.