Christoph Striecks | publications

2024

Identity-Based Encryption with (Almost) Tight Security in the Multi-instance, Multi-ciphertext Setting

With Dennis Hofheinz, and Jessica Koch.

Journal of Cryptology (accepted).

Abstract ePrint

We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (Crypto 2013). The security loss of our reduction is O(k)(where k is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to "lift" their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.
(Inner-Product) Functional Encryption with Updatable Ciphertexts

With Valerio Cini, Sebastian Ramacher, Daniel Slamanig, and Erkan Tairi.

Journal of Cryptology.

Abstract URL ePrint

We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional encryption paradigm and is carried out via so-called update tokens. However, allowing update tokens requires some care for the security definition as we want that updates can be done by any semi-trusted third party and only on ciphertexts. Our contribution is three-fold: a) We define our new primitive with a security notion in the indistinguishability setting. Within CUFE, functional decryption keys and ciphertexts are labeled with tags such that only if the tag 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. b) 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 (probabilistic) indistinguishability obfuscation (iO). c) 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.

2023

Revisiting Updatable Encryption: Controlled Forward Security, Constructions and a Puncturable Perspective

With Daniel Slamanig.

TCC 2023, November 29 - December 2. (Recorded talk given by Roman Langrehr from ETH Zurich.)

Abstract URL ePrint Talk Slides

Updatable encryption (UE) allows a third party to periodically rotate encryption keys from one epoch to another without the need to download, decrypt, re-encrypt, and upload already encrypted data by a client. Updating those outsourced ciphertexts is carried out via the use of so-called update tokens which in turn are generated during key rotation and can be sent (publicly) to the third party. The arguably most efficient variant of UE is ciphertext-independent UE as the key rotation does not depend on the outsourced ciphertexts which makes it particularly interesting in scenarios where access to (information of the) ciphertexts is not possible during key rotation. Available security notions cannot guarantee any form of _forward security_ (i.e., old ciphertexts are in danger after key leakage). Counter-intuitively, forward security would violate correctness, as ciphertexts should be updatable ad-infinitum given the update token. In this work, we investigate if we can have at least some form of "controlled" forward security to mitigate the following shortcoming: an adversary would record available information (i.e., some ciphertexts, all update tokens) and simply would wait for a single key leakage to decrypt all data ever encrypted. Our threefold contribution is as follows: a) First, we introduce an epoch-based UE CPA security notion to allow fine-grained updatability. It covers the concept of expiry epochs, i.e., ciphertexts can lose the ability of being updatable via a token after a certain epoch has passed. This captures the above mentioned shortcoming as the encrypting party can decide how long a ciphertext can be updatable (and, hence, decryptable). b) Second, we introduce a novel approach of constructing UE which significantly departs from previous ones and in particular views UE from the perspective of puncturable encryption (Green and Miers, S&P’15). We define tag-inverse puncturable encryption as a new variant that generalizes UE and may be of independent interest. c) Lastly, we present and prove secure the first UE scheme with the aforementioned properties. It is constructed via tag-inverse puncturable encryption and instantiated from standard assumptions. As it turned out, constructing such puncturing schemes is not straightforward and we require adapted proof techniques. Surprisingly, as a special case, this yields the first backwards-leak UE scheme with sub-linear ciphertexts from standard assumptions (an open problem posted in two recent works by Jiang Galteland and Pan & Miao et al., PKC’23).
Optimizing 0-RTT Key Exchange with Full Forward Security

With Christian Göth, Sebastian Ramacher, Daniel Slamanig, Erkan Tairi, and Alexander Zikulnig.

14th Cloud Computing Security Workshop - CCSW 2023, November 26.

Abstract URL PDF

Secure communication protocols such as TLS 1.3 or QUIC are doing the heavy lifting in terms of security of today’s Internet. These modern protocols provide modes that do not need an interactive handshake, but allow to send cryptographically protected data with the first client message in zero round-trip time (0-RTT). While this helps to reduce communication latency, the security of such protocols in terms of forward security is rather weak. In recent years, the academic community investigated ways of mitigating this problem and achieving full forward security and replay resilience for such 0-RTT protocols. In particular, this can be achieved via a so-called Puncturable Key Encapsulation Mechanism (PKEM). While the first such schemes were too expensive to be used in practice, Derler et al. (EUROCRYPT 2018) proposed a variant of PKEMs called Bloom Filter Key Encapsulation Mechanism (BFKEM). Unfortunately, these primitives have only be investigated asymptotically and no real benchmarks were conducted. Dallmeier et al. (CANS 2020) were the first to study their practical application within the QUIC protocol. They build upon a specific BFKEM instantiation and conclude that while it comes with significant computational overhead, its practical use is feasible, especially in applications where the increased CPU and memory load can be tolerated. In this paper, we revisit their choice of the concrete BFKEM instantiation and show that by relying on the concept of Time-based BFKEMs (TB-BFKEMs), also introduced by Derler et al. (EUROCRYPT 2018), one can combine the advantages of having computational efficiency and smaller key sizes. We thereby investigate algorithmic as well as conceptual optimizations with various trade-offs and conclude that our approach seems favorable for many practical settings. Overall, this extends the applicability of 0-RTT protocols with strong security in practice.
Muckle+: End-to-End Hybrid Authenticated Key Exchanges

With Sonja Bruckner, and Sebastian Ramacher.

PQCrypto 2023, August 16-18.

Abstract URL PDF ePrint Talk Slides

End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).
Unique-Path Identity Based Encryption With Applications to Strongly Secure Messaging

With Paul Rösler, and Daniel Slamanig.

Eurocrypt 2023, Lyon, France, April 23-27.

Abstract URL PDF ePrint

Hierarchical Identity Based Encryption (HIBE) is a well studied, versatile tool used in many cryptographic protocols. Yet, since the performance of all known HIBE constructions is broadly considered prohibitive, some real-world applications avoid relying on HIBE at the expense of security. A prominent example for this is secure messaging: Strongly secure messaging protocols are provably equivalent to Key-Updatable Key Encapsulation Mechanisms (KU-KEMs; Balli et al., Asiacrypt 2020); so far, all KU-KEM constructions rely on adaptive unbounded-depth HIBE (Poettering and Rösler, Jaeger and Stepanovs, both CRYPTO 2018). By weakening security requirements for better efficiency, many messaging protocols dispense with using HIBE. In this work, we aim to gain better efficiency without sacrificing security. For this, we observe that applications like messaging only need a restricted variant of HIBE for strong security. This variant, that we call Unique-Path Identity Based Encryption (UPIBE), restricts HIBE by requiring that each secret key can delegate at most one subordinate secret key. However, in contrast to fixed secret key delegation in Forward-Secure Public Key Encryption, the delegation in UPIBE, as in HIBE, is uniquely determined by variable identity strings from an exponentially large space. We investigate this mild but surprisingly effective restriction and show that it offers substantial complexity and performance advantages. More concretely, we generically build bounded-depth UPIBE from only bounded-collusion IBE in the standard model; and we generically build adaptive unbounded-depth UPIBE from only selective bounded-depth HIBE in the random oracle model. These results significantly extend the range of underlying assumptions and efficient instantiations. We conclude with a rigorous performance evaluation of our UPIBE design. Beyond solving challenging open problems by reducing complexity and improving efficiency of KU-KEM and strongly secure messaging protocols, we offer a new definitional perspective on the bounded-collusion setting.

2022

Logarithmic-Size (Linkable) Threshold Ring Signatures in the Plain Model

With Abida Haque, Stephan Krenn, and Daniel Slamanig.

PKC 2022, Virtual, March 7-11.

Abstract URL PDF ePrint

Ring signatures are a cryptographic primitive that allow a signer to anonymously sign messages on behalf of an ad-hoc group of N potential signers (the so-called ring). This primitive has attracted significant research since its introduction by Rivest et al. (ASIACRYPT’01), but until recently, no construction was known that was both (i) compact, i.e., the signature size is sub-linear in N, and (ii) in the plain model, i.e., secure under standard hardness assumptions without requiring heuristic or setup assumptions. The first construction in this most desirable set- ting, where reducing trust in external parties is the primary goal, was only recently presented by Backes et al. (EUROCRYPT’19). An interesting generalization of ring signatures are t-out-of-N ring signa- tures for t ≥ 1, also known as threshold ring (thring) signatures (Bresson et al., CRYPTO’02). For threshold ring signatures, non-linkable sub-linear-size constructions are not even known under heuristic or setup assumptions. In this work, we propose the first sub-linear thring signatures and prove them secure in the plain model. While our constructions are inspired by the template underlying the Backes et al. construction, they require novel ideas and techniques. Our scheme is non-interactive, and has strong inter- signer anonymity, meaning that signers do not need to know the other signers that participate in a threshold signing. We then present a linkable counterpart to our non-linkable construction. Our thring signatures can easily be adapted to achieve the recently introduced notions of flexibility (Okamoto et al., EPRINT’18) as well as claimability and repudiability (Park and Sealfon, CRYPTO’19). (Th)Ring signatures and, in particular, their linkable versions have recently drawn significant attention in the field of privacy-friendly cryptocurrencies. We discuss applications that are enabled by our strong inter-signer anonymity, demonstrating that thring signatures are interesting from a practical perspective also.

2021

Versatile and Sustainable Timed-Release Encryption and Sequential Time-Lock Puzzles

With Peter Chvojka, Tibor Jager, and Daniel Slamanig.

European Symposium on Research in Computer Security (ESORICS) 2021, Virtual, October 4-8.

Abstract URL PDF ePrint

Timed-release encryption (TRE) makes it possible to send messages "into the future" such that a pre-determined amount of time needs to pass before a message can be accessed. The most prominent construction is based on sequential squaring in RSA groups, proposed by Rivest et al. in 1996. Malavolta and Thyagarajan (CRYPTO’19) recently introduced an interesting variant of TRE called homomorphic time-lock puzzles (HTLPs), making TRE more versatile and greatly extending its applications. Here one considers multiple independently generated puzzles and the homomorphic evaluation of a circuit over these puzzles. Solving the so obtained puzzle yields the output of a circuit evaluated on the messages locked by the original puzzles. We observe that viewing HTLPs more abstractly gives rise to a simple generic construction of homomorphic TRE (HTRE) that is not necessarily based on sequential squaring, but can be instantiated based on any TLP, such as those based on one-way functions and the LWE assumption (via randomized encodings). This construction has slightly different properties, but provides essentially the same functionality for applications. It makes TRE versatile and can be used beyond HTRE, for instance to construct timed-release functional encryption. Interestingly, it achieves a new "solve one, get many for free" property, which supports that an arbitrary number of independently time-locked (homomorphically evaluated) messages can all be obtained simultaneously after solving only a single puzzle. This puzzle is independent of the number of time-locked messages and thus achieves optimal amortized cost. As a second contribution we define and construct sequential TLPs as a particularly useful generalization of TLPs and TRE. Such puzzles can be solved sequentially in a way that solving a puzzle additionally considers the previous solution and the time required to solve the puzzle is determined by the difference in the time parameters. When instantiated from sequential squaring, this allows to realize public "sequential squaring services", where everyone can time-lock messages, but only one entity needs to perform the computations required to solve puzzles. Thus, this removes the burden of wasting computational resources by every receiver and makes TRE economically and ecologically more sustainable.
Guideline for Architectural Safety, Security and Privacy Implementations Using Design Patterns: SECREDAS Approach

With Nadja Marko, Joaquim Maria Castella Triginer, Tobias Braun, Reinhard Schwarz, Stefan Marksteiner, Alexandr Vasenev, Joerg Kemmerich, Hayk Hamazaryan, Lijun Shan, and Claire Loiseaux.

Computer Safety, Reliability, and Security. SAFECOMP Workshops – DECSoS 2021, Virtual, September 7-10.

Abstract URL PDF

Vehicle systems engineering experiences new challenges with vehicle electrification, advanced driving systems, and connected vehicles. Modern architectural designs cope with an increasing number of functionalities integrated into complex Electric/Electronic (E/E) systems. Such complexity is extended, adding V2X (Vehicle-to-everything) communication systems, which provide remote communication services that collect, store, and manipulate confidential data. The impact on Safety, Security, and Privacy (SSP) of these new advanced technological systems requires the implementation of new processes during their development phase. Therefore, new product development strategies need to be implemented to integrate SSP mechanism across the entire product development lifecycle. The European H2020 ECSEL project SECREDAS proposes an innovative solution for Safety, Security and Privacy specifically for automated systems. The project outlines the shortcomings of existing SSP approaches and proposes its own approach to implementing SSP mechanism for the emerging technologies. This approach includes a reference architecture with SSP features implemented by a set of reusable Design Patterns (DPs) along with their associated technology elements. This guideline proposes rules for developing new architectural Safety, Security, and Privacy implementations in a product under development using Design Patterns.
Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

With David Derler, Kai Gellert, Tibor Jager, and Daniel Slamanig.

Journal of Cryptology, Volume 34, 2021.

Abstract URL PDF ePrint

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 seconds 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.
Updatable Signatures and Message Authentication Codes

With Valerio Cini, Sebastian Ramacher, Daniel Slamanig, and Erkan Tairi.

PKC 2021, Virtual, May 10-13. (Recorded talk given by Valerio Cini and Erkan Tairi.)

Abstract URL PDF ePrint Talk

Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO’94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC’17) as well as concrete practical motivations (Lehmann et al., EC’18; Groth et al. CRYPTO’18; Klooß et al., EC’19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update “old” cryptographic objects, e.g., signatures or message authentication codes, from the “old” key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token). Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC’18) and Boyd et al. (CRYPTO’20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.
Fine-Grained Forward Secrecy: Allow-List/Deny-List Encryption and Applications

With David Derler, Sebastian Ramacher, and Daniel Slamanig.

Financial Cryptography and Data Security 2021, Virtual, March 1-5. (Recorded talk given with Sebastian Ramacher and Daniel Slamanig.)

Abstract URL PDF ePrint Talk

Forward secrecy is an important feature for modern cryptographic systems and is widely used in secure messaging such as Signal and WhatsApp as well as in common Internet protocols such as TLS, IPSec or SSH. The benefits of forward secrecy is that the damage in case of key-leakage is mitigated. Forward-secret encryption schemes provides security of past ciphertexts even if secret key leaks, which is interesting in settings where cryptographic keys often reside in memory for quite a long time and could be extracted by an adversary, e.g., in cloud computing. The recent concept of puncturable encryption (PE; IEEE S&P’15) provides a versatile generalization of forward-secret encryption: it allows to puncture secret keys with respect to ciphertexts to prevent the future decryption of these ciphertexts. Thus it represents a fine-grained mechanism to restrict decryption capabilities of a secret key to reduce damage in case of key leakage. We introduce the abstraction of allow-list/deny-list encryption schemes, and classify different types of PE schemes using this abstraction. Based on our classification we identify and close a gap in existing work by introducing a novel variant of PE which we dub Dual-Form Puncturable Encryption (DFPE). DFPE significantly enhances and in particular generalizes previous variants of PE, by allowing an interleaved application of allow- and deny-list operations. We present a construction of DFPE in prime order bilinear groups based on the novel primitive of tagged hierarchical identity-based encryption (THIBE). We discuss a direct application of DPFE for enhancing security guarantees within Cloudflare’s Geo Key Manager and show its generic use to construct forward-secret IBE and forward-secret digital signatures.

2020

CCA-Secure (Puncturable) KEMs from Encryption with Non-Negligible Decryption Errors

With Valerio Cini, Sebastian Ramacher, and Daniel Slamanig.

ASIACRYPT 2020, Daejeon, South Korea, December 7-11. (Recorded talk given by Valerio Cini.)

Abstract URL PDF ePrint Talk

Public-key encryption (PKE) schemes or key-encapsulation mechanisms (KEMs) are fundamental cryptographic building blocks to realize secure communication protocols. There are several known transformations that generically turn weakly secure schemes into strongly (i.e., IND-CCA) secure ones. While most of these transformations require the weakly secure scheme to provide perfect correctness, Hofheinz, Hövelmanns, and Kiltz (HHK) (TCC 2017) have recently shown that variants of the Fujisaki-Okamoto (FO) transform can work with schemes that have negligible correctness error in the (quantum) random oracle model (QROM). Many recent schemes in the NIST post-quantum competition (PQC) use variants of these transformations. Some of their CPA-secure versions even have a non-negligible correctness error and so the techniques of HHK cannot be applied. In this work, we study the setting of generically transforming PKE schemes with potentially large, i.e., non-negligible, correctness error to ones having negligible correctness error. While there have been previous treatments in an asymptotic setting by Dwork et al. (EUROCRYPT 2004), our goal is to come up with practically efficient compilers in a concrete setting and apply them in two different contexts: firstly, we show how to generically transform weakly secure deterministic or randomized PKEs into CCA-secure KEMs in the (Q)ROM using variants of HHK. This applies to essentially all candidates to the NIST PQC based on lattices and codes with non-negligible error, for which we provide an extensive analysis. We thereby show that it improves some of the code-based candidates. Secondly, we study puncturable KEMs in terms of the Bloom Filter KEM (BFKEM) proposed by Derler et al. (EUROCRYPT 2018) which inherently have a non-negligible correctness error. BFKEMs are a building block to construct fully forward-secret zero round-trip time (0-RTT) key-exchange protocols. In particular, we show how to achieve the first post-quantum secure BFKEM generically from lattices and codes by applying our techniques to identity-based encryption (IBE) schemes with (non-)negligible correctness error.
Privacy-Preserving Incentive Systems with Highly Efficient Point-Collection

With Jan Bobolz, Fabian Eidens, Stephan Krenn, and Daniel Slamanig.

AsiaCCS 2020, Taipei, Taiwan, October 5-9.

Abstract URL PDF ePrint

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. In this paper we construct an incentive system that improves upon the state-of-the-art in several ways: (1) We improve efficiency of the Earn protocol by replacing costly zero-knowledge proofs with a short structure-preserving signature on equivalence classes. (2) We enable tracing of remainder tokens from double-spending transactions without losing backward unlinkability. (3) We allow for secure recovery of failed Spend protocol runs (where usually, any retries would be counted as double-spending attempts). (4) We guarantee that corrupt users cannot falsely blame other corrupt users for their double-spending. We propose an extended formal model of incentive systems and a concrete instantiation using homomorphic Pedersen commitments, ElGamal encryption, structure-preserving signatures on equivalence classes (SPS-EQ), and zero-knowledge proofs of knowledge. We formally prove our construction secure and present benchmarks showing its practical efficiency.
Collecting and Classifying Security and Privacy Design Patterns for Connected Vehicles: SECREDAS Approach

With Nadja Marko, and Alexandr Vasenev.

Computer Safety, Reliability, and Security. SAFECOMP 2020 Workshops – DECSoS 2020, Lisbon, Portugal, September 15.

Abstract URL PDF

In the past several years, autonomous driving turned out to be a target for many technical players. Automated driving requires new and advanced mechanisms to provide safe functionality and the increased communication makes automated vehicles more vulnerable to attacks. Security is already well-established in some domains, such as the IT sector, and now spills over to Automotive. In order to not reinvent the wheel, existing security methods and tools can be evaluated and adapted to be applicable in other domains, such as Automotive. In the European H2020 ECSEL project SECREDAS, this approach is followed and existing methods, tools, protocols, best practices etc. are analyzed, combined and improved to be applicable in the field of connected vehicles. To provide modular and reusable designs, solutions are collected in form of design patterns. The SECREDAS design patterns describe solution templates to solve security, safety and privacy issues related to automated systems. The grouping and classification of design patterns is important to facilitate the selection process which is a challenging task and weak classification schemes can be a reason for a sparse application of security patterns, which represent a subgroup of design patterns. This work aims to assist automotive software and systems engineers in adopting and using technologies available on the market. The SECREDAS security patterns are based on existing technologies, so-called Common Technology Elements, and describe how and where to apply them in context of connected vehicles by making a reference to a generic architecture. This allows developers to easily find solutions to common problems and reduces the development effort by providing concrete, trustworthy solutions. The whole approach and classification scheme is illustrated based on one example security pattern.

2019

Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based

With David Derler, Kai Samelin, and Daniel Slamanig.

NDSS 2019, San Diego, USA, February 24-27. (Invited to ACM Advances in Financial Technologies (AFT 2019) as highlights-track presentation.)

Abstract URL PDF ePrint Talk Slides

Blockchain technologies recently received a considerable amount of attention. While the initial focus was mainly on the use of blockchains in the context of cryptocurrencies such as Bitcoin, application scenarios now go far beyond this. Most blockchains have the property that once some object, e.g., a block or a transaction, has been registered to be included into the blockchain, it is persisted and there are no means to modify it again. While this is an essential feature of most blockchain scenarios, it is still often desirable—at times it may be even legally required–to allow for breaking this immutability in a controlled way. Only recently, Ateniese et al. (EuroS&P 2017) proposed an elegant solution to this problem on the block level. Thereby, the authors replace standard hash functions with so-called chameleon-hashes (Krawczyk and Rabin, NDSS 2000). While their work seems to offer a suited solution to the problem of controlled re-writing of blockchains, their approach is too coarse-grained in that it only offers an all-or-nothing solution. We revisit this idea and introduce the novel concept of policy-based chameleon-hashes (PBCH). PBCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects. Besides modeling PBCHs, we present a generic construction of PBCHs (using a strengthened version of chameleon-hashes with ephemeral trapdoors which we also introduce), rigorously prove its security, and instantiate it with efficient building blocks. We report first implementation results.
Practical Group-Signatures with Privacy-Friendly Openings

With Stephan Krenn, and Kai Samelin.

International Conference on Availability, Reliability and Security (ARES) 2019, Canterbury, UK, August 26-29.

Abstract URL PDF ePrint

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. We unify these approaches, supporting all these possibilities simultaneously, providing fine-granular openings, even by members. Namely, a member can prove itself whether it has created a given signature (or not), and can create a proof which makes two created signatures linkable (or unlinkable resp.) in a controlled way. Likewise, the opener can show that a signature was not created by a specific member and can prove whether two signatures stem from the same signer (or not) without revealing anything else. Combined, these possibilities can make full openings irrelevant in many use-cases. This has the additional benefit that the requirements on the reachability of the opener are lessened. Moreover, even in the case of an involved opener, our framework is less privacy-invasive, as the opener no longer requires access to the signed message. Our provably secure black-box CCA-anonymous construction with dynamic joins requires only standard building blocks. We prove its practicality by providing a performance evaluation of a concrete instantiation, and show that our non-optimized implementation is competitive compared to other, less feature-rich, notions.

2018

Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

With David Derler, Tibor Jager, and Daniel Slamanig.

EUROCRYPT 2018, Tel Aviv, Israel, April 29 - May 3. (Recorded talk at Real World Crypto 2018 and EUROCRYPT 2018 given by David Derler.)

Abstract URL PDF ePrint Talk RWC Talk EC

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 pay- load 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. (Euro- crypt 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 seconds 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.
Revisiting Proxy Re-encryption: Forward Secrecy, Improved Security, and Applications

With David Derler, Stephan Krenn, Thomas Lorünser, Sebastian Ramacher, and Daniel Slamanig.

PKC 2018, Rio de Janeiro, Brazil, March 25-29.

Abstract URL PDF ePrint

We revisit the notion of proxy re-encryption (PRE), an enhanced public-key encryption primitive envisioned by Blaze et al. (Eurocrypt’98) and formalized by Ateniese et al. (NDSS’05) for delegating decryption rights from a delegator to a delegatee using a semi- trusted proxy. PRE notably allows to craft re-encryption keys in order to equip the proxy with the power of transforming ciphertexts under a delegator’s public key to ciphertexts under a delegatee’s public key, while not learning anything about the underlying plaintexts. We study an attractive cryptographic property for PRE, namely that of forward secrecy. In our forward-secret PRE (fs-PRE) definition, the proxy periodically evolves the re-encryption keys and permanently erases old versions while he delegator’s public key is kept constant. As a consequence, ciphertexts for old periods are no longer re-encryptable and, in particular, cannot be decrypted anymore at the delegatee’s end. Moreover, delegators evolve their secret keys too, and, thus, not even they can decrypt old ciphertexts once their key material from past periods has been deleted. This, as we will discuss, directly has application in short-term data/message-sharing scenarios. Technically, we formalize fs-PRE. Thereby, we identify a subtle but significant gap in the well-established security model for conventional PRE and close it with our formalization (which we dub fs-PRE+). We present the first provably secure and efficient constructions of fs-PRE as well as PRE (implied by the former) satisfying the strong fs-PRE+ and PRE+ notions, respectively. All our constructions are instantiable in the standard model under standard assumptions and our central build- ing block are hierarchical identity-based encryption (HIBE) schemes that only need to be selectively secure.
Engineering Cryptography for Security and Privacy in the Cloud

With Stephan Krenn, and Thomas Lorünser.

ERCIM News 2018.

Abstract URL

A large body of research in cryptography was established over recent decades but little of it has been commercialised. This is to the detriment of cloud computing, where the new methods would help to establish end-to-end security, which is not yet common practice. Cloud computing has made its way into all domains and remains one of the major growth areas in information and communication technology. It will also form the main backend platform of the internet of things and therefore play a crucial role in information society. Nevertheless, it still suffers from its outsourcing paradigm and intrinsic security and privacy problems. Cryptographic research has made substantial progress over recent years and now provides a portfolio of mature cryptographic primitives and protocols suitable for addressing several of these problems in an effective and efficient way. Nevertheless, there still exists a substantial gap between what is possible and what is actually available in the cloud. In PRISMACLOUD and CREDENTIAL we analysed the situation, extracted main inhibitors and developed promotors for the use and integration of cryptography in engineering work flows of interdisciplinary projects.

2017

Agile cryptographic solutions for the cloud

With Thomas Lorünser, Stephan Krenn, and Thomas Länger.

Elektrotechnik und Informationstechnik 2017.

Abstract URL PDF

Cloud computing, with its estimated market size of 150 billion USD annual turnover, is one of the major growth areas in information and communication technologies today. As a paradigm building on outsourcing of storage and processing, cloud computing suffers from intrinsic security and privacy problems. However, cryptographic research has made substantial progress over the last years and today provides a portfolio of mature cryptographic primitives and protocols suitable for addressing several of these problems in an effective and efficient way. Nevertheless, today’s reality shows that there exists a gap between what is possible and what is actually available in the cloud. We will present a detailed analysis of inhibitors and roadblocks standing in the way of an extensive deployment of cryptographic protection to cloud services, and how organizational and procedural measures may support the practical deployment of cryptography. We conclude our article with an overview of novel cryptographic schemes and their potential for protection of end-user data during storage and processing in the cloud, once they will become widely available.
Towards Attribute-Based Credentials in the Cloud

With Stephan Krenn, Thomas Lorünser, and Anja Salzer.

CANS 2017, Hong Kong, China, November 30 - December 2.

Abstract URL PDF

Attribute-based credentials (ABCs, sometimes also anonymous credentials) are a core cryptographic building block of privacy-friendly authentication systems, allowing users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion. Thereby, users have full control over which attributes the user wants to reveal to a third party while offering high authenticity guarantees to the receiver. Unfortunately, up to date, all known ABC systems require access to all attributes in the clear at the time of proving possession of a credential to a third party. This makes it hard to offer privacy-preserving identity management systems "as a service," as the user still needs specific key material and/or dedicated software locally, e.g., on his device. We address this gap by proposing a new cloud-based ABC system where a dedicated cloud service ("wallet") can present the users’ credentials to a third-party without accessing the attributes in the clear. This enables new privacy-preserving applications of ABCs "in the cloud." This is achieved by carefully integrating proxy re-encryption with structure-preserving signatures and zero-knowledge proofs of knowledge. The user obtains credentials on his attributes (encrypted under his public key) and uploads them to the wallet, together with a specific re-encryption key. To prove a possession, the wallet re-encrypts the ciphertexts to the public key of the receiving third party and proves, in zero-knowledge, that all computations were done honestly. Thereby, the wallet never sees any user attribute in the clear. We show the practical efficiency of our scheme by giving concrete benchmarks of a prototype implementation.
Batch-verifiable Secret Sharing with Unconditional Privacy

With Stephan Krenn, and Thomas Lorünser.

International Conference on Information Systems Security and Privacy (ICISSP) 2017, Porto, Portugal, February 19-21.

Abstract URL PDF

We propose the first batch-verifiable secret sharing scheme with a significant security property, namely that of unconditional privacy. Verifiability and privacy of secret-shared messages are a crucial feature, e.g., in distributed computing scenarios, and verifiable secret sharing schemes with unconditional privacy (but without a batching feature) exist for a long time, e.g., Ben-Or, Goldwasser, and Wigderson (STOC 1988). Unfortunately, those schemes are able to verify only a single message at a time which, however, is not a very realistic scenario in a more practical setting. Namely, large files in real-world implementations are often split into many message blocks on a several-byte level and, thus, many known single-message verifiable secret sharing schemes tend to behave inefficiently in such a scenario. To improve practicability, batch-verifiable secret sharing was proposed by Bellare, Garay, and Rabin (ACM PODC 1996). In their scheme, the servers are able to verify a batch of m essages (instead of only one) at almost the same amortized efficiency costs in comparison to efficient existing verifiable secret sharing schemes that only deal with single messages. However, the Bellare-Garay-Rabin scheme does not consider the important security property of unconditional privacy. Unconditionally private schemes information-theoretically guarantee privacy even against computationally unbounded adversaries and, hence, can be seen to be private in a long-term sense. In this work, we lift the Bellare-Garay-Rabin scheme to the unconditional privacy setting in a rigorous manner while preserving the practicability of their scheme simultaneously.
Secure and Privacy-Friendly Storage and Data Processing in the Cloud

With Pasquale Chiaro, Simone Fischer-Hübner, Thomas Groß, Stephan Krenn, Thomas Lorünser, Ana Isabel Martı́nez Garcı́, Andrea Migliavacca, Kai Rannenberg, Daniel Slamanig, and Alberto Zanini.

IFIP Summer School 2016 - Privacy and Identity Management, Ispra, Italy, September 4-8.

Abstract URL PDF

At the IFIP Summer School 2017, the two H2020 projects credential and prismacloud co-organized a workshop dedicated to in- troducing the necessary background knowledge and demonstrating proto- types of privacy-preserving solutions for storing, sharing, and processing potentially sensitive data in untrusted cloud environments. This paper summarizes the given presentations and presents the discussions and feedback given by the workshop attendees, including students and se- nior researchers from different domains as well as relevant non-academic stakeholders such as public data protection agencies.

2016

Opportunities and Challenges of CREDENTIAL - Towards a Metadata-Privacy Respecting Identity Provider

With Farzaneh Karegar, Stephan Krenn, Felix Hörandner, Thomas Lorünser, and Simone Fischer-Hübner.

IFIP Summer School 2016 - Privacy and Identity Management, Karlstad, Sweden, August 21-26.

Abstract URL PDF

This paper summarizes the results of a workshop at the IFIP Summer School 2016 introducing the EU Horizon 2020 project CREDENTIAL, i.e., Secure Cloud Identity Wallet. The contribution of this document is three-fold. First, it gives an overview of the CREDENTIAL project, its use-cases, and core technologies. Second, it explains the challenges of the project’s approach and summarizes the results of the parallel focus groups. Third, it focuses on a specific challenge—the protection of metadata in centralized identity providers—and suggests a potential architecture addressing this problem.

2015

On Cryptographic Building Blocks and Transformations

PhD thesis, Karlsruhe Institute of Technology, Karlsruhe, Germany, June 26, 2015.

Abstract URL PDF

Cryptographic building blocks play a central role in cryptography, e.g., encryption or digital signatures with their security notions. Further, cryptographic building blocks might be constructed modularly, i.e., emerge out of other cryptographic building blocks. Essentially, one cryptographically transforms the underlying block(s) and their (security) properties into the emerged block and its properties. This thesis considers cryptographic building blocks and new cryptographic transformations.
Confined Guessing: New Signatures From Standard Assumptions

With Florian Böhl, Dennis Hofheinz, Tibor Jager, and Jessica Koch.

Journal of Cryptology, Volume 28, 2015.

Abstract URL PDF ePrint

We put forward a new technique to construct very efficient and compact signature schemes. Our technique combines several instances of only a mildly secure signature scheme to obtain a fully secure scheme. Since the mild security notion we require is much easier to achieve than full security, we can combine our strategy with existing techniques to obtain a number of interesting new (stateless and fully secure) signature schemes. Concretely, we get (1) A scheme based on the computational Diffie–Hellman (CDH) assumption in pairing-friendly groups. Signatures contain O(1) and verification keys O(logk) group elements, where k is the security parameter. Our scheme is the first fully secure CDH-based scheme with such compact verification keys. (2) A scheme based on the (nonstrong) RSA assumption in which both signatures and verification keys contain O(1) group elements. Our scheme is significantly more efficient than existing RSA-based schemes. (3) A scheme based on the Short Integer Solutions (SIS) assumption. Signatures contain O(log(k)*m) and verification keys O(n*m) Zp-elements, where p may be polynomial in k, and n, m denote the usual SIS matrix dimensions. Compared to state-of-the-art SIS-based schemes, this gives very small verification keys, at the price of slightly larger signatures. In all cases, the involved constants are small, and the arising schemes provide significant improvements upon state-of-the-art schemes. The only price we pay is a rather large (polynomial) loss in the security reduction. However, this loss can be significantly reduced at the cost of an additive term in signature and verification key size.
Identity-Based Encryption with (Almost) Tight Security in the Multi-instance, Multi-ciphertext Setting

With Dennis Hofheinz, and Jessica Koch.

PKC 2015, Gaithersburg, MD, USA, March 30 - April 1. (Invited to the Journal of Cryptology.)

Abstract URL PDF ePrint

We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (Crypto 2013). The security loss of our reduction is O(k)(where k is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to "lift" their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.

2014

A Generic View on Trace-and-Revoke Broadcast Encryption Schemes

With Dennis Hofheinz.

CT-RSA 2014 - The Cryptographer’s Track at the RSA Conference 2014, San Francisco, USA, February 25-28.

Abstract URL PDF ePrint

At Eurocrypt 2011, Wee presented a generalization of threshold public key encryption, threshold signatures, and revocation schemes arising from threshold extractable hash proof systems. In particular, he gave instances of his generic revocation scheme from the DDH assumption (which led to the Naor-Pinkas revocation scheme), and from the factoring assumption (which led to a new revocation scheme). We expand on Wee’s work in two directions: (a) We propose threshold extractable hash proof instantiations from the “Extended Decisional Diffie-Hellman” (EDDH) assumption due to Hemenway and Ostrovsky (PKC 2012). This in particular yields EDDH-based variants of threshold public key encryption, threshold signatures, and revocation schemes. In detail, this yields a DCR-based revocation scheme. (b) We show that our EDDH-based revocation scheme allows for a mild form of traitor tracing (and, thus, yields a new trace-and-revoke scheme). In particular, compared to Wee’s factoring-based scheme, our DCR-based scheme has the advantage that it allows to trace traitors.

2013

Programmable Hash Functions in the Multilinear Setting

With Eduarda S. V. Freire, Dennis Hofheinz, and Kenneth G. Paterson.

CRYPTO 2013, Santa Barbara, USA, August 18-22.

Abstract URL PDF ePrint

We adapt the concept of a programmable hash function (PHF, Crypto 2008) to a setting in which a multilinear map is available. This enables new PHFs with previously unachieved parameters. To demonstrate their usefulness, we show how our (standard-model) PHFs can replace random oracles in several well-known cryptographic constructions. Namely, we obtain standard-model versions of the Boneh-Franklin identity-based encryption scheme, the Boneh-Lynn-Shacham signature scheme, and the Sakai-Ohgishi-Kasahara identity-based non- interactive key exchange (ID-NIKE) scheme. The ID-NIKE scheme is the first scheme of its kind in the standard model. Our abstraction also allows to derive hierarchical versions of the above schemes in settings with multilinear maps. This in particular yields simple and efficient hierarchical generalizations of the BF, BLS, and SOK schemes. In the case of hierarchical ID-NIKE, ours is the first such scheme with full security, in either the random oracle model or the standard model. While our constructions are formulated with respect to a generic multilinear map, we also outline the necessary adaptations required for the recent “noisy” multilinear map candidate due to Garg, Gentry, and Halevi.
Practical Signatures from Standard Assumptions

With Florian Böhl, Dennis Hofheinz, Tibor Jager, Jessica Koch, and Jae Hong Seo.

EUROCRYPT 2013, Athens, Greece, May 26-30.

Abstract URL PDF ePrint

We put forward new techniques for designing signature schemes. As a result, we present practical signature schemes based on the CDH, the RSA, and the SIS assumptions. Our schemes compare favorably with existing schemes based on these assumptions. Our core idea is the use of tag-based signatures. Concretely, each signatures contains a tag which is uniformly chosen from a suitable tag set. Intuitively, the tag provides a way to embed instances of computational problems. Indeed, carefully choosing these tag spaces provides new ways to partition the set of possible message-tag pairs into "signable" and "unsignable" pairs. In our security proof, we will thus be able to sign all adversarially requested messages, and at the same time use an adversarially generated forgery with suitably large probability.