ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average case?Take average case to mean average running time with uniform distribution on the inputs.
Are there any known NP problems which are conjectured to be exponentially hard on average?
cc.complexity theory;np;average case complexity
It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$.  The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.