Non-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (zk-SNARKs) increasingly see real-world adoption in large and complex systems. Many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and for practical use it is desirable to reduce the trust in the CRS generation. The latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large systems is the ability to securely compose them to obtain more complex protocols, e.g., via the Universal Composability (UC) framework. Relying on the UC framework allows arbitrary and secure composition of protocols in a modular way. In this work, we investigate whether zk-SNARKs can provide updatability and composability simultaneously. This is a challenging task as the UC framework rules out several natural techniques for such a construction. As our main result, we show that it is indeed possible to achieve these properties in a generic and modular way if we relax the succinctness properties of zk-SNARKs slightly to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness$w$. We argue that for various practical applications of zk-SNARKs this overhead is acceptable. Our starting point is the Lamassu framework (ACM CCS'20), which we extend in several directions. Our new generic compiler adds only minimal overhead, which we demonstrate by benchmarking its application to the Sonic proof system (ACM CCS'19).

Anonymous or attribute-based credential (ABC) systems are a versatile and important cryptographic tool to achieve strong access control guarantees while simultaneously respecting the privacy of individuals. A major problem in the practical adoption of ABCs is their transferability, i.e., such credentials can easily be duplicated, shared or lent. One way to counter this problem is to tie ABCs to biometric features of the credential holder and to require biometric verification on every use. While this is certainly not a viable solution for all ABC use-cases, there are relevant and timely use-cases, such as vaccination credentials as widely deployed during the COVID-19 pandemic. In such settings, ABCs that are tied to biometrics, which we call Biometric-Bound Attribute-Based Credentials (bb-ABC ), allow to implement scalable and privacy-friendly systems to control physical access to (critical) infrastructure and facilities. While there are some previous works on bb-ABC in the literature, the state of affairs is not satisfactory. Firstly, in existing work the problem is treated in a very abstract way when it comes to the actual type of biometrics. Thus, it does not provide concrete solutions which allow for assessing their practicality when deployed in a real-world setting. Secondly, there is no formal model which rigorously captures bb-ABC systems and their security requirements, making it hard to assess their security guarantees. With this work we overcome these limitations and provide a rigorous formalization of bb-ABC systems. Moreover, we introduce two generic constructions which offer different trade-offs between efficiency and trust assumptions, and provide benchmarks from a concrete instantiation of such a system using facial biometrics. The latter represents a contact-less biometric feature that provides acceptable accuracy and seems particularly suitable to the above use-case.

Abstract We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption. Such a feature further broadens the practical applicability of the functional encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care for the security definition. Our contribution is threefold: We define our new primitive with a security notion in the indistinguishability setting. Within CUFE, functional decryption keysandciphertexts are labeled with tags such that only if the tags of the decryption key and the ciphertext match, then decryption succeeds. Furthermore, we allow ciphertexts to switch their tags to any other tag via update tokens. Such tokens are generated by the holder of the main secret key and can only be used in the desired direction. We present a generic construction of CUFE for any functionality as well as predicates different from equality testing on tags which relies on the existence of indistinguishability obfuscation (iO). We present a practical construction of CUFE for the inner-product functionality from standard assumptions (i.e., LWE) in the random-oracle model. On the technical level, we build on the recent functional encryption schemes with fine-grained access control and linear operations on encrypted data (Abdalla et al., AC’20) and introduce an additional ciphertext updatability feature. Proving security for such a construction turned out to be non-trivial, particularly when revealing keys for the updated challenge ciphertext is allowed. Overall, such construction enriches the set of known inner-product functional encryption schemes with the additional updatability feature of ciphertexts.

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.

Anonymous credential systems allow users to obtain a credential on multiple attributes from an organization and then present it to verifiers in a way that no information beyond what attributes are required to be shown is revealed. Moreover, multiple uses of the credential cannot be linked. Thus they represent an attractive tool to realize fine-grained privacy-friendly authentication and access control. In order to avoid a single point of trust and failure, decentralized AC systems have been proposed. They eliminate the need for a trusted credential issuer, e.g., by relying on a set of credential issuers that issue credentials in a threshold manner (e.g.,$t$out of$n$f). In this paper, we present a novel AC system with such a threshold issuance that additionally provides credential delegation. It represents the first decentralizedanddelegatable AC system. We provide a rigorous formal framework for such threshold delegatable anonymous credentials ($\mathsf {TDAC}$'s). Our concrete approach departs from previous delegatable ACs and is inspired by the concept of functional credentials. More precisely, we propose a threshold delegatable subset predicate encryption ($\mathsf {TDSPE}$) scheme and use$\mathsf {TDSPE}$to construct a$\mathsf {TDAC}$scheme and present a comparison with previous work and performance benchmarks based on a prototype implementation.

Traditional (physical) access control systems are well-established mechanisms, allowing organizations to determine who should be able to access which physical space. This can either be a facility such as a critical infrastructure with a well-defined set of individuals, e.g., employees, or public spaces where everyone can be subject to access control. During the Covid-19 pandemic, additional features to reduce the risks of individuals when entering spaces became popular or even mandatory, including automatic scanning for protective wear (e.g., whether an individual wears a mask), body temperature checks, or digital health certificates, certifying that one has been negatively tested for, or vaccinated against, Covid-19. We refer to this as risk-based access control (RiBAC).

Anonymous credentials (AC) offer privacy in user-centric identity management. They enable users to authenticate anonymously, revealing only necessary attributes. With the rise of decentralized systems like self-sovereign identity, the demand for efficient AC systems in a decentralized setting has grown. Relying on conventional AC systems, however, require users to present independent credentials when obtaining them from different issuers, leading to increased complexity. AC systems should ideally support being multi-authority for efficient presentation of multiple credentials from various issuers. Another vital property is issuer hiding, ensuring that the issuer's identity remains concealed, revealing only compliance with the verifier's policy. This prevents unique identification based on the sole combination of credential issuers. To date, there exists no AC scheme satisfying both properties simultaneously.

Anonymous credentials (ACs) systems are a powerful cryptographic tool for privacy-preserving applications and provide strong user privacy guarantees for authentication and access control. ACs allow users to prove possession of attributes encoded in a credential without revealing any information beyond them. A delegatable AC (DAC) system is an enhanced AC system that allows the owners of credentials to delegate the obtained credential to other users. This allows to model hierarchies as usually encountered within public-key infrastructures (PKIs). DACs also provide stronger privacy guarantees than traditional AC systems since the identities of issuers and delegators can also be hidden. In this paper we present a novel DAC scheme that supports attributes, provides anonymity for delegations, allows the delegators to restrict further delegations, and also comes with an efficient construction. Our approach builds on a new primitive that we call structure-preserving signatures on equivalence classes on updatable commitments (SPSEQ-UC). The high-level idea is to use a special signature scheme that can sign vectors of set commitments, where signatures can be extended by additional set commitments. Signatures additionally include a user's public key, which can be switched. This allows us to efficiently realize delegation in the DAC. Similar to conventional SPSEQ, the signatures and messages can be publicly randomized and thus allow unlinkable delegation and showings in the DAC system. We present further optimizations such as cross-set commitment aggregation that, in combination, enable efficient selective showing of attributes in the DAC without using costly zero-knowledge proofs. We present an efficient instantiation that is proven to be secure in the generic group model and finally demonstrate the practical efficiency of our DAC by presenting performance benchmarks based on an implementation.

Anonymous credentials (ACs) are a powerful cryptographic tool for the secure use of digital services, when simultaneously aiming for strong privacy guarantees of users combined with strong authentication guarantees for providers of services. They allow users to selectively prove possession of attributes encoded in a credential without revealing any other meaningful information about themselves. While there is a significant body of research on AC systems, modern use-cases of ACs such as mobile applications come with various requirements not sufficiently considered so far. These include preventing the sharing of credentials and coping with resource constraints of the platforms (e.g., smart cards such as SIM cards in smartphones). Such aspects are typically out of scope of AC constructions, and, thus AC systems that can be considered entirely practical have been elusive so far.

Abstract Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication. For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. (Eurocrypt, 2017). It is based on puncturable encryption. Forward secrecy is achieved by “puncturing” the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 s and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice. In this paper, we introduce a new primitive that we term Bloom filter encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.

Zero-knowledge proofs and in particular succinct non-interactive zero-knowledge proofs (so called zk-SNARKs) are getting increasingly used in real-world applications, with cryptocurrencies being the prime example. Simulation extractability (SE) is a strong security notion for zk-SNARKs which informally ensures non-malleability of proofs. The high importance of this property is acknowledged by leading companies in this field such as Zcash and underpinned by various attacks against the malleability of cryptographic primitives in the past. Another problematic issue for the practical use of zk-SNARKs is the requirement of a fully trusted setup, as especially for large-scale decentralized applications finding a trusted party that runs the setup is practically impossible. Quite recently, the study of approaches to relax or even remove the trust in the setup procedure, and in particular subversion as well as updatable zk-SNARKs (with latter being the most promising approach), has been initiated and received considerable attention since then. Unfortunately, so far SE-SNARKs with the aforementioned properties are only constructed in an ad-hoc manner and no generic techniques are available.

Incentive systems (such as customer loyalty systems) are omnipresent nowadays and deployed in several areas such as retail, travel, and financial services. Despite the benefits for customers and companies, this involves large amounts of sensitive data being transferred and analyzed. These concerns initiated research on privacy-preserving incentive systems, where users register with a provider and are then able to privately earn and spend incentive points.

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 are a central tool in privacy-enhancing cryptography, which allow members of a group to anonymously produce signatures on behalf of the group. Consequently, they are an attractive means to implement privacy-friendly authentication mechanisms. Ideally, group signatures are dynamic and thus allow to dynamically and concurrently enroll new members to a group. For such schemes, Bellare et al. (CT-RSA»05) proposed the currently strongest security model (BSZ model). This model, in particular, ensures desirable anonymity guarantees. Given the prevalence of the resource asymmetry in current computing scenarios, i.e., a multitude of (highly) resource-constrained devices are communicating with powerful (cloud-powered) services, it is of utmost importance to have group signatures that are highly-efficient and can be deployed in such scenarios. Satisfying these requirements in particular means that the signing (client) operations are lightweight.

Double-authentication-preventing signatures (DAPS) are signatures designed with the aim that signing two messages with an identical first part (called address) but different second parts (called payload) allows to publicly extract the secret signing key from two such signatures. A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address, such as penalizing double spending of transactions in Bitcoin by the loss of the double spender's money. So far DAPS have been constructed from very specific signature schemes not used in practice and using existing techniques it has proved elusive to construct DAPS schemes from signatures widely used in practice. This, unfortunately, has prevented practical adoption of this interesting tool so far. In this paper we ask whether one can construct DAPS from signature schemes used in practice. We affirmatively answer this question by presenting novel techniques to generically construct provably secure DAPS from a large class of discrete logarithm based signatures. This class includes schemes like Schnorr, DSA, EdDSA, and, most interestingly for practical applications, the widely used ECDSA signature scheme. The resulting DAPS are highly efficient and the shortest among all existing DAPS schemes. They are nearly half of the size of the most efficient factoring based schemes (IACR PKC'17) and improve by a factor of 100 over the most efficient discrete logarithm based ones (ACM CCS'15). Although this efficiency comes at the cost of a reduced address space, i.e., size of keys linear in the number of addresses, we will show that this is not a limitation in practice. Moreover, we generalize DAPS to any N > 2, which we denote as N-times-authentication-preventing signatures (NAPS). Finally, we also provide an integration of our ECDSA-based DAPS into the OpenSSL library and perform an extensive comparison with existing approaches.

We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable.

The EC Horizon 2020 project PRISMACLOUD aims at cryptographically addressing several severe risks threatening end user security and privacy in current cloud settings. This shall be achieved by the provision of a reusable toolbox encapsulating cryptographic functionality from which dependably secure cloud services can be assembled. In order to provide a tangible abstraction of the complexity involved with the construction of cryptographically secured cloud services, we introduce the four-layer PRISMACLOUD architecture. Top down, it consists of a use cases (application) layer, a services layer, a tools layer, and a cryptographic primitives and protocols layer. In this paper we provide a detailed description of the PRISMACLOUD tools in terms of functional components, as well as how they interact to provide the desired security functionality. We also briefly describe the cutting-edge cryptographic primitives which are encompassed by the tools. Both the toolbox and the cryptographic primitives and protocols are being currently developed and will be provided as reference implementation by project end in July 2018.

Cloud based collaboration gives rise to many new applications and business opportunities in both the private and the business domain. However, building such systems in a secure and robust manner is a challenging task. In this paper, we present a new architecture for secure cloud based data sharing called ARCHISTAR. It builds upon a distributed storage system and thus avoids any single point of trust or failure. Besides providing confidentiality of data, our focus is on availability and in particular on robustness against active attacks or failures. Our system provides full multi-user support and enables advanced sharing scenarios without complex key management and revocation mechanisms. We also present a prototype implementation of the ARCHISTAR system and discuss open issues.

Unique identification and secure authentication of users are essential processes in numerous security-critical areas such as e-Government, e-Banking, or e-Business. Therefore, many countries (particularly in Europe) have implemented national eID solutions within the past years. Such implementations are typically based on smart cards holding some certified collection of citizen attributes and hence follow a client-side and user-centric approach. However, most of the implementations only support all-or-nothing disclosure of citizen attributes and thus do not allow privacy-friendly selective disclosure of attributes. Consequently, the complete identity of the citizen (all attributes) are always revealed to identity providers and/or service providers, respectively. In this paper, we propose a novel user-centric identification and authentication model for eIDs, which supports selective attribute disclosure but only requires minimal changes in the existing eID architecture. In addition, our approach allows service providers to keep their infrastructure nearly untouched. Latter is often an inhibitor for the use of privacy-preserving cryptography like anonymous credentials in such architectures. Furthermore, our model can easily be deployed in the public cloud as we do not require full trust in identity providers. This fully features the Identity as a Service-paradigm while at the same time preserves citizens' privacy. We demonstrate the applicability of our model by adopting to the Austrian eID system to our approach.

In this paper we present a novel type of digital signatures, which we call blank digital signatures. The basic idea behind this scheme is that an originator can define and sign a message template, describing fixed parts of a message as well as multiple choices for exchangeable parts of a message. One may think of a form with blank fields, where for such fields the originator specifies all the allowed strings to choose from. Then, a proxy is given the power to sign an instantiation of the template signed by the originator by using some secret information. By an instantiation, the proxy commits to one allowed choice per blank field in the template. The resulting message signature can be publicly verified under the originator's and the proxy's signature verification keys. Thereby, no verifying party except the originator and the proxy learn anything about the "unused" choices from the message template given a message signature. Consequently, the template is hidden from verifiers.

Modern smartphones with the capability to be always online and equipped with data transfer interfaces such as NFC allow to take advantage of a wide variety of services and pave the way for new classes of services. Naturally, not every service will be available for free, some providers will charge money for the services provided. Usually, users are uniquely identified by the provider of a service for billing purposes and providers therefore maintain user profiles. This allows to personalize services with respect to user's interests and preferences. However, it is problematic regarding user's privacy since users disclose lots of sensitive information to the service provider. Different mobile payment solutions have been proposed to date, but privacy aspects are usually not considered at all. In this paper, we demonstrate how privacy friendly payment can be realized using a recent payment mechanisms in combination with an ARM processor platform with TrustZone enhancements. We discuss the public transport ticket domain as an example. Then we propose a platform framework that can be used for arbitrary applications requiring a privacy preserving online remote prepaid payment system suitable for micro as well as macro payments.

A central aspect of eHealth is the electronic healthcare record (EHR) which integrates all relevant medical information of a person and represents a lifelong documentation of the medical history. By virtue of their sensitive character it is crucial that medical data can only be accessed by the patient herself and persons who are directly involved in the treatment of the patient. Since eHealth portals can be accessed via the Internet, security and privacy issues arise that have to be considered carefully. Besides traditional security properties, we mainly focus on additional threats, namely the trivial disclosure attack and the statistical analysis of metadata. Thereby a disclosure attack takes place if a person enforces another person to present her EHR, e.g. during a job interview. Additionally, by applying statistical analysis on the metadata of an eHealth portal, it is possible to determine relevant information (e.g. psychological treatment) which could have negative effects on the patient. In this paper we present a concept including pseudonymization of medical data, identity management, obfuscation of metadata and anonymous authentication to prevent disclosure attacks and statistical analysis.