Cryptology ePrint Archive: Report 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.

Category / Keywords: Randomness Extractors, Non-Malleability

Original Publication (with minor differences): IACR-EUROCRYPT-2019

Date: received 27 Feb 2019, last revised 19 Jul 2019

Contact author: yifans2 at cmu edu,vipul@cmu edu

Available format(s): PDF | BibTeX Citation

Note: A correction of Section 4.

Version: 20190719:183054 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]