# 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.

25 questions
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 ...
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. ...
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-...
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 ...
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?
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$?
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 ...
250 views

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 ...
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'$ ...
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?
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 ...
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(...
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. ...
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 ...
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 ...
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. ...
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 ...
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 ...
### 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 ...
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 >...