You are looking at a specific version 20170206:193554 of this paper. See the latest version.

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 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
tibor jager @ upb de
History
2018-09-03: last of 5 revisions
2017-01-31: received
See all versions
Short URL
https://ia.cr/2017/061
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.