Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Expanding Pseudorandom Functions; or: From Known-Plaintext Security to Chosen-Plaintext Security

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2442))

Included in the following conference series:

Abstract

Given any weak pseudorandom function, we present a general and efficient technique transforming such a function to a new weak pseudorandom function with an arbitrary length output. This implies, among other things, an encryption mode for block ciphers. The mode is as efficient as known (and widely used) encryption modes as CBC mode and counter (CTR) mode, but is provably secure against chosen-plaintext attack (CPA) already if the underlying symmetric cipher is secure against known-plaintext attack (KPA). We prove that CBC, CTR and Jutla’s integrity aware modes do not have this property. In particular, we prove that when using a KPA secure block cipher, then: CBC mode is KPA secure, but need not be CPA secure, Jutla’s modes need not be CPA secure, and CTR mode need not be even KPA secure. The analysis is done in a concrete security framework.

Basic Research in Computer Science, Centre of the Danish National Research Foundation.

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

  1. M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption. In38th Annual Symposium on Foundations of Computer Science [IEE97].

    Google Scholar 

  2. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits.SIAM Journal on Computing, 13(4):850–864, November 1984.

    Article MATH MathSciNet  Google Scholar 

  3. Anand Desai. New paradigms for constructing symmetric encryption schemes secure against chosen-ciphertext attack. In Mihir Bellare, editor,Advances in Cryptology — Crypto 2000, pages 394–412, Berlin, 2000. Springer-Verlag. Lecture Notes in Computer Science Volume 1880.

    Chapter  Google Scholar 

  4. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions.Journal of the ACM, 33(4):792–807, 1986.

    Article MathSciNet  Google Scholar 

  5. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. InProceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 25–32, Seattle, Washington, 15–17 May 1989.

    Google Scholar 

  6. Johan Høastad and Mats Näslund. Key feedback mode: a keystream generator with provable security. 2000.

    Google Scholar 

  7. IEEE.38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, 19–22 October 1997.

    Google Scholar 

  8. Charanjit S. Jutla. Encryption modes with almost free message integrity. InAdvances in Cryptology — EuroCrypt 2001, pages 529–544, Berlin, 2001. Springer-Verlag. Lecture Notes in Computer Science Volume 2045.

    Chapter  Google Scholar 

  9. Leonid A. Levin. One-way functions and pseudorandom generators. InProceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 363–365, Providence, Rhode Island, 6–8 May 1985.

    Google Scholar 

  10. Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions (extended abstract). In38th Annual Symposium on Foundations of Computer Science [IEE97], pages 458–467.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. BRICS Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000, Arhus C, Denmark

    Ivan Damgåard & Jesper Buus Nielsen

Authors
  1. Ivan Damgåard

    You can also search for this author inPubMed Google Scholar

  2. Jesper Buus Nielsen

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Columbia University, 450 Computer Science Building 1214 Amsterdam Ave., 10027, NewYork, N.Y., USA

    Moti Yung

Rights and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Damgåard, I., Nielsen, J.B. (2002). Expanding Pseudorandom Functions; or: From Known-Plaintext Security to Chosen-Plaintext Security. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_29

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp