Пренебрежимо малая функция
Криптографический способ сказать «слишком мало, чтобы иметь значение»: в итоге меньше единицы, делённой на любой полином.
Функция μ(n) пренебрежимо мала, если для любого полинома p она в конце концов опускается ниже 1/p(n). 2−n пренебрежимо мала; 1/n100 — нет. На этом понятии держится вся асимптотическая школа, основанная Гольдвассер и Микали в начале 1980-х. Схема стойка, если преимущество любого эффективного противника пренебрежимо мало по параметру безопасности; так определяются и семантическая стойкость, и IND-CPA.
Слабое место в том, что «в конце концов» не говорит, когда именно. Схема может быть доказуемо стойкой и всё же взламываться при 128 битах. Поэтому практические доказательства для режимов шифрования теперь опираются на конкретную стойкость: преимущество записывают явной формулой от числа запросов и размера блока.