Overcoming the worst-case curse for cryptographic constructions. IACR Cryptology ePrint Archive

Modeling efficient algorithms as polynomial size circuits rather than as polynomial time Turing machines has been the rule with few exceptions in cryptographic constructions which provide “secure versions ” of general efficient algorithms. A consequence of this modeling is that the resulting “secure version ” of an efficient algorithm A incurs the worst-case runtime of A over all inputs of a certain length, rather than the runtime of A on specific inputs. In this work, we address the challenge of achieving input-specific runtime rather than worst-case runtime for a wide variety of cryptographic tasks. In particular, we construct (under cryptographic assumptions detailed below): • An attribute-based encryption (ABE) scheme for any polynomial-time Turing and RAMs (including those with non-uniform advice), where the length of the function keys (or Turing machine keys) depends on the size of the Turing machine (and does not depend on its runtime). Moreover, the decryption algorithm has input-specific runtime (as opposed to worst-case). • A single-key functional encryption scheme (FE) for any polynomial-time Turing machines (uniform or non-uniform), where the length of the function keys (or Turing machine keys) depends only o