File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-319-76953-0_26
- Scopus: eid_2-s2.0-85045475276
- WOS: WOS:000445246500026
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Regularly lossy functions and applications
Title | Regularly lossy functions and applications |
---|---|
Authors | |
Issue Date | 2018 |
Publisher | Springer |
Citation | The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018. In Smart, N. (Eds), Topics in Cryptology - CT-RSA 2018 : The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, p. 491-511. Cham, Switzerland : Springer, 2018 How to Cite? |
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, regularly 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 regularly lossy functions (ABO-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 shorter key size and better computational efficiency than that of (ABO)-LTFs. We demonstrate the applications of (ABO)-RLFs in leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate (formula presented).ABO-RLFs immediately imply leakage-resilient message authentication code (MAC) with optimal leakage rate (formula presented), though in a weak sense.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). |
Persistent Identifier | http://hdl.handle.net/10722/312034 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
ISI Accession Number ID | |
Series/Report no. | Lecture Notes in Computer Science ; 10808 LNCS sublibrary. SL 4, Security and Cryptology |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, Yu | - |
dc.contributor.author | Qin, Baodong | - |
dc.contributor.author | Xue, Haiyang | - |
dc.date.accessioned | 2022-04-06T04:32:02Z | - |
dc.date.available | 2022-04-06T04:32:02Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018. In Smart, N. (Eds), Topics in Cryptology - CT-RSA 2018 : The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, p. 491-511. Cham, Switzerland : Springer, 2018 | - |
dc.identifier.isbn | 9783319769523 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/312034 | - |
dc.description.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, regularly 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 regularly lossy functions (ABO-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 shorter key size and better computational efficiency than that of (ABO)-LTFs. We demonstrate the applications of (ABO)-RLFs in leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate (formula presented).ABO-RLFs immediately imply leakage-resilient message authentication code (MAC) with optimal leakage rate (formula presented), though in a weak sense.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). | - |
dc.language | eng | - |
dc.publisher | Springer | - |
dc.relation.ispartof | Topics in Cryptology - CT-RSA 2018 : The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science ; 10808 | - |
dc.relation.ispartofseries | LNCS sublibrary. SL 4, Security and Cryptology | - |
dc.title | Regularly lossy functions and applications | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-319-76953-0_26 | - |
dc.identifier.scopus | eid_2-s2.0-85045475276 | - |
dc.identifier.spage | 491 | - |
dc.identifier.epage | 511 | - |
dc.identifier.eissn | 1611-3349 | - |
dc.identifier.isi | WOS:000445246500026 | - |
dc.publisher.place | Cham, Switzerland | - |