CryptoDB
Limits on the Power of Garbling Techniques for Public-Key Encryption
| Authors: | |
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2018 |
| 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 Döttling 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. |
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28791,
title={Limits on the Power of Garbling Techniques for Public-Key Encryption},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10993},
pages={335-364},
doi={10.1007/978-3-319-96878-0_12},
author={Sanjam Garg and Mohammad Hajiabadi and Mohammad Mahmoody and Ameer Mohammed},
year=2018
}