Electronic identities (eIDs) are crucial in an increasingly digitalized environment. Pseudonyms, as offered by Austria's governmental sector-specific personal identifiers (bPks), can significantly improve privacy by ensuring that personal data is not universally traceable across public services and private companies. However, the current architecture comes with several challenges regarding availability, privacy, and authenticity, due to a fully centralized design. This paper proposes bPk#, a distributed architecture to address these issues, reducing reliance on the central authority, while still providing all functional requirements to the existing bPk system. In particular, users are delegated the rights to compute their own pseudonyms, thereby minimizing metadata revealed to the central authority, while (subsets of) service providers may receive the right to compute pseudonyms only within their own domain, thereby reducing the availability needs of the central authority. To the best of our knowledge, we provide the first formal framework for such delegatable pseudonym systems, together with a generic construction for which we provide formal security proofs. Furthermore, we propose a concrete instantiation of our construction, together with a reference implementation demonstrating the practical efficiency.

Oblivious Pseudorandom Functions (OPRFs) are an elementary building block in cryptographic and privacy-preserving applications. While there are numerous pre-quantum secure OPRF constructions, it is unclear which of the proposed options for post-quantum secure constructions are practical for modern-day applications. In this work, we focus on isogeny group actions, as the associated low bandwidth leads to efficient constructions. We introduce OPUS, a novel Naor-Reingold-based OPRF from isogenies without oblivious transfer, and show efficient evaluations of the Naor-Reingold PRF using CSIDH and CSI-FiSh. Additionally, we analyze a previous proposal of a CSIDH-based OPRF and that the straightforward instantiation of the protocol leaks the server's private key. As a result, we propose mitigations to address those shortcomings, which require additional hardness assumptions. Our results report a very competitive protocol when combined with lattices for Oblivious Transfer.

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

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.

With recent advances on the capabilities of quantum computers and the seminal work by Shor on the prime factorization of integers with quantum algorithms, the threat of quantum computers is looming over public-key based cryptographic systems. Two distinct areas of research – post-quantum and quantum cryptography – provide the technical means to secure cryptographic systems against potentially powerful enough quantum computers. As both technologies are now becoming readily available, integration in a wide range of applications to understand their characteristics and trade-offs and the associated evaluation is of importance.

The Key Management System (KMS) is an important component in scaling up from link-to-link key generation to large key distribution networks. In this work we provide an overview of a KMS in the context of Quantum Key Distribution Networks (QKDN) and give a thorough summary of the functionality of a KMS in such an application. Beyond classical QKDNs, we discuss Post Quantum Cryptography (PQC) hybridization techniques at the KMS level. These methods add an additional layer of security against quantum computer driven attacks. We also discuss selected topics regarding the development, deployment and operation of components for such security infrastructure. In addition, relevant standards in the realm of Quantum Key Distribution (QKD) are outlined and analyzed. As some of the necessary interfaces have not been standardized, namely the interface between two KMS instances and the interface between the KMS and the Software Defined Network (SDN) Agent, we propose APIs for these two cases. The design of the interface between the KMS and QKD modules is discussed and, considering their resource constraints, a push mode for the ETSI GS QKD 004 standard is proposed. Finally, implementation details of a prototype KMS are outlined and trade-offs are discussed.

Authentication, authorization, and trust verification are central parts of an access control system. The conditions for granting access in such a system are collected in access policies. Since access conditions are often complex, dedicated languages – policy languages – for defining policies are in use.However, current policy languages are unable to express such conditions having privacy of users in mind. With privacy-preserving technologies, users are enabled to prove information to the access system without revealing it.In this work, we present a generic design for supporting privacy-preserving technologies in policy languages. Our design prevents unnecessary disclosure of sensitive information while still allowing the formulation of expressive rules for access control. For that we make use of zero-knowledge proofs (NIZKs). We demonstrate our design by applying it to the TPL policy language, while using SNARKs. Also, we evaluate the resulting ZK-TPL language and its associated toolchain. Our evaluation shows that for regular-sized credentials communication and verification overhead is negligible.

Digital identities play a vital role in an increasingly digital world. These identities often rely on central authorities to issue and manage them. Central authorities have the drawback of being a central trusted party, representing a bottleneck and single point of failure with exclusive control of identity-related data. Self-sovereign identity (SSI) tackles those problems by utilizing distributed ledger technology and making users the sovereign owners of their identity data. Nevertheless, SSI, as recent technology, still lacks qualified identity data. This is especially a problem since sensitive services like eGovernment or banking services require identity data issued by a qualified identity provider; thus, SSI - based identities cannot be used for these services. In this paper, we propose a concept for deriving identity data from an existing identity system into an SSI in a fully privacy-preserving way by additionally supporting offline verification. This way, we enable a chain of trust from the existing identity system to the SSI system by introducing a novel trust model. Our concept utilizes novel cryptographic primitives to support efficient and privacy-preserving identity showing as well as revo-cation. To underline the feasibility of our concept, we implement a proof system and benchmark the related use cases.

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.

Public key infrastructure (PKI) based on certificate authorities is one of the cornerstones of secure communication over the internet. Certificates issued as part of this PKI provide authentication of web servers among others. Yet, the PKI ecosystem is susceptible to certificate misissuance and misuse attacks. To prevent those attacks, Certificate Transparency (CT) facilitates auditing of issued certificates and detecting certificates issued without authorization. Users that want to verify inclusion of certificates on CT log servers contact the CT server directly to retrieve inclusion proofs. This direct contact with the log server creates a privacy problem since the users' browsing activities could be recorded by the log server owner. Lueks and Goldberg (FC 2015) suggested the use of Private Information Retrieval (PIR) in order to protect the users' privacy in the CT ecosystem. With the immense amount of certificates included on CT log servers, their approach runs into performance issues, however. Nevertheless, we build on this approach and extend it using multi-tier Merkle trees, and render it practical using multi-server PIR protocols based on distributed point functions (DPFs). Our approach leads to a scalable design suitable to handle the increasing number of certificates and is, in addition, generic allowing instantiations using secure accumulators and PIRs. We implement and test this mechanism for privacy-preserving membership proof retrieval and show that it can be integrated without disrupting existing CT infrastructure. Most importantly, even for larger CT log sizes of 2^31 certificates, the performance overhead is less than 9 milliseconds in total.

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.