<p>The assumptions often used in crypto are a form of average-case complexity assumptions, such as hardness of factoring or discrete log in various groups. </p>

<p>Many lattice problems used for strong hardness guarantees for lattice based cryptography are qualitatively somewhat different than the factoring/discrete log based cryptographic assumptions.</p>

<p>The development of indistinguishability obfuscation has also introduced a number of novel average case hardness assumptions.</p>

<p>Often times average case complexity is used in the study of data structures for upper bounds (eg., of hash tables), but there are also some useful lower bounds. For example, the worst case $\Omega(n \log n)$ lower bound on sorting can be generalized to the average case, and to randomized algorithms as well (eg., see <a href="https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf" rel="nofollow">these lecture notes</a>)</p>

CC BY-SA 3.0
2015-12-15T05:16:52.110Z
2015-12-15T05:16:52.110Z
Joe Bebel
<p>The bounded post correspondence problem is complete for RNP (Randomized NP). Therefore, it is believed to be hard on average over uniformly random distributions of inputs.</p>

<p>Y. Gurevich, Average case completeness, J. Comp. Sys. Sci., 42 (3): 346–398, 1991</p>

CC BY-SA 3.0
2015-12-15T09:39:36.167Z
2015-12-15T09:39:36.167Z
Mohammad Al-Turkistany
<p>Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?</p>

<cc.complexity-theory><np-hardness><complexity-classes><time-complexity><average-case-complexity>
Popular average-case complexity assumptions
Minkov
# Popular average-case complexity assumptions

(Asked by: username_0 on 2015-12-15)

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, time-complexity, average-case-complexity


---

## 2 answers

### Answer by username_1 on 2015-12-15. Score: 4 | Accepted answer

The assumptions often used in crypto are a form of average-case complexity assumptions, such as hardness of factoring or discrete log in various groups.

Many lattice problems used for strong hardness guarantees for lattice based cryptography are qualitatively somewhat different than the factoring/discrete log based cryptographic assumptions.

The development of indistinguishability obfuscation has also introduced a number of novel average case hardness assumptions.

Often times average case complexity is used in the study of data structures for upper bounds (eg., of hash tables), but there are also some useful lower bounds. For example, the worst case $\Omega(n \log n)$ lower bound on sorting can be generalized to the average case, and to randomized algorithms as well (eg., see [these lecture notes](https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf))


---

### Answer by username_2 on 2015-12-15. Score: 3

The bounded post correspondence problem is complete for RNP (Randomized NP). Therefore, it is believed to be hard on average over uniformly random distributions of inputs.

Y. Gurevich, Average case completeness, J. Comp. Sys. Sci., 42 (3): 346–398, 1991


---

