Paper 2018/555

Limits on the Power of Garbling Techniques for Public-Key Encryption

Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, and Ameer Mohammed

Abstract

Understanding whether public-key encryption can be based on one-way functions is a fundamental open problem in cryptography. The seminal work of Impagliazzo and Rudich [STOC'89] shows that black-box constructions of public-key encryption from one-way functions are impossible. However, this impossibility result leaves open the possibility of using non-black-box techniques for achieving this goal. One of the most powerful classes of non-black-box techniques, which can be based on one-way functions (OWFs) alone, is Yao's garbled circuit technique [FOCS'86]. As for the non-black-box power of this technique, the recent work of Dottling and Garg [CRYPTO'17] shows that the use of garbling allows us to circumvent known black-box barriers in the context of identity-based encryption. We prove that garbling of circuits that have OWF (or even random oracle) gates in them are insufficient for obtaining public-key encryption. Additionally, we show that this model also captures (non-interactive) zero-knowledge proofs for relations with OWF gates. This indicates that currently known OWF-based non-black-box techniques are perhaps insufficient for realizing public-key encryption.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Public-key encryptionone-way functionblack-box constructionsnon-black-box separationsgarbling schemes
Contact author(s)
sanjamg @ berkeley edu
mdhajiabadi @ berkeley edu
mohammad @ virginia edu
am8zv @ virginia edu
History
2018-06-04: received
Short URL
https://ia.cr/2018/555
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/555,
      author = {Sanjam Garg and Mohammad Hajiabadi and Mohammad Mahmoody and Ameer Mohammed},
      title = {Limits on the Power of Garbling Techniques for Public-Key Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/555},
      year = {2018},
      url = {https://eprint.iacr.org/2018/555}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.