Abstract
Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example, one encrypts using a shared key K the value K. Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the publickey and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model. By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under “formal” models of security can, in time, be safely realized by generically instantiating their primitives.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Abadi and A. Gordon. A calculus for cryptographic protocols: The spi calculus. Information and Computation, 148(1):1–70, January 1999. An extended version appeared as Digital Equipment Corporation Systems Research Center report No. 149, January 1998.
M. Abadi and P. Rogaway. Reconciling two views of cryptography: The computational soundness of formal encryption. In IFIP International Conference on Theoretical Computer Science, August 2000.
M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption: analysis of the DES modes of operation. In Proceedings of 38th Annual Symposium on Foundations of Computer Science (FOCS 97), 1997.
M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among notions of security for public-key encryption schemes. In H. Krawczyk, editor, Advances in Cryptology-CRYPTO’ 98, volume 1462 of Lecture Notes in Computer Science, pages 232–249. Springer-Verlag, 1998.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62–73, 1993.
M. Burrows, M. Abadi, and R. Needham. A logic of authentication. Proceedings of the Royal Society of London A, 426:233–271, 1989. A preliminary version appeared as Digital Equipment Corporation Systems Research Center report No. 39, February 1989.
J. Camenisch and A. Lysyanskaya. “Efficient non-transferable anonymous multishow credential system with optional anonymity revocation”. In Advances in Cryptology-EUROCRYPT’ 01, Lecture Notes in Computer Science. Springer-Verlag, 2001.
D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography. To appear in SIAM J. on Computing. Earlier version in STOC 91, 1998.
D. Dolev and A. Yao. On the security of public key protocols. IEEE Transactions on Information Theory, IT-29(12):198–208, March 1983.
M. Fischlin. “Pseudorandom function tribe ensembles based on one-way permutations: Improvements and applications”. In Advances in Cryptology-EUROCRYPT’ 99, Lecture Notes in Computer Science. Springer-Verlag, 1999.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28:270–299, April 1984.
J. Kilian and P. Rogaway. How to protect DES against exhaustive key search. Journal of Cryptology, 14(1):17–35, 2001. Earlier version in CRYPTO’ 96.
P. Lincoln, J. Mitchell, M. Mitchell, and A. Scedrov. A probabilistic poly-time framework for protocol analysis. In Proceedings of the Fifth ACM Conference on Computer and Communications Security, pages 112–121, 1998.
S. Micali. Personal communication, circa 1985.
L. Paulson. The inductive approach to verifying cryptographic protocols. Journal of Computer Security, 6(1–2):85–128, 1998.
B. Pfitzmann, M. Schunter, and M. Waidner. Cryptographic security of reactive systems (extended abstract). Electronic Notes in Theoretical Computer Science, 32, April 2000.
B. Pfitzmann and M. Waidner. “Composition and integrity preservation of secure reactive systems”. IBM Research Report RZ 3234, #93280, June 2000.
C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In Advances in Cryptology-CRYPTO’ 94, Lecture Notes in Computer Science. Springer-Verlag, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Black, J., Rogaway, P., Shrimpton, T. (2003). Encryption-Scheme Security in the Presence of Key-Dependent Messages. In: Nyberg, K., Heys, H. (eds) Selected Areas in Cryptography. SAC 2002. Lecture Notes in Computer Science, vol 2595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36492-7_6
Download citation
DOI: https://doi.org/10.1007/3-540-36492-7_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00622-0
Online ISBN: 978-3-540-36492-4
eBook Packages: Springer Book Archive