The power and limits of preprocessing in cryptography