---
OA_type: closed access
_id: '3208'
abstract:
- lang: eng
  text: "A new technique for proving the adaptive indistinguishability of two systems,
    each composed of some component systems, is presented, using only the fact that
    corresponding component systems are non-adaptively indistinguishable. The main
    tool is the definition of a special monotone condition for a random system F,
    relative to another random system G, whose probability of occurring for a given
    distinguisher D is closely related to the distinguishing advantage ε of D for
    F and G, namely it is lower and upper bounded by ε and (1+ln1), respectively.\r\nA
    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.\r\nAs
    applications we provide some results in various fields as almost k-wise independent
    probability spaces, decorrelation theory and computational indistinguishability
    (i.e., pseudo-randomness)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ueli
  full_name: Maurer, Ueli
  last_name: Maurer
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Maurer U, Pietrzak KZ. Composition of random systems: When two weak make one
    strong. In: <i>First Theory of Cryptography Conference, 2004</i>. Vol 2951. Springer
    Nature; 2004:410-427. doi:<a href="https://doi.org/10.1007/978-3-540-24638-1_23">10.1007/978-3-540-24638-1_23</a>'
  apa: 'Maurer, U., &#38; Pietrzak, K. Z. (2004). Composition of random systems: When
    two weak make one strong. In <i>First Theory of Cryptography Conference, 2004</i>
    (Vol. 2951, pp. 410–427). Cambridge, MA, United: Springer Nature. <a href="https://doi.org/10.1007/978-3-540-24638-1_23">https://doi.org/10.1007/978-3-540-24638-1_23</a>'
  chicago: 'Maurer, Ueli, and Krzysztof Z Pietrzak. “Composition of Random Systems:
    When Two Weak Make One Strong.” In <i>First Theory of Cryptography Conference,
    2004</i>, 2951:410–27. Springer Nature, 2004. <a href="https://doi.org/10.1007/978-3-540-24638-1_23">https://doi.org/10.1007/978-3-540-24638-1_23</a>.'
  ieee: 'U. Maurer and K. Z. Pietrzak, “Composition of random systems: When two weak
    make one strong,” in <i>First Theory of Cryptography Conference, 2004</i>, Cambridge,
    MA, United, 2004, vol. 2951, pp. 410–427.'
  ista: 'Maurer U, Pietrzak KZ. 2004. Composition of random systems: When two weak
    make one strong. First Theory of Cryptography Conference, 2004. TCC: Theory of
    Cryptography Conference, LNCS, vol. 2951, 410–427.'
  mla: 'Maurer, Ueli, and Krzysztof Z. Pietrzak. “Composition of Random Systems: When
    Two Weak Make One Strong.” <i>First Theory of Cryptography Conference, 2004</i>,
    vol. 2951, Springer Nature, 2004, pp. 410–27, doi:<a href="https://doi.org/10.1007/978-3-540-24638-1_23">10.1007/978-3-540-24638-1_23</a>.'
  short: U. Maurer, K.Z. Pietrzak, in:, First Theory of Cryptography Conference, 2004,
    Springer Nature, 2004, pp. 410–427.
conference:
  end_date: 2004-02-21
  location: Cambridge, MA, United
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2004-02-19
date_created: 2018-12-11T12:02:01Z
date_published: 2004-03-19T00:00:00Z
date_updated: 2026-09-11T12:11:09Z
day: '19'
doi: 10.1007/978-3-540-24638-1_23
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-24638-1_23
intvolume: '      2951'
language:
- iso: eng
month: '03'
oa_version: None
page: 410 - 427
publication: First Theory of Cryptography Conference, 2004
publication_identifier:
  eisbn:
  - '9783540246381'
  isbn:
  - '9783540210009'
publication_status: published
publisher: Springer Nature
publist_id: '3471'
status: public
title: 'Composition of random systems: When two weak make one strong'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2951
year: '2004'
...