Paper 2016/150

On Garbling Schemes with and without Privacy

Carsten Baum

Abstract

Garbling schemes allow to construct two-party function evaluation with security against cheating parties (SFE). To achieve this goal, one party (the Garbler) sends multiple encodings of a circuit (called Garbled Circuits) to the other party (the Evaluator) and opens a subset of these encodings, showing that they were generated honestly. For the remaining garbled circuits, the garbler sends encodings of the inputs. This allows the evaluator to compute the result of function, while the encoding ensures that no other information beyond the output is revealed. To achieve active security against a malicious adversary, the garbler in current protocols has to send O(s) circuits (where s is the statistical security parameter). In this work we show that, for a certain class of circuits, one can reduce this overhead. We consider circuits where sub-circuits depend only on one party's input. Intuitively, one can evaluate these sub-circuits using only one circuit and privacy-free garbling. This has applications to e.g. input validation in SFE and allows to construct more efficient SFE protocols in such cases. We additionally show how to integrate our solution with the SFE protocol of Frederiksen et al. (FJN14), thus reducing the overhead even further.

Note: Full version of the SCN paper.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.SCN 2016 (10th Conference on Security and Cryptography for Networks)
Keywords
Garbled CircuitsPrivacy-Free Garbling
Contact author(s)
cbaum @ cs au dk
History
2016-06-27: revised
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/150,
      author = {Carsten Baum},
      title = {On Garbling Schemes with and without Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2016/150},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/150}},
      url = {https://eprint.iacr.org/2016/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.