TY - GEN
T1 - Limits on the power of garbling techniques for public-key encryption
AU - Garg, Sanjam
AU - Hajiabadi, Mohammad
AU - Mahmoody, Mohammad
AU - Mohammed, Ameer
N1 - Funding Information:
S. Garg—Research supported in part from DARPA/ARL SAFEWARE Award W911NF15C0210, AFOSR Award FA9550-15-1-0274, AFOSR YIP Award, DARPA and SPAWAR under contract N66001-15-C-4065, a Hellman Award and research grants by the Okawa Foundation, Visa Inc., and Center for Long-Term Cybersecu-rity (CLTC, UC Berkeley). The views expressed are those of the author and do not reflect the official policy or position of the funding agencies. M. Hajiabadi—Supported by NSF award CCF-1350939 and AFOSR Award FA9550-15-1-0274. M. Mahmoody—Supported by NSF CAREER award CCF-1350939, a subcontract on AFOSR Award FA9550-15-1-0274, and University of Virginia’s SEAS Research Innovation Award. A. Mohammed—Supported by Kuwait University and the Kuwait Foundation for the Advancement of Science. Work done while at University of Virginia and visiting University of California, Berkeley.
Funding Information:
S. Garg—Research supported in part from DARPA/ARL SAFEWARE Award W911NF15C0210, AFOSR Award FA9550-15-1-0274,AFOSR YIP Award, DARPA and SPAWAR under contract N66001-15-C-4065, a Hellman Award and research grants by the Okawa Foundation, Visa Inc., and Center for Long-Term Cybersecurity (CLTC, UC Berkeley). The views expressed are those of the author and do not reflect the official policy or position of the funding agencies. M. Hajiabadi—Supported by NSF award CCF-1350939 and AFOSR Award FA9550-15-1-0274. M. Mahmoody—Supported by NSF CAREER award CCF-1350939, a subcontract on AFOSR Award FA9550-15-1-0274, and University of Virginia’s SEAS Research Innovation Award. A. Mohammed—Supported by Kuwait University and the Kuwait Foundation for the Advancement of Science. Work done while at University of Virginia and visiting University of California, Berkeley.
Publisher Copyright:
© International Association for Cryptologic Research 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85052371724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052371724&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-96878-0_12
DO - 10.1007/978-3-319-96878-0_12
M3 - Conference contribution
AN - SCOPUS:85052371724
SN - 9783319968773
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 335
EP - 364
BT - Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
A2 - Shacham, Hovav
A2 - Boldyreva, Alexandra
PB - Springer Verlag
T2 - 38th Annual International Cryptology Conference, CRYPTO 2018
Y2 - 19 August 2018 through 23 August 2018
ER -