Abstract Chameleon-hash functions, introduced by Krawczyk and Rabin (NDSS’00), are trapdoor collision-resistant hash functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be found efficiently. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications, ranging from editable blockchains to advanced signature and encryption schemes. We observe that, in latter applications, various different notions of collision-resistance are used, and it is not always clear if the respective notion really covers what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and by means of selected applications discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature (which we call full collision-resistance). Finally, we present a surprisingly simple, and efficient, black-box construction of chameleon-hash functions achieving this strong notion of full collision-resistance.

Protean signatures (PSs), recently introduced by Krenn et al . (CANS ‘18), allow a semi‐trusted third party (the sanitiser ), to modify a signed message in a controlled way: the signer can define the message parts to be arbitrarily editable by the sanitiser, as well as message parts which can be redacted (but not altered otherwise) by the sanitiser. Thus, PS s generalise both redactable signatures (RSs) and sanitisable signatures (SSs) into a single notion. Invisibility for PSs guarantees that no outsider (i.e. any party not being signer or sanitiser) can decide which message parts can be edited. However, the current definition of invisibility does not prohibit that an outsider can decide which parts are redactable – only which parts can be edited are hidden. This negatively impacts the privacy guarantees provided by this definition. The authors extend PSs to be fully invisible. Their notion guarantees that an outsider can identify neither editable nor redactable parts. They, therefore, introduce the new notions of invisible RS s and invisible non‐accountable SSs ( ), along with a consolidated framework for aggregate signatures. Using those building blocks, their resulting construction is significantly more efficient than the original scheme by Krenn et al ., which they demonstrate in a prototypical implementation.

Group signatures allow creating signatures on behalf of a group, while remaining anonymous. To prevent misuse, there exists a designated entity, named the opener, which can revoke anonymity by generating a proof which links a signature to its creator. Still, many intermediate cases have been discussed in the literature, where not the full power of the opener is required, or the users themselves require the power to claim (or deny) authorship of a signature and (un-)link signatures in a controlled way. However, these concepts were only considered in isolation.

Sanitizable signature schemes (SSS), as well as redactable signature schemes (RSS), gained a lot of attention in the recent past. In a nutshell, both types of signature schemes allow to alter signed data in a controlled way by a, potentially semi-trusted, third party. The resulting signatures still verify. Thus, the authenticity of the subsequently modified content is preserved. In this position paper, we discuss the state-of-the-art, and highlight potential future research opportunities. We hope this work gives rise to additional ideas, real-life use-cases, and interesting upcoming research, helping to bring both primitives into practice. Hence, this paper is meant as a starting point for readers interested in these primitives, looking for new research and application opportunities. In other words, we think that both primitives deserve further attention.

The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.

Membership revocation is essential for cryptographic applications, from traditional PKIs to group signatures and anonymous credentials. Of the various solutions for the revocation problem that have been explored, dynamic accumulators are one of the most promising. We propose Braavos, a new, RSA-based, dynamic accumulator. It has optimal communication complexity and, when combined with efficient zero-knowledge proofs, provides an ideal solution for anonymous revocation. For the construction of Braavos we use a modular approach: we show how to build an accumulator with better functionality and security from accumulators with fewer features and weaker security guarantees. We then describe an anonymous revocation component (ARC) that can be instantiated using any dynamic accumulator. ARC can be added to any anonymous system, such as anonymous credentials or group signatures, in order to equip it with a revocation functionality. Finally, we implement ARC with Braavos and plug it into Idemix, the leading implementation of anonymous credentials. This work resolves, for the first time, the problem of practical revocation for anonymous credential systems.

The 4-eyes principle (4EP) is a well-known access control and authorization principle, and used in many scenarios to minimize the likelihood of corruption. It states that at least two separate entities must approve a message before it is considered authentic. Hence, an adversarial party aiming to forge bogus content is forced to convince other parties to collude in the attack. We present a formal framework along with a suitable security model. Namely, a party sets a policy for a given message which involves multiple additional approvers in order to authenticate the message. Finally, we show how these signatures are black-box realized by secure sanitizable signature schemes.

Redactable signature schemes (RSS) allow removing blocks from signed data. State-of-the-art schemes have public redactions, i.e., Any party can remove parts from a signed message. This prohibits meaningful definitions of accountability. We address this gap by introducing the notion of accountable redactable signature schemes (ARSS). We present a generic construction which couples a sanitizable signature scheme (SSS) to profit from its accountability with an RSS to maintain the reduced malleability of RSSs. Depending on the building blocks, the resulting scheme offers transparency or public accountability. Transparency provides stronger privacy guarantees, while public accountability meets legal and application requirements.

Sanitizable signature schemes allow for altering signed data in a signer-controlled way by a semi-trusted third party. This is contrary to standard digital signature schemes, which do not permit any modifications by any party without invalidating the signature. Due to transparency, a strong privacy notion, outsiders cannot see if the signature for a message was created by the signer or by the semi-trusted party. Accountability allows the signer to prove to outsiders if a message was original or touched by the semi-trusted party. Currently, block-level accountability requires to drop transparency. We allow for accountability for sanitizable signatures with transparency on the block-level. Additionally, we generalize the concept of block-level properties to groups. This offers a even more fine-grained control and leads to more efficient schemes. We prove that group-level definitions imply both the block-level and message-level notions. We derive a provably secure construction, achieving our enhanced notions. A further modification of our construction achieves efficient group-level non-interactive public accountability. This construction only requires a constant amount of signature generations to achieve this property. Finally, we have implemented our constructions and the scheme introduced by Brzuska et al. at PKC '09 and provide a detailed performance analysis of our reference implementations.