Пренебрежительное значение имеет точное значение в криптографии. Он действительно определяется с точки зрения роста (точнее, упадка), например, по параметру безопасности.
Функция $\му$ пренебрежимо мал, если он растет медленнее (или убывает быстрее), чем 1 по любой полиномиальной функции. В частности, для любого многочлена $\mathsf{поли}$, для некоторой постоянной $N$, то для всех $x \geq N$, у нас есть:
$$|\му(х)| < \frac{1}{\mathsf{poly}(x)}.$$
Примером незначительной функции является $\mu(x) = 2^{-x}$. Это потому, что для любого многочлена мы всегда можем найти $N$ так что предыдущее неравенство выполняется, поскольку затухание экспоненциальное. Например, с помощью полинома $х^3$, неравенство не выполняется при $х = 2$ (поскольку $1/4 > 1/8$), $х = 3$ (поскольку $1/8 > 1/27$), и так далее. Но когда $x\geq 10$, то неравенство выполняется (например, $2^{-10} < 1/10^3$). Итак, в этом конкретном примере мы бы установили $N = 10$.
В конкретном примере DDH предположим, $ млн $ тратит полиномиальное количество времени на вычисление случайных троек DDH ($г^а,г^б,г^{аб}$). Тогда есть некоторая крошечная вероятность того, что задача DDH, которую ему дали, была рассчитана, поэтому он выиграет. немного больше, чем $1/2$ время (в половине случаев он выигрывает от равномерно случайного предположения). Однако в техническом смысле это преимущество ничтожно, т.к. $ млн $ является PPT, он может вычислять только полиномиальное количество кортежей, но число возможных кортежей растет экспоненциально с параметром безопасности. Поэтому преимущество выглядит примерно так $\textsf{поли}(\каппа)/2^{\каппа}$, что пренебрежимо мало в формальном смысле выше.
