Cryptology ePrint Archive: Report 2019/1488

Fine-Grained Cryptography Revisited

Shohei Egashira and Yuyu Wang and Keisuke Tanaka

Abstract: Fine-grained cryptographic primitives are secure against adversaries with bounded resources and can be computed by honest users with less resources than the adversaries. In this paper, we revisit the results by Degwekar, Vaikuntanathan, and Vasudevan in Crypto 2016 on fine-grained cryptography and show constructions of three key fundamental fine-grained cryptographic primitives: one-way permutations, hash proof systems (which in turn implies a public-key encryption scheme against chosen chiphertext attacks), and trapdoor one-way functions. All of our constructions are computable in $\mathsf{NC}^1$ and secure against (non-uniform) $\mathsf{NC}^1$ circuits under the widely believed worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus \mathsf{L/poly}$.

Category / Keywords: public-key cryptography / Fine-grained cryptography, NC1 circuit, One-way permutation, Hash proof system, Trapdoor one-way function

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 27 Dec 2019

Contact author: egashira s aa at m titech ac jp,wangyuyu@uestc edu cn,keisuke@is titech ac jp

Available format(s): PDF | BibTeX Citation

Version: 20191230:193404 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]