Paper 2019/240

Correlated-Source Extractors and Cryptography with Correlated-Random Tapes

Vipul Goyal and Yifan Song


In this paper, we consider the setting where a party uses correlated random tapes across multiple executions of a cryptographic algorithm. We ask if the security properties could still be preserved in such a setting. As examples, we introduce the notion of correlated-tape zero knowledge, and, correlated-tape multi-party computation, where, the zero-knowledge property, and, the ideal/real model security must still be preserved even if a party uses correlated random tapes in multiple executions. Our constructions are based on a new type of randomness extractor which we call correlated-source extractors. Correlated-source extractors can be seen as a dual of non-malleable extractors, and, allow an adversary to choose several tampering functions which are applied to the randomness source. Correlated-source extractors guarantee that even given the output of the extractor on the tampered sources, the output on the original source is still uniformly random. Given (seeded) correlated-source extractors, and, resettably-secure computation protocols, we show how to directly get a positive result for both correlated-tape zero-knowledge and correlated-tape multi-party computation in the CRS model. This is tight considering the known impossibility results on cryptography with imperfect randomness. Our main technical contribution is an explicit construction of a correlated-source extractor where the length of the seed is independent of the number of tamperings. Additionally, we also provide a (non-explicit) existential result for correlated source extractors with almost optimal parameters.

Note: A correction of Section 4.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Randomness ExtractorsNon-Malleability
Contact author(s)
yifans2 @ cmu edu
vipul @ cmu edu
2019-07-19: last of 2 revisions
2019-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vipul Goyal and Yifan Song},
      title = {Correlated-Source Extractors and Cryptography with Correlated-Random Tapes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/240},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.