Paper 2019/1488

Fine-Grained Cryptography Revisited

Shohei Egashira, 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}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2019
DOI
10.1007/978-3-030-34618-8_22
Keywords
Fine-grained cryptographyNC1 circuitOne-way permutationHash proof systemTrapdoor one-way function
Contact author(s)
egashira s aa @ m titech ac jp
wangyuyu @ uestc edu cn
keisuke @ is titech ac jp
History
2019-12-30: received
Short URL
https://ia.cr/2019/1488
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1488,
      author = {Shohei Egashira and Yuyu Wang and Keisuke Tanaka},
      title = {Fine-Grained Cryptography Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1488},
      year = {2019},
      doi = {10.1007/978-3-030-34618-8_22},
      note = {\url{https://eprint.iacr.org/2019/1488}},
      url = {https://eprint.iacr.org/2019/1488}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.