Paper 2018/021
Regular Lossy Functions and Their Applications in Leakage-Resilient Cryptography
Yu Chen, Baodong Qin, and Haiyang Xue
Abstract
In STOC 2008, Peikert and Waters introduced a powerful primitive called lossy trapdoor functions (LTFs). In a nutshell, LTFs are functions that behave in one of two modes. In the normal mode, functions are injective and invertible with a trapdoor. In the lossy mode, functions statistically lose information about their inputs. Moreover, the two modes are computationally indistinguishable. In this work, we put forward a relaxation of LTFs, namely, regular lossy functions (RLFs). Compared to LTFs, the functions in the normal mode are not required to be efficiently invertible or even unnecessary to be injective. Instead, they could also be lossy, but in a regular manner. We also put forward richer abstractions of RLFs, namely all-but-one regular lossy functions (ABO-RLFs) and one-time regular lossy filters (OT-RLFs). We show that (ABO)-RLFs admit efficient constructions from both a variety of number- theoretic assumptions and hash proof system (HPS) for subset membership problems satisfying natural algebraic properties. Thanks to the relaxations on functionality, the constructions enjoy much compact key size and better computational efficiency than that of (ABO)-LTFs. We demonstrate the utility of RLFs and their extensions in the leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate $1 - o(1)$. ABO-RLFs (or OT-RLFs) immediately imply leakage-resilient one-time message authentication code (MAC) with optimal leakage rate $1 - o(1)$. ABO-RLFs together with HPS give rise to leakage-resilient chosen-ciphertext (CCA) secure key encapsulation mechanisms (KEM) (this approach extends naturally to the identity-based setting). Combining the construction of ABO-RLFs from HPS, this gives the first leakage-resilient CCA-secure public-key encryption (PKE) with optimal leakage rate based solely on HPS, and thus goes beyond the barrier posed by Dodis et al. (Asiacrypt 2010). Our construction also applies to the identity-based setting, yielding LR-CCA secure IB-KEM with higher leakage rate than previous works.
Note: An extended abstract of this paper appears in CT-RSA 2018. This full version appears in Theoretical Computer Science.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. Theoretical Computer Sciences
- DOI
- 10.1016/j.tcs.2018.04.043
- Keywords
- leakage-resilient cryptography
- Contact author(s)
- yuchen prc @ gmail com
- History
- 2018-11-24: last of 3 revisions
- 2018-01-06: received
- See all versions
- Short URL
- https://ia.cr/2018/021
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/021, author = {Yu Chen and Baodong Qin and Haiyang Xue}, title = {Regular Lossy Functions and Their Applications in Leakage-Resilient Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/021}, year = {2018}, doi = {10.1016/j.tcs.2018.04.043}, url = {https://eprint.iacr.org/2018/021} }