Paper 2014/598

Privacy-Free Garbled Circuits with Applications To Efficient Zero-Knowledge

Tore Kasper Frederiksen, Jesper Buus Nielsen, and Claudio Orlandi

Abstract

In the last few years garbled circuits (GC) have been elevated from being merely a compo- nent in Yao’s protocol for secure two-party computation, to a cryptographic primitive in its own right, following the growing number of applications that use GCs. Zero-Knowledge (ZK) protocols is one of these examples: In a recent paper Jawurek et al. [JKO13] showed that GCs can be used to construct efficient ZK proofs for unstructured languages. In this work we show that due to the property of this particular scenario (i.e., one of the parties knows all the secret input bits, and therefore all intermediate values in the computation), we can construct more efficient garbling schemes specifically tailored to this goal. As a highlight of our result, in one of our constructions only one ciphertext per gate needs to be communicated and XOR gates never require any cryptographic operations. In addition to making a step forward towards more practical ZK, we believe that our contribution is also interesting from a conceptual point of view: in the terminology of Bellare et al. [BHR12] our garbling schemes achieve au- thenticity, but no privacy nor obliviousness, therefore representing the first natural separation between those notions.

Note: Fixed typos and minor corrections.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2015
DOI
10.1007/978-3-662-46803-6_7
Keywords
zero-knowledgegarbled circuits
Contact author(s)
orlandi @ cs au dk
History
2015-05-11: last of 2 revisions
2014-08-05: received
See all versions
Short URL
https://ia.cr/2014/598
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/598,
      author = {Tore Kasper Frederiksen and Jesper Buus Nielsen and Claudio Orlandi},
      title = {Privacy-Free Garbled Circuits with Applications To Efficient Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2014/598},
      year = {2014},
      doi = {10.1007/978-3-662-46803-6_7},
      note = {\url{https://eprint.iacr.org/2014/598}},
      url = {https://eprint.iacr.org/2014/598}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.