Correlated-Source Extractors and Cryptography with Correlated-Random Tapes

Vipul Goyal; Yifan Song

Paper 2019/240

Correlated-Source Extractors and Cryptography with Correlated-Random Tapes

Vipul Goyal and Yifan Song

Abstract

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.

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in EUROCRYPT 2019
Keywords: Randomness Extractors Non-Malleability
Contact author(s): yifans2 @ cmu edu
vipul @ cmu edu
History: 2019-07-19: last of 2 revisions; 2019-02-28: received; See all versions
Short URL: https://ia.cr/2019/240
License: CC BY

BibTeX

@misc{cryptoeprint:2019/240,
      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{https://eprint.iacr.org/2019/240}},
      url = {https://eprint.iacr.org/2019/240}
}