Cryptology ePrint Archive: Report 2013/229

Overcoming the Worst-Case Curse for Cryptographic Constructions

Shafi Goldwasser and Yael Kalai and Raluca Ada Popa and Vinod Vaikuntanathan and Nickolai Zeldovich

Abstract: 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:

-- 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 on the size of the Turing machine independent of its runtime. In addition, we construct a decryption algorithm that has input-specific runtime (at the price of revealing this runtime).

-- A reusable garbling scheme for arbitrary Turing machines (uniform or non-uniform), where the size of the garbling depends only on the size of the Turing machine.

Previously, it was known how to construct all these objects for depth d circuits, where all the parameters grow with d. Our constructions remove this depth d restriction, and moreover, have short key sizes and avoid the worst-case ``curse''.

Our results are obtained via a reduction from (a variant of) the witness encryption scheme, recently introduced by Garg et al. (STOC 2013) and the existence of SNARKs (Bitansky et al. STOC 2013). In particular, when instantiating our schemes using the witness encryption construction proposed by Garg et al., the security of our schemes relies on a strengthening of their assumption. We thus view our results as a ``proof of concept". We note that previously, no proposals for such schemes existed. We also point out the connection between this variant of witness encryption and the obfuscation of point filter functions as defined by Goldwasser and Kalai in 2005.

Category / Keywords: public-key cryptography / Functional encryption; Fully homomorphic encryption; Turing machines; Input-specific runtime

Publication Info: In submission.

Date: received 20 Apr 2013

Contact author: shafi at theory csail mit edu, yaelism@gmail com, raluca@csail mit edu, vinodv@cs toronto edu, nickolai@csail mit edu

Available formats: PDF | BibTeX Citation

Version: 20130429:100538 (All versions of this report)

Discussion forum: Show discussion | Start new discussion