You are looking at a specific version 20170621:005658 of this paper. See the latest version.

Paper 2017/488

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Nir Bitansky and Yael Tauman Kalai and Omer Paneth

Abstract

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. In the unkeyed setting we only require that the size of collisions an adversarial algorithm can find is not much larger than its description size, or non-uniform advice. We show how to replace collision resistance with multi-collision resistance in several foundational applications, improving on the best known round complexity, obtaining: - 3-message zero-knowledge arguments for NP. - 3-message succinct arguments of knowledge for NP. - 4-message epsilon-zero-knowledge proofs for NP. - 5-message public-coin zero-knowledge arguments for NP. Our techniques can also be applied in the keyed setting, at the cost of adding another message. In this case, we weaken the known complexity assumptions for the last three applications, while still matching the state of the art in terms of round complexity. The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
hash functionszero knowledgesuccinct arguments
Contact author(s)
nbitansky @ gmail com
History
2018-08-06: last of 2 revisions
2017-05-31: received
See all versions
Short URL
https://ia.cr/2017/488
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.