期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the notion of multi-collision resistance of hash functions --- a natural relaxation of collision-resistance 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. Specifically, in the keyless 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.
