Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [negligible]

Negligible means that something is so unimportant, that it isn't worth considering. For example, if a flaw in a cryptographic algorithm is considered to be negligible, it is insignificant to both the algorithm as well as it's security.

0
votes
0answers
24 views

What is $n_0$ in the definition of neglibible? [duplicate]

In a lecture, I have seen the following: Negligible Function: a function $f(n)$ is negligible if $\forall$ polyn. $p \;\exists n_0 \text{ s.t. }\forall n>n_o\; f(n) < 1/p(n)$ What is exactly ...
2
votes
1answer
47 views

Polynomial sum of negligible functions need not be negligible

Let $\{\epsilon_i\}_{n \in \mathbb{N}}$ be a sequence of negligible functions and $q(n)$ be a polynomial in $n$. Then $f(n) = \sum_{i = 1}^{q(n)} \epsilon_i(n)$ need not be a negligible function. ...
2
votes
2answers
110 views

Identifying negligible functions

I am having a hard time understanding and applying the formulas that are used to identify a function is negligible or not? One text defines it as; a function $f$ from the natural numbers to the non-...
11
votes
3answers
1k views

How small is negligible?

When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters. As a rule of thumb, given today (2018) computational power, what is ...
1
vote
1answer
140 views

Is power of non-negligible function non-negligible?

If I have a probability which is > negl(n), i.e., non-negligible, will be this probability raised to the power of n also non-negligible?
1
vote
1answer
61 views

Is inverse of a combination function negligible?

Can anyone help me in determining whether $1/{n\choose a}$ negligible function for sufficiently large value of $n$, say for example $n=p^2$ and $a=p$, for an integer $p$?
1
vote
1answer
216 views

How to prove a function is negligible?

My question essentially concerns how to prove if a function is negligible. As a matter of fact, though this question might seem very basic, it seems that most of the "proofs" of negligible concern ...
2
votes
1answer
250 views

Proving that a function is negligible

My question is about proving that a function is negligible if it is ran polynomial number of times. This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'...
5
votes
2answers
277 views

Property of negligible functions

Suppose that $\mu(n)$ is a negligible function, which means that for every $c>0$ there is some $N$ such that for all $n>N$ it holds that $\mu(n)\leq n^{-c}$. Now, imagine that some encryption ...
1
vote
2answers
560 views

Negligible function defined as product of polynomial and a negligible function

How do I prove that a function $f_2$, defined as the product of a negligible function $f_1$ and a polynomial $p$, is itself negligible? $$f_2(n)= p_1(n)f_1(n)$$ I see $f_2$ as negligible simply ...
1
vote
1answer
103 views

Is $\operatorname{negl}_1(n)-\operatorname{negl}_2(n) \leq \operatorname{negl}_3(n)$?

Is this statement $\operatorname{negl}_1(n)-\operatorname{negl}_2(n)\leq \operatorname{negl}_3(n)$ true for some negligible function $\operatorname{negl}_3$ and security parameter $n$?
0
votes
0answers
85 views

Can we come up with a counterexample?

Suppose $\epsilon$ : $N\in~ [0,1]$ is not a negligible function. Does it follow that for some polynomial $p$ (where $p(k)$ > 0 for all $k$) and some $k_0$, $\epsilon(k) > \frac{1}{p(k)}$ for all $k ...
5
votes
1answer
474 views

What does “overwhelming” mean in cryptography?

I found the term "overwhelming" when I study cryptography. According to the definition, we call $f$ overwhelming if $1-f$ is negligible. I already know the negligible function and its way to use but ...
4
votes
1answer
299 views

Differential Privacy: why $\delta$ negligible on the row numbers?

The definition of differential privacy says that an algorithm $M$ is $(\epsilon,\delta)$-differentially private if $$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$ where $D,D'$ ...
0
votes
1answer
130 views

Is $f(x) = -1.5$ a negligible function? [closed]

Is $f(x) = -1.5$ a negligible function? Since it satisfies the condition for a negligible function?
0
votes
2answers
193 views

What does “with all but negligible probability” mean?

I have met the sentence that something will happen "with all but negligible probability" in the paper "Homomorphic Signatures for Polynomial Functions". However, I cannot quite figure out what exactly ...
0
votes
1answer
94 views

Negative negligible functions

If f(n) is a negligible function, is -f(n) also negligible by definition? Since $$f(n) < \frac{1}{p(n)}$$ for all positive polynomials $p(n)$ and for some integer N such that $n > N$ Thus $$-f(...
1
vote
1answer
356 views

How do you prove that if f(x) and g(x) are negligible, then f(x)/g(x) is not?

I can use an example: the case where we have $x$ such that $f(x)=g(x)$. The quotient is $1$, a non-negligible function. However, we can't conclude that all functions $f(x)/g(x)$ are also negligible. ...
2
votes
1answer
1k views

Unpacking the definition of negligible & non-negligible

There are several threads on this topic including: How is an epsilon of 1/1000 non-negligible? How to calculate if probability is negligible or not (and others) but I do not fully understand the ...
0
votes
0answers
455 views

How to check if a function is significant or not?

f(n) = 1 / ( log n ) ^ 1/2 I know that this function is not negligible because it will never converge to zero even for large values of n. Now my question is, how ...
1
vote
0answers
67 views

How is an epsilon of 1/1000 non-negligible? [duplicate]

Lately I've been studying cryptography and in the current course I'm taking we're reviewing statistical tests and how they can be used to determine if a pseudo-random generator is secure or not. ...
1
vote
2answers
118 views

Negilible Function $\frac{1}{n!}$

Is $\frac{1}{n!}$ a negligible function where $n$ is a security parameter? Application: I have a vector of n>100 elements. I permute it and give it to an adversary. The adversary can break it if it ...
3
votes
2answers
2k views

How to calculate if probability is negligible or not

If i have probability $Q = 2C(A\times B)$ where $A$ and $B$ are unknown probabilities and $C$ is a non-negligible probability, what can i speculate about probability $Q$ and how can i calculate bounds ...
3
votes
1answer
624 views

Is $q(n)=1/n$ a negligible function?

By definition - $q(n)$ is a negligible function if for every positive integer $c>0$ there exist an integer $N_c$ such that for all $x>N_c$ : $q(n)<1/x^c$ So for the function $1/x$, if we ...
3
votes
1answer
362 views

When truncating an AES MAC value by “w” , how do I justify that “w” is still negligible?

I'm taking an online class on cryptography at corsera.org / Stanford, and the professor is explaining that it's OK to truncate an AES MAC to $w$ bits as long as $1/2^w$ is still negligible (say $w >...