Cryptology ePrint Archive: Report 2014/995

Partial Garbling Schemes and Their Applications

Yuval Ishai and Hoeteck Wee

Abstract: Garbling schemes (aka randomized encodings of functions) represent a function F by a "simpler" randomized function F^ such that F^(x) reveals F(x) and no additional information about x. Garbling schemes have found applications in many areas of cryptography. Motivated by the goal of improving the efficiency of garbling schemes, we make the following contributions:

– We suggest a general new notion of partial garbling which unifies several previous notions from the literature, including standard garbling schemes, secret sharing schemes, and “conditional disclosure of secrets”. This notion considers garbling schemes in which part of the input is public, in the sense that it can be leaked by F^.

– We present constructions of partial garbling schemes for (boolean and arithmetic) formulas and branching programs which take advantage of the public input to gain better efficiency.

– We demonstrate the usefulness of the new notion by presenting applications to efficient attribute-based encryption, delegation, and secure computation. In each of these applications, we obtain either new schemes for larger classes of functions or efficiency improvements from quadratic to linear. In particular, we obtain the first ABE scheme in bilinear groups for arithmetic formulas, as well as more efficient delegation schemes for boolean and arithmetic branching programs.

Category / Keywords: foundations /

Original Publication (with major differences): ICALP 2014

Date: received 12 Dec 2014

Contact author: wee at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20141218:033826 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]