research-article

Leakage-resilient lossy trapdoor functions and public-key encryption

Authors:

Manuel CharlemagneAuthors Info & Claims

AsiaPKC '13: Proceedings of the first ACM workshop on Asia public-key cryptography

Pages 3 - 12

https://doi.org/10.1145/2484389.2484393

Published: 08 May 2013 Publication History

Abstract

Lossy Trapdoor Functions (LTFs) was introduced by Peikert and Waters in 2008. The importance of the LTFs was justified by their numerous cryptographic applications, like the construction of injective one-way trapdoor functions, CCA-secure public-key encryption, etc. However, little research on application of LTFs to key-leakage resilient public-key encryption was done. In this article we introduce a new variant of LTFs featuring leakage-resilience, namely lrLTFs and give a realization of lrLTFs with leakage rate 1/Θ(κ) (where κ is the security parameter) under the Decisional Diffie-Hellman (DDH) assumption. We further improve the leakage rate to 1-o(1) over a composite-order group in which the Decisional Composite Residuosity (DCR) assumption holds. We also introduce a new notion of key-leakage attacks, which we call weak key-leakage attacks, for bridging the adaptive and non-adaptive key-leakage attacks in the setting of public-key cryptosystem. In this model, the leakage adversary only gets a part of public key before accessing to a leakage oracle. We show that lrLTFs imply public-key encryption schemes secure against chosen-ciphertext weak key-leakage attacks in a black-box sense.

References

[1]

A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In O. Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 474--495. Springer, 2009.

Digital Library

[2]

M. Bellare, D. Hofheinz, and S. Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening. In Joux {17}, pages 1--35.

[3]

D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. Circular-secure encryption from decision diffie-hellman. In Wagner {30}, pages 108--125.

[4]

L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18(2):143--154, 1979.

[5]

R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In L. R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 45--64. Springer, 2002.

Digital Library

[6]

R. Cramer and V. Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput., 33(1):167--226, Jan. 2004.

Digital Library

[7]

I. Damgård and M. Jurik. A generalisation, a simplification and some applications of paillier's probabilistic public-key system. In K. Kim, editor, PKC 2001, volume 1992 of LNCS, pages 119--136. Springer, 2001.

Digital Library

[8]

Y. Dodis, K. Haralambiev, A. López-Alt, and D. Wichs. Cryptography against continuous memory attacks. In FOCS, pages 511--520. IEEE Computer Society, 2010.

Digital Library

[9]

Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97--139, 2008.

Digital Library

[10]

D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM J. Comput., 30(2):391--437, 2000.

Digital Library

[11]

C. Dwork, editor. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17--20, 2008. ACM, 2008.

[12]

S. Dziembowski and K. Pietrzak. Leakage-resilient cryptography. In FOCS 2008, pages 293--302. IEEE Computer Society, 2008.

Digital Library

[13]

C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Dwork {11}, pages 197--206.

[14]

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. One-time programs. In Wagner {30}, pages 39--56.

[15]

J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: Cold boot attacks on encryption keys. In P. C. van Oorschot, editor, USENIX Security Symposium, pages 45--60. USENIX Association, 2008.

Digital Library

[16]

B. Hemenway and R. Ostrovsky. Extended-ddh and lossy trapdoor functions. In M. Fischlin, J. Buchmann, and M. Manulis, editors, PKC 2012, volume 7293 of LNCS, pages 627--643. Springer, 2012.

Digital Library

[17]

A. Joux, editor. Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26--30, 2009. Proceedings, volume 5479 of LNCS. Springer, 2009.

[18]

E. Kiltz, P. Mohassel, and A. O'Neill. Adaptive trapdoor functions and chosen-ciphertext security. In H. Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 673--692. Springer, 2010.

Digital Library

[19]

P. C. Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In N. Koblitz, editor, CRYPTO 1996, volume 1109 of LNCS, pages 104--113. Springer, 1996.

Digital Library

[20]

P. C. Kocher, J. Jaffe, and B. Jun. Differential power analysis. In M. J. Wiener, editor, CRYPTO 1999, volume 1666 of LNCS, pages 388--397. Springer, 1999.

Digital Library

[21]

S. Liu, J. Weng, and Y. Zhao. Efficient public key cryptosystem resilient to key leakage chosen ciphertext attacks. In E. Dawson, editor, CT-RSA 2013, volume 7779 of LNCS, pages 84--100. Springer, 2013.

Digital Library

[22]

S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In M. Naor, editor, TCC 2004, volume 2951 of LNCS, pages 278--296. Springer, 2004.

[23]

M. Naor and G. Segev. Public-key cryptosystems resilient to key leakage. In S. Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 18--35. Springer, 2009.

Digital Library

[24]

M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In H. Ortiz, editor, STOC 1990, pages 427--437. ACM, 1990.

Digital Library

[25]

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In J. Stern, editor, EUROCRYPT 1999, volume 1592 of LNCS, pages 223--238. Springer, 1999.

Digital Library

[26]

C. Peikert and B. Waters. Lossy trapdoor functions and their applications. In Dwork {11}, pages 187--196.

[27]

C. Petit, F.-X. Standaert, O. Pereira, T. Malkin, and M. Yung. A block cipher based pseudo random number generator secure against side-channel key recovery. In M. Abe and V. D. Gligor, editors, ASIACCS 2008, pages 56--65. ACM, 2008.

Digital Library

[28]

K. Pietrzak. A leakage-resilient mode of operation. In Joux {17}, pages 462--482.

[29]

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, STOC 2005, pages 84--93. ACM, 2005.

Digital Library

[30]

D. Wagner, editor. Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17--21, 2008. Proceedings, volume 5157 of LNCS. Springer, 2008.

Digital Library

[31]

H. Wee. Dual projective hashing and its applications - lossy trapdoor functions and more. In D. Pointcheval and T. Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 246--262. Springer, 2012.

Digital Library

Cited By

Huang MYang BZhou YHu X(2021)Continual Leakage-Resilient Hedged Public-Key EncryptionThe Computer Journal10.1093/comjnl/bxaa20465:6(1574-1585)Online publication date: 13-Feb-2021
https://doi.org/10.1093/comjnl/bxaa204
Zhao YLiang KYang BChen L(2019)CCA Secure Public Key Encryption against After-the-Fact Leakage without NIZK ProofsSecurity and Communication Networks10.1155/2019/83572412019Online publication date: 31-Oct-2019
https://dl.acm.org/doi/10.1155/2019/8357241
Zhang MHuang JShen HXia ZDing Y(2018)Consecutive Leakage-Resilient and Updatable Lossy Trapdoor Functions and Application in Sensitive Big-Data EnvironmentsIEEE Access10.1109/ACCESS.2018.28641636(43936-43945)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2864163
Show More Cited By

Index Terms

Leakage-resilient lossy trapdoor functions and public-key encryption
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Post-challenge leakage in public-key encryption

When an adversary can measure the physical memory storing the decryption key, decryption functionality often comes in handy. Halevi and Lin (TCC'11) studied after-the-fact (or post-challenge) leakage in public-key encryption (PKE), in which an adversary ...
Lossy trapdoor functions from homomorphic reproducible encryption

Reproducible public-key encryption (reproducible PKE) provides an alternative way of encryption, which is called a reproduction algorithm, in addition to normally applying the encryption algorithm with the message and the randomness - applying the ...
Simpler CCA-Secure Public Key Encryption from Lossy Trapdoor Functions
Information Security and Cryptology
Abstract
In STOC’08, Peikert and Waters presented a black-box construction of CCA-secure public key encryption (PKE) scheme from lossy trapdoor functions (LTDFs) [20], and they mentioned in the paper that their construction is a hybrid of Naor-Yung [18] ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

AsiaPKC '13: Proceedings of the first ACM workshop on Asia public-key cryptography

May 2013

70 pages

ISBN:9781450320696

DOI:10.1145/2484389

General Chairs:
Kefei Chen
Shanghai Jiao Tong University, China
,
Qi Xie
Hangzhou Normal University, China
,
Weidong Qiu
Shanghai Jiao Tong University, China
,
Program Chairs:
Shouhuai Xu
University of Texas at San Antonio, USA
,
Yunlei Zhao
Fudan University, China

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASIA CCS '13

Sponsor:

SIGSAC

ASIA CCS '13: 8th ACM Symposium on Information, Computer and Communications Security

May 8, 2013

Hangzhou, China

Acceptance Rates

AsiaPKC '13 Paper Acceptance Rate 8 of 18 submissions, 44%;

Overall Acceptance Rate 36 of 103 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang MYang BZhou YHu X(2021)Continual Leakage-Resilient Hedged Public-Key EncryptionThe Computer Journal10.1093/comjnl/bxaa20465:6(1574-1585)Online publication date: 13-Feb-2021
https://doi.org/10.1093/comjnl/bxaa204
Zhao YLiang KYang BChen L(2019)CCA Secure Public Key Encryption against After-the-Fact Leakage without NIZK ProofsSecurity and Communication Networks10.1155/2019/83572412019Online publication date: 31-Oct-2019
https://dl.acm.org/doi/10.1155/2019/8357241
Zhang MHuang JShen HXia ZDing Y(2018)Consecutive Leakage-Resilient and Updatable Lossy Trapdoor Functions and Application in Sensitive Big-Data EnvironmentsIEEE Access10.1109/ACCESS.2018.28641636(43936-43945)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2864163
Li SMu YZhang MZhang F(2017)Continuous Leakage Resilient Lossy Trapdoor FunctionsInformation10.3390/info80200388:2(38)Online publication date: 23-Mar-2017
https://doi.org/10.3390/info8020038
Hu CLiu PZhou YGuo SWang YXu Q(2016)Public-key encryption for protecting data in cloud system with intelligent agents against side-channel attacksSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1782-620:12(4919-4932)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s00500-015-1782-6
Li SMu YZhang MZhang F(2016)Updatable Lossy Trapdoor Functions andźItsźApplication in Continuous LeakageProceedings of the 10th International Conference on Provable Security - Volume 1000510.1007/978-3-319-47422-9_18(309-319)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-47422-9_18
Koppula VPandey ORouselakis YWaters B(2016)Deterministic Public-Key Encryption Under Continual LeakageApplied Cryptography and Network Security10.1007/978-3-319-39555-5_17(304-323)Online publication date: 9-Jun-2016
https://doi.org/10.1007/978-3-319-39555-5_17
Hu CLiu PGuo S(2015)Public key encryption secure against related-key attacks and key-leakage attacks from extractable hash proofsJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-015-0329-07:5(681-692)Online publication date: 1-Dec-2015
https://doi.org/10.1007/s12652-015-0329-0

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten