Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ICALP 2014
DOI
10.1007/978-3-662-43948-7_54
Contact author(s)
wee @ di ens fr
History
2014-12-18: received
Short URL
https://ia.cr/2014/995
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/995,
      author = {Yuval Ishai and Hoeteck Wee},
      title = {Partial Garbling Schemes and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2014/995},
      year = {2014},
      doi = {10.1007/978-3-662-43948-7_54},
      note = {\url{https://eprint.iacr.org/2014/995}},
      url = {https://eprint.iacr.org/2014/995}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.