You are looking at a specific version 20190228:200045 of this paper. See the latest version.

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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Keywords
Randomness ExtractorsNon-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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.