Статистически близко - Statistically close

В расстояние вариации двух раздач ${displaystyle X}$ и ${displaystyle Y}$ над конечной областью ${displaystyle D}$, (часто называемый статистическая разница^[1]или же статистическое расстояние^[2] в криптографии) определяется как

${displaystyle Delta (X,Y)={frac {1}{2}}sum _{alpha in D}|Pr[X=alpha ]-Pr[Y=alpha ]|}$.

Мы говорим, что два вероятностные ансамбли ${displaystyle {X_{k}}_{kin mathbb {N} }}$ и ${displaystyle {Y_{k}}_{kin mathbb {N} }}$ статистически близки, если ${displaystyle Delta (X_{k},Y_{k})}$ это незначительная функция в ${displaystyle k}$.

Рекомендации

1. Гольдрайх, Одед (2001). Основы криптографии: основные инструменты (1-е изд.). Берлин: Издательство Кембриджского университета. п. 106. ISBN  0-521-79172-3.
2. Рейзин, Лев. (Конспект лекций) Экстракторы и лемма об оставшихся хэшах

Смотрите также

• Доказательство с нулевым разглашением
• Экстрактор случайности