Paper 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 element of a prime-order group and which achieve full adaptive security without random oracles. Continuous collision resistance can be viewed as a way to realize certain potential applications of extremely lossy functions (ELFs; Zhandry, CRYPTO 2016) with a standard cryptographic primitive, which partially resolves the open problem of constructing ELFs based on symmetric-key techniques.