Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Composition of Random Systems: When Two Weak Make One Strong

  • Conference paper

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

Included in the following conference series:

  • 1613Accesses

Abstract

A new technique for proving theadaptive indistinguishability of two systems, each composed of some component systems, is presented, using only the fact that corresponding component systems arenon-adaptively indistinguishable. The main tool is the definition of a special monotone condition for a random systemF, relative to another random systemG, whose probability of occurring for a given distinguisherD is closely related to the distinguishing advantageε ofD forF andG, namely it is lower and upper bounded byε and\(\epsilon(1 + {\rm ln}\frac{1}{\epsilon})\), respectively.

A concrete instantiation of this result shows that the cascade of two random permutations (with the second one inverted) is indistinguishable from a uniform random permutation by adaptive distinguishers which may query the system from both sides, assuming the components’ security only against non-adaptive one-sided distinguishers.

As applications we provide some results in various fields as almostk-wise independent probability spaces, decorrelation theory and computational indistinguishability (i.e., pseudo-randomness).

Similar content being viewed by others

References

  1. Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Structures and Algorithms 3(3), 289–304 (1992)

    Article MATH MathSciNet  Google Scholar 

  2. Luby, M., Rackoff, C.: How to construct pseudo-random permutations from pseudo-random functions. SIAM J. on Computing 17(2), 373–386 (1988)

    Article MATH MathSciNet  Google Scholar 

  3. Maurer, U.: Indistinguishability of random systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110–132. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Maurer, U., Pietrzak, K.: The security of many-round Luby-Rackoff pseudorandom permutations. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 544–561. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  5. Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing 22(4), 838–356 (1993)

    Google Scholar 

  6. Renner, R.: The Statistical Distance of Independently Repeated Experiments (manuscript), available at:http://www.crypto.ethz.ch/~renner/publications.html

  7. Vaudenay, S.: Provable security for block ciphers by decorrelation. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 249–275. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  8. Vaudenay, S.: Adaptive-attack norm for decorrelation and super-pseudorandomness. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 49–61. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, ETH Zürich,  

    Ueli Maurer & Krzysztof Pietrzak

Authors
  1. Ueli Maurer

    You can also search for this author inPubMed Google Scholar

  2. Krzysztof Pietrzak

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel

    Moni Naor

Rights and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Maurer, U., Pietrzak, K. (2004). Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (eds) Theory of Cryptography. TCC 2004. Lecture Notes in Computer Science, vol 2951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24638-1_23

Download citation

Publish with us

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