New method of key-dependent message security for asymmetric encryption
Authors: 
Qiqi Lai, Yupu Hu, Yuan Chen, Baocang Wang, Fenghe WangAuthors Info & Claims
Pages 2157 - 2170
Abstract
Key-dependent message KDM security should be considered in the design of security protocols, especially for complicated ones, where the messages related to the secret key might be encrypted. In this paper, we present a new method of constructing a KDM secure asymmetric encryption scheme with the notation of hybrid encryption in the standard model; although the notation of hybrid encryption was thought as no help to get rid of dependencies between messages and the secret key. Our result can also be seen as a partial instantiation for a previously well-known KDM secure asymmetric encryption scheme based on random oracle. As we know, this has never been carried out before. And our result indicates a new cryptographic application for the primitive of lossy trapdoor function. Throughout the paper, our main idea is to archive KDM security by making use of both leakage-resilience and auxiliary-input security properties. Copyright © 2014 John Wiley & Sons, Ltd.
References
[1]
Adão P, Bana G, Herzog J, Scedrov A. Soundness of formal encryption in the presence of key-cycles. Proceedings of the 10th European Symposium on Research in Computer Security, ESORICS '05, Milan, Italy, 2005; pp.374-369.
[2]
Applebaum B, Cash D, Peikert C, Sahai A. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. Proceedings of the 29th Annual International Cryptology Conference, CRYPTO '09, Santa Barbara, California, USA, 2009; pp.595-618.
[3]
Backes M, Dürmuth M, Unruh D. OAEP is secure under key-dependent messages. Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT '08, Melbourne, Australia, 2008; pp.506-523.
[4]
Boneh D, Halevi S, Hamburg M, Ostrovsky R. Circular-secure encryption from decision Diffie-Hellman. Proceedings of the 28th Annual International Cryptology Conference, CRYPTO '08, Santa Barbara, California, USA, 2008; pp.108-125.
[5]
Backes M, Pfitzmann B, Scedrov A. Key-dependent message security under active attacks-BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. Journal of Computer Security 2008; Volume 16 Issue 5: pp.C497-C530.
[6]
Black J, Rogaway P, Shrimpton T. Encryption-scheme security in the presence of key-dependent messages. Proceedings of the 9th Annual International Workshop, SAC '02, Madrid, Spain, 2002; pp.62-75.
[7]
Camenisch J, Lysyanskaya A. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. Proceedings of the 20th International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT '01, Innsbruck, Austria, 2001; pp.93-118.
[8]
Halevi S, Krawczyk H. Security under key-dependent inputs. Proceedings of the Proceedings of the 14th ACM conference on Computer and Communications Security, CCS '07, Alexandria, Virginia, USA, 2008; pp.466-475.
[9]
Misra S, Denko M, Mouftah H. Security challenges in emerging and next-generation wireless communication networks. Security and Communication Networks 2011; Volume 4 Issue 9: pp.979-980.
[10]
Misra S, Goswami S, Pathak GP, Shah N, Woungang I. Geographic server distribution model for key revocation. Proceedings of Telecommunication Systems, 2010 Issue 44; pp.281-295.
[11]
Narula P, Dhurandher SK, Misra S, Woungang I. Security in mobile ad-hoc networks using soft encryption and trust-based multi-path routing. Computer Communications 2008; Volume 31 Issue 4: pp.760-769.
[12]
Obaidat MS, Woungang I, Dhurandher SK, Koo V. A cryptography-based protocol against packet dropping and message tampering attacks on mobile ad hoc networks. Security and Communication Networks Volume 7 Issue 2: pp.376-384.
[13]
Alperin-Sheriff J, Peikert C. Circular and KDM security for identity-based encryption. Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography, PKC '12, Darmstadt, Germany, 2012; pp.334-352.
[14]
Applebaum B. Key-dependent message security: generic amplification and completeness theorems. Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '11, Tallinn, Estonia, 2011; pp.527-546.
[15]
Brakerski Z, Goldwasser S. Circular and leakage resilient public-key encryption under subgroup indistinguishability. Proceedings of the 30th Annual International Cryptology Conference, CRYPTO '10, Santa Barbara, California, USA, 2010; pp.1-20.
[16]
Brakerski Z, Goldwasser S, Kalai YT. Black-box circular-secure encryption beyond affine functions. Proceedings of the 8th Theory of Cryptography Conference, TCC '11, Providence, Rhode Island, USA, 2011; pp.201-218.
[17]
Barak B, Haitner I, Hofheinz D, Ishai Y. Bounded key-dependent message security. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '10, Monaco and Nice, French Riviera, 2010; pp.423-444.
[18]
Galindo D, Herranz J, Villar JL. Identity-based encryption with master key dependent message security and leakage-resilience. Proceedings of the Proceedings of the 17th European Symposium on Research in Computer Security, ESORICS '12, Pisa, Italy, 2012; pp.627-642.
[19]
Hofheinz D. Circular chosen-ciphertext security with compact ciphertexts. Proceedings of the Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '13, Athens, Greece, 2013; pp.520-536.
[20]
Malkin T, Teranishi I, Yung M. Efficient circuit-size independent public key encryption with KDM security. Proceedings of the Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '11, Tallinn, Estonia, 2011; pp.507-526.
[21]
Goldwasser S, Micali S. Probabilistic encryption. Journal of Computer and System Sciences 1984; Volume 28 Issue 2: pp.270-299.
[22]
Camenisch J, Chandran N, Shoup V. A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '09, Cologne, Germany, 2009; pp.351-368.
[23]
Haitner I, Holenstein T. On the impossibility of key dependent encryption. Proceedings of the Proceedings of the 6th Theory of Cryptography Conference, TCC '09, San Francisco, California, USA, 2009; pp.202-219.
[24]
Hofheinz D, Unruh D. Towards key-dependent message security in the standard model. Proceedings of the Proceedings of the 27nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '08, Istanbul, Turkey, 2008; pp.108-126.
[25]
Lu X, Li B, Mei Q, Xu H. Key-dependent message security for division function discouraging anonymous credential sharing. Proceedings of the Proceedings of the 5th International Conference of Provable Security, ProvSec '11, Xi'an, China, 2011; pp.297-308.
[26]
Bellare M, Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS '93, Fairfax, Virginia, USA, 1993; pp.62-73.
[27]
Regev O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37st Annual ACM Symposium on Theory of Computing, STOC '05, Baltimore, Maryland, USA, 2005; pp.84-93.
[28]
Akavia A, Goldwasser S, Vaikuntanathan V. Simultaneous hardcore bits and cryptography against memory attacks. Proceedings of the 6th Theory of Cryptography Conference, TCC '10, Zurich, Switzerland, 2010; pp.474-495.
[29]
Peikert C, Waters B. Lossy trapdoor functions and their applications. Proceedings of the 40st Annual ACM Symposium on Theory of Computing, STOC '08, Victoria, British Columbia, Canada, 2008; pp.187-196.
[30]
Dodis Y, Kalai YT, Lovett S. On cryptography with auxiliary input. Proceedings of the Proceedings of the 41st Annual ACM symposium on Theory of Computing, STOC '09, Bethesda, Maryland, USA, 2009; pp.621-630.
[31]
Dodis Y, Goldwasser S, Kalai Y, Peikert C, Vaikuntanathan V. Public-key encryption schemes with auxiliary inputs. Proceedings of the 7th Theory of Cryptography Conference, TCC '10, Zurich, Switzerland, 2010; pp.361-381.
[32]
Brakerski Z, Langlois A, Peikert C, Regev O, Stehlá D. Classical hardness of learning with errors. Proceedings of the 45th Annual ACM symposium on Symposium on Theory of Computing, STOC '13, Palo Alto, California, USA, 2013; pp.575-584.
[33]
Peikert C. Public-key cryptosystems from the worst-case shortest vector problem. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC '09, Bethesda, Maryland, USA, 2009; pp.333-342.
[34]
Goldwasser S, Kalai YT, Peikert C, Vaikuntanathan V. Robustness of the learning with errors assumption. Proceedings of the Proceedings of the Innovations in Computer Science, ICS '10, Beijing, China, 2010; pp.230-240.
[35]
Ajtai M, Kumar R, Sivakumar D. An overview of the sieve algorithm for the shortest lattice vector problem. Proceedings of the International Conference of Cryptography and Lattices, CaLC '01, Providence, Rhode Island, USA, 2001; pp.1-3.
[36]
Impagliazzo R, Zuckerman D. How to recycle random bits. Proceedings of the Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS '89, Research Triangle Park, North Carolina, USA, 1989; pp.248-253.
[37]
Micciancio D, Regev O. Lattice-based cryptography. In Post-Quantum Cryptography, Bernstein DJ, Buchmann J, Dahmen E eds. Springer: Berlin, Germany, 2009; pp.147-191.
Index Terms
- New method of key-dependent message security for asymmetric encryption
Index terms have been assigned to the content through auto-classification.
Recommendations
Key-Dependent Message Security: Generic Amplification and Completeness
Key-dependent message (KDM) secure encryption schemes provide secrecy even when the attacker sees encryptions of messages related to the secret-key sk. Namely, the scheme should remain secure even when messages of the form f (sk) are encrypted, where ...
Leakage-resilient lossy trapdoor functions and public-key encryption
AsiaPKC '13: Proceedings of the first ACM workshop on Asia public-key cryptographyLossy 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 ...
Key-dependent message security: generic amplification and completeness
EUROCRYPT'11: Proceedings of the 30th Annual international conference on Theory and applications of cryptographic techniques: advances in cryptologyKey-dependent message (KDM) secure encryption schemes provide secrecy even when the attacker sees encryptions of messages related to the secret-key sk. Namely, the scheme should remain secure even when messages of the form f(sk) are encrypted, where f ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 10 September 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in