us with a way of generating hard instances. Fortunately, many average-case assumptions used in cryptography (including RSA, discrete log, and some lattice problems) can be based on worst-case assumptions via worst-case-to-average-case reductions.

Falsifiability

A desired characteristic of a computational hardness assumption is falsifiability, i.e. that if the assumption were false, then it would be possible to prove it. In particular, introduced a formal notion of cryptographic falsifiability.

1.Previous
3.Next