Cryptology ePrint Archive: Report 2017/061

Continuous Collision Resistance and its Applications

Tibor Jager and Rafael Kurek

Abstract: We introduce a new, simple and non-interactive complexity assumption for cryptographic hash functions, which seems very reasonable for standard functions like SHA-3. We describe how this assumption can be leveraged to obtain standard-model constructions that previously seemed to require a programmable random oracle: a generic construction of identity-based key encapsulation (ID-KEM) with full adaptive security from a scheme with very weak security ("selective and non-adaptive chosen-ID security"), a similar generic construction for digital signatures, and the first constructions of ID-KEMs and signatures over bilinear groups, where a ciphertext or signature consists of only a single group element and which achieve full adaptive security without random oracles.

Continuous collision resistance can be viewed as a way to realize certain potential applications of \emph{extremely lossy functions} (ELFs; Zhandry, CRYPTO 2016) with a standard cryptographic primitive. Furthermore, known ELF constructions had only "nearly black-box" security proofs, because the reduction was assumed to "know" sufficiently close approximations of the running time and success probability of a given adversary. In contrast, our constructions allow for full black-box security proofs without this requirement. The main drawback of our schemes, from a practical perspective, is that the reductions in the security proof are very non-tight, and some are based on strong "q-type" assumptions. Therefore our results are mainly of conceptual interest, but not yet suitable for practical deployment.

Category / Keywords:

Date: received 27 Jan 2017, last revised 6 Feb 2017

Contact author: tibor jager at upb de

Available format(s): PDF | BibTeX Citation

Version: 20170206:193554 (All versions of this report)

Short URL: ia.cr/2017/061

Discussion forum: Show discussion | Start new discussion