2026 [ to top ]

1.
Cremers, C., Günsay, E., Wesselkamp, V., Zhao, M.: ETK: External-Operations TreeKEM and the Security of MLS in RFC 9420. to appear at IACR Eurocrypt (2026).
[ Abstract ] [ Download ]
 
The Messaging Layer Security protocol MLS is standardized in IETF’s RFC 9420 and allows a group of parties to securely establish and evolve group keys even if the servers are malicious. The core design of MLS is based on the TreeKEM protocol, which was significantly modified and extended during the standard’s development. Over the last years, several partial security analyses have appeared of incomplete drafts of the standard. One of the major additions to MLS RFC 9420 (the final version of the standard) are the external operations, i.e., external commits and proposals. These additional operations have not been considered in any previous security analysis, while they can have a significant impact on the standard’s security. In this work, we prove the consistency, confidentiality and authentication of MLS in RFC 9420. To this end, we formalize ETK: External-Operations TreeKEM, which models RFC 9420 and includes the external commits and proposals. We propose a corresponding ideal functionality FECGKA and prove that ETK realizes it. Our work is the first cryptographic analysis that considers both the final changes to the standard, and the first approach overall to cover external proposals and external commits. Compared to previous works that considered MLS drafts, our ETK protocol is by far the closest to the final MLS RFC 9420 standard. Our analysis implies that the core of MLS in RFC 9420 is an ETK protocol that realizes FECGKA. Notably, we show that when external proposals and commits are allowed, MLS achieves a weaker form of security than was suggested by previous analyses, because the external operations can be exploited to violate Post-Compromise Security guarantees. We show that the security of the protocol can be further strengthened by leveraging the standard’s optional PSK mechanism, allowing another form of healing, and give a corresponding construction ETKPSK and ideal functionality FECGKAPSK .

2.
Lehmann, A., Özbay, C.: Putting Multi into Multi-Signatures: Tight Security for Multiple Signers. to appear at IACR Eurocrypt. (2026).
[ Abstract ] [ Download ]
 
Multi-signatures enable multiple parties to create a joint signature on the same message. Such schemes aggregate several individual signatures and public keys into a short signature and aggregated public key, and verification is performed on these combined values. Interestingly, all existing notions of unforgeability for multi-signatures are designed with a single honest user in mind, overlooking the multi-user setting that multi-signatures are built for. While multi-user security can be bootstrapped from any single-user secure scheme, the straightforward adoption implies a security loss that is linear in the number of signers n. In this work we therefore start the investigation of multi-signatures with tight multi-user security. We show that none of the existing multi-signatures with tight single-user security seems amendable to the multi-user setting, as all their proofs and design choices exploit the fact that there is only a single honest user. Based on this insight, we then propose two new constructions built from scratch with multi-user security in mind: Skewer-NI, a non-interactive and pairing-based scheme, and Skewer-PF, a pairing-free and two-round construction. We prove both schemes tightly secure under the DDH assumption in the ROM. Both schemes also improve the state-of-the-art in another aspect: they support the feature of key aggregation. Skewer-NI is the first non-interactive tightly secure multi-signature with this feature. In the pairing-free two-round setting, Skewer-PF is the first to combine tight multi-user security with key aggregation where the only prior result, due to Bacho and Wagner (CRYPTO’25), achieved aggregation but only in the single-user case.

3.
Friedrichs, K., Harding, F., Lehmann, A., Lysyanskaya, A.: Device-Bound Anonymous Credentials With(out) Trusted Hardware. to appear at IACR Eurocrypt. (2026).
[ Abstract ] [ Download ]
 
Anonymous credentials enable unlinkable and privacy-preserving user authentication. To ensure non-transferability of credentials among corrupt users, they can additionally be device-bound. Therein, a credential is tied to a key protected by a secure element (SE), usually a hardware component, and any presentation of the credential requires a fresh contribution of the SE. Interestingly, despite being a fundamental aspect of user credentials, device binding for anonymous credentials is relatively unstudied. Existing constructions either require multiple calls to the SE, or need the SE to keep a credential-specific state -- violating core design principles of shielded SEs. Further, constructions that are compatible with the most mature credential scheme BBS rely on the honesty of the SE for privacy, which is hard to vet given that SEs are black-box components. In this work, we thoroughly study and solve the problem of device-bound anonymous credentials (DBACs). We model DBACs to ensure the unforgeability and non-transferability of credentials, and to guarantee user privacy at the same time. Our definitions cover a range of SE trust levels, including the case of a subverted or fully corrupted SE. We also define blind DBACs, in which the SE learns nothing about the credential presentations it helped compute. This targets the design of a remote, cloud-based SE which is a deployment model considered for the EU Digital Identity (EUDI) wallet to address the fact that most user phones are not equipped with a sufficiently secure SE. Finally, we present three simple and round-optimal constructions for device binding of BBS credentials, and prove their security in the AGM+ROM and privacy unconditionally. The SE therein is extremely lightweight: it only has to compute a BLS or Schnorr signature in a single call. We also give the BLS-based construction in a blind variant, yielding the first protocol that enables privacy-preserving device binding for anonymous credentials when being used with a remote SE.

4.
Lehmann, A., Mouchet, C., Sidorenko, A.: Multi-Party Private Join. to appear at 26th Privacy Enhancing Technologies Symposium (PETS) (2026).
[ Abstract ] [ Download ]
 
A multi-party private join (MPPJ) protocol enables multiple source parties to provide a receiver party with the inner joins over their respective datasets, while revealing as little information as possible. There is currently no protocol that directly and efficiently enables such a MPPJ beyond the two- or three-party setting. The presently known protocols either achieve weaker functionality (e.g., multiparty private set intersection protocols) or more general ones (e.g., private-join-compute and generic secure multi-party computation protocols) and are therefore more costly to run for the sources. This work formally introduces MPPJ as an explicit goal, and proposes an efficient, helper-assisted protocol that achieves n-party inner joins with small leakage and close-to-optimal overhead for the sources. Specifically, for n databases with m rows, it requires only a single O(m) upload from the sources to the helper, and a single O(n*m) download from the helper to the receiver. Moreover, the helper is entirely oblivious: it enables the efficiency and simplicity goals we are striving for, but it does not learn anything about the computation it facilitates. We formally model and prove the security of our protocol from standard assumptions, in the passive-adversary model. Then, we provide an open-source implementation and an extensive performance evaluation. According to our experiments, our protocol requires 1.02 to 20 times less communication than a current private-join-compute protocol (with no computation over the join) for 2 to 6 parties and input database sizes from 1.5K to 250K records. Finally, we demonstrate the versatility of our approach by extending our protocol to threshold-joins.

2025 [ to top ]

1.
Friedrichs, K., Lehmann, A., Özbay, C.: Game Changer: A Modular Framework for OPRF Security. IACR Asiacrypt. pp. 582–613 (2025).
[ Abstract ] [ Download ]
 
Oblivious pseudorandom functions (OPRFs) allow the blind evaluation of a pseudorandom function, which makes them a versatile building block that enjoys usage in numerous applications. So far, security of OPRFs is predominantly captured in the Universal Composability (UC) framework, where an ideal functionality covers the expected security and privacy properties. While the OPRF functionality appears intuitive at first, the ideal-world paradigm also comes with a number of challenges: from imposing idealized building blocks when building OPRFs, to the lack of modularity, and requiring intricate UC knowledge to securely maneuver their usage. Game-based definitions are a simpler way to cover security properties. They model each property in a single game, which grants modularity in formalizing, proving, and using OPRFs. Interestingly, the few game-based works on OPRFs each re-invent the security model, with considerable variation. Thus, the advantages of the game-based approach remain out of reach: definitions are not easily accessible and comparability across works is low. In this work, we therefore systematize all existing notions into a clear, hierarchical framework. We unify or separate properties, making hidden relations explicit. This effort reveals the necessity of two novel properties: an intermediate privacy notion and a stronger unpredictability notion. Finally, we analyze the two most prominent constructions in our framework: HashDH and 2HashDH. The former does not achieve UC security, but has advantages in applications that require key rotation or updatability; yet it lacks a security analysis. We show that it achieves most security properties in our framework. We also observe that HashDH and 2HashDH do not satisfy our strongest privacy notion, indicating that the guarantees by the UC functionality are not as well understood as we might expect them to be. Overall, we hope that our framework facilitates the usage and design of OPRFs.

2.
Bormann, C., Lehmann, A.: SoK: Anonymous Credentials for Digital Identity Wallets. Security Standardisation Research (SSR) 2025. (2025).
[ Abstract ] [ Download ]
 
Digital identity wallets are currently developed around the globe, aiming to provide user-centric and secure authentication. Realizing this in a privacy-preserving manner is paramount, and even mandated in Europe which is developing the European Digital Identity Wallet with planned release in 2026. Current proposals to build these wallets are based on classic signature schemes such as ECDSA, but would benefit greatly from the use of anonymous credentials. Thus, there is currently a strong interest in developing the necessary standards to bring these cryptographic concepts into the real world. This work aims to inform ongoing standardization efforts by providing an overview of the most prominent solutions, and the remaining open challenges. We split our overview among two fundamental architectural approaches: (1) dedicated multi-message signature schemes that allow for efficient ZKPs, and (2) general purpose ZKPs used on top of legacy ECDSA. We also provide a comprehensive summary of the broad feature set that anonymous credentials can provide for identity wallets, in order to demonstrate that upgrading to these systems is a worthwhile endeavor and help to design standards that can leverage the rich existing body of work.

3.
Lehmann, A., Sidorenko, A., Zacharakis, A.: Vision: A Modular Framework for Anonymous Credential System. Security Standardisation Research (SSR) 2025. (2025).
[ Abstract ] [ Download ]
 
Anonymous credentials enable the unlinkable presentation of previously attested information, or even only predicates thereof. They are a versatile tool and currently enjoy attention in various real-world applications, ranging from the European Digital Identity project to Privacy Pass. While each application usually requires their own tailored variant of anonymous credentials, they all share the same common blueprint. So far, this has not been leveraged though, and currently several proposals either targeting monolithic variants of core components such as BBS signatures, or application-specific protocols undergo standardization. This is clearly not optimal, as the same work gets repeated multiple times, while still risking ending up with many slight modifications of the same main idea and protocols. In this work we present our vision to use a modular approach to build anonymous credential systems: they are built from a core component – consisting of a commitment, signature and NIZK scheme – that can be extended with additional commitment-based modules in a plug-and-play manner. We sketch modules for pseudonyms, range proofs and device binding. Importantly, apart from the committed input, all modules are entirely independent of each other. We use this modularity to propose a concrete instantiation that uses BBS signatures for the core component and ECDSA signatures for device binding, addressing the need to bind modern credential schemes to legacy signatures in secure hardware elements.

4.
Hanff, K., Lehmann, A., Özbay, C.: Security Analysis of Privately Verifiable Privacy Pass. ACM CCS 2025. pp. 2922–2936 (2025).
[ Abstract ] [ Download ]
 
Privacy Pass is an anonymous authentication protocol which was initially designed by Davidson et al. (PETS’18) to reduce the number of CAPTCHAs that TOR users must solve. It issues single-use authentication tokens with anonymous and unlinkable redemption guarantees. The issuer and verifier of the protocol share a symmetric key, and tokens are privately verifiable. The protocol has sparked interest from both academia and industry, which led to an Internet Engineering Task Force (IETF) standard. While Davidson et al. formally analyzed the original protocol, the IETF standard introduces several changes to their protocol. Thus, the standardized version’s formal security remains unexamined. We fill this gap by analyzing the IETF standard’s privately verifiable Privacy Pass protocol. In particular, there are two main discrepancies between the analyzed and standardized version: First, the IETF version introduces a redemption context, that can be used for blindly embedding a validity period into the Privacy Pass tokens. We show that this variant has significant differences to public metadata extension that has been proposed for the same purpose in the literature. Redemption context offers better privacy and security than public metadata. We capture both stronger guarantees through game-based security definitions and show that the currently considered one-more unforgeability notion for Privacy Pass is insufficient when a redemption context is used. Thus, we propose a new property, targeted context unforgeability, and prove its incomparability to one-more unforgeability. Second, Davidson et al. focused on a concrete Diffie-Hellman based construction, whereas the IETF version is built generically from a verifiable oblivious pseudorandom function (VOPRF). Further, the analyzed protocol omitted the full redemption phase needed to prevent double-spending. We prove that the generic IETF construction satisfies the desired security and privacy guarantees covering the full life-cycle of tokens. Our analysis relies on natural security properties of VOPRFs, providing compatibility with any secure VOPRF instantiation. This enables crypto agility, e.g., allowing to switch to efficient quantum-safe VOPRFs when they become available.

5.
Dayanikli, D., Lehmann, A.: Updatable aPAKE: Security Against Bulk Precomputation Attacks. ACM CCS 2025. pp. 1158–1172 (2025).
[ Abstract ] [ Download ]
 
Asymmetric Password-Authenticated Key Exchange (aPAKE) enables secure key establishment between a client and a server using a pre-shared password, while providing security against offline attacks. However, aPAKE does not guarantee any precomputation resistance, and considers passwords to become immediately available upon server compromise. A recent work by Dayanikli and Lehmann (EuroS&P'24) observed that many existing aPAKE protocols provide stronger precomputation attack resistance than what is guaranteed through the aPAKE model: they often rely on salted password hashes, where a unique salt makes precomputation attacks more difficult. While these salts are sent in clear to the client during authentication, and thus trivial to obtain for an attacker, this makes a difference in multi-user settings with millions of user accounts per server. In order to run bulk precomputation attacks on all users' passwords, the attacker needs to start an authentication session on behalf of every user to obtain their salts. However, this protection is still limited as salts are static, and the attacker can gradually extract all salt values for precomputation attacks. In this work, we build upon the observation that many aPAKE protocols include salts for their password protection, and propose a new aPAKE variant that makes such bulk precomputation attacks practically infeasible. We propose updatable aPAKE which employs updatable salts. In updatable aPAKE, the salt is implicitly refreshed with each successful user authentication, forcing an attacker to rebuild their precomputation table after every honest user's login -- offering a level of precomputation resistance similar to that of strong aPAKE protocols. We formalize the security of updatable aPAKE in the Universal Composability framework and show how OKAPE-HMQV, the currently most efficient aPAKE protocol, can be lifted to the updatable aPAKE setting in a provably secure way. The core idea is that this salt update can be integrated through relying on the password-based server-side authentication, that is already guaranteed through aPAKE. We also observe that OKAPE-HMQV is very similar to SRP-6a, the currently most widely deployed aPAKE protocol, and explain how the same idea can be used to upgrade this legacy protocol to achieve strong bulk precomputation attack resistance with minimal overhead.

6.
Dayanikli, D., Holz, L., Lehmann, A.: Virtual End-to-End Encryption: Analysis of the Doctolib Protocol. 20th ACM AsiaCCS. pp. 773–789 (2025).
[ Abstract ] [ Download ]
 
Doctolib is a popular healthcare platform, used by over 90 million users across France, Italy, and Germany. One of its main features is the secure data exchange between patients and doctors, with 7 million documents shared per month. Doctolib claims to provide the "world’s first end-to-end encryption platform built for health applications". The encryption protocol, described in a Whitepaper and Github repository, relies on envelope encryption and lets users upload ciphertexts for the secure data exchange. The ciphertexts are stored and retrieved through a distributed system, consisting of a data server and a key server. To access the data, recipients fetch the ciphertexts and decrypt them with their private key. However, the platform does not require end-users to maintain any cryptographic keys themselves and instead relies on a virtual device that leverages the two-server setting. The virtual device splits the user’s private key over both servers, and uses password-based authentication for its retrieval. Overall, the goal of the protocol is to ensure confidentiality of the uploaded medical records as long as at most one server is corrupt. In this work, we analyze the security of Doctolib’s distributed encryption protocol. First, we define a set of formal security models for such password-based distributed envelope encryption, that capture the optimal security properties under different corruption settings. We then analyze the protocol – abstracted from the available information – in our model, and show that it does not achieve the desired security guarantees.We finally propose a simple modification that strengthens the original protocol through the use of a distributed oblivious pseudorandom function that provably achieves all our security properties.

7.
Bossuat, J.-P., Costache, A., Mouchet, C., Nürnberger, L., Troncoso-Pastoriza, J.R.: Accurate and Composable Noise Estimates for CKKS with Application to Exact HE Computation. IACR Communications in Cryptology. 2, 1–49 (2025).
[ Abstract ] [ Download ]
 
All RLWE-based FHE schemes are inherently noisy. The CKKS scheme (Cheon, Kim, Kim, Song, Asiacrypt 2017) considers the noise as a part of the message, yielding approximate computations but also considerable performance gains. Since it grows with each homomorphic operation and incurs a precision loss, it is paramount for users to be able to estimate the noise level throughout a given circuit in order to appropriately estimate parameters and control the precision loss in the message. In this work, we develop a noise model that allows for tight estimates of the precision loss, and propose a tool prototype for computing these estimates on any given circuit. Our noise model relies on a novel definition, the component-wise noise, which makes the average-case noise estimates tighter and more composable. As a result, our model and tool can derive accurate estimates of complex circuits such as bootstrapping. We experimentally demonstrate the tightness of our noise estimates by showing that our theoretical estimates never deviate by more than 0.01 bits from experimental estimates, even for large circuits, and hold with high probability. Furthermore, we demonstrate how to apply our techniques to obtain an exact version of the CKKS scheme in which the decryption removes all the noise (with high probability). Such a scheme has many applications, as it allows to take advantage of the efficiency of CKKS, while preserving an exact message space, hence further strengthening CKKS against IND-CPA-D attacks.

8.
Kroschewski, M., Lehmann, A., Özbay, C.: OPPID: Single Sign-On with Oblivious Pairwise Pseudonyms. Privacy Enhancing Technologies Symposium (PETS) 2025. pp. 629–649 (2025).
[ Abstract ] [ Download ]
 
Single Sign-On (SSO) allows users to conveniently authenticate to many Relying Parties (RPs) through a central Identity Provider (IdP). SSO supports unlinkable authentication towards the RPs via pairwise pseudonyms, where the IdP assigns the user an RP-specific pseudonym. This feature has been rolled out prominently within Apple's SSO service. While establishing unlinkable identities provides privacy towards RPs, it actually emphasizes the main privacy problem of SSO: with every authentication request, the IdP learns the RP that the user wants to access. Solutions to overcome this limitation exist, but either assume users to behave honestly or require them to manage long-term cryptographic keys. In this work, we propose the first SSO system that can provide such pseudonymous authentication in an unobservable yet strongly secure and convenient manner. That is, the IdP blindly derives the user's pairwise pseudonym for the targeted RP without learning the RP's identity and without requiring key material handled by the user. We formally define the desired security and privacy properties for such unlinkable, unobservable, and strongly secure SSO. In particular, our model includes the often neglected RP authentication: the IdP typically wants to limit its services to registered RPs only and thus must be able to (blindly) verify that it issues the token and pseudonym to such a registered RP. We propose a simple construction that combines signatures with efficient proofs-of-knowledge with a blind, yet verifiable, evaluation of the Hashed-Diffie-Hellman PRF. We prove the security of our construction and demonstrate its efficiency through a prototypical implementation, which requires a running time of 2-20ms per involved party.

9.
Lehmann, A., Nazarian, P., Özbay, C.: Stronger Security for Threshold Blind Signatures. 44th IACR Eurocrypt 2025. pp. 335–364 (2025).
[ Abstract ] [ Download ]
 
Blind signatures allow a user to obtain a signature from an issuer in a privacy-preserving way: the issuer neither learns the signed message, nor can link the signature to its issuance. The threshold version of blind signatures further splits the secret key among n issuers, and requires the user to obtain at least t ≤ n of signature shares in order to derive the final signature. Security should then hold as long as at most t − 1 issuers are corrupt. Security for blind signatures is expressed through the notion of one-more unforgeability and demands that an adversary must not be able to produce more signatures than what is considered trivial after its interactions with the honest issuer(s). While one-more unforgeability is well understood for the single-issuer setting, the situation is much less clear in the threshold case: due to the blind issuance, counting which interactions can yield a trivial signature is a challenging task. Existing works bypass that challenge by using simplified models that do not fully capture the expectations of the threshold setting. In this work, we study the security of threshold blind signatures, and propose a framework of one-more unforgeability notions where the adversary can corrupt c < t issuers. Our model is generic enough to capture both interactive and non-interactive protocols, and it provides a set of natural properties with increasingly stronger guarantees, giving the issuers gradually more control over how their shares can be combined. As a point of comparison, we reconsider the existing threshold blind signature models and show that their security guarantees are weaker and less clearly comprehensible than they seem. We then re-assess the security of existing threshold blind signature schemes – BLS-based and Snowblind – in our framework, and show how to lift them to provide stronger security.

10.
Abou Haidar, C., Das, D., Lehmann, A., Özbay, C., Perez Kempner, O.: Privacy-Preserving Multi-Signatures: Generic Techniques and Constructions Without Pairings. 28th IACR Public-Key Cryptography (PKC). pp. 66–98 (2025).
[ Abstract ] [ Download ]
 
Multi-signatures allow a set of parties to produce a single signature for a common message by combining their individual signatures. The result can be verified using the aggregated public key that represents the group of signers. Very recent work by Lehmann and Özbay (PKC '24) studied the use of multi-signatures for ad-hoc privacy-preserving group signing, formalizing the notion of multi-signatures with probabilistic yet verifiable key aggregation. Moreover, they proposed new BLS-type multi-signatures, allowing users holding a long-term key pair to engage with different groups, without the aggregated key leaking anything about the corresponding group. This enables key-reuse across different groups in a privacy-preserving way. Unfortunately, their technique cannot be applied to Schnorr-type multi-signatures, preventing state-of-the-art multi-signatures to benefit from those privacy features. In this work, we revisit the privacy framework from Lehmann and Özbay. Our first contribution is a generic lift that adds privacy to any multi-signature with deterministic key aggregation. As our second contribution, we study two concrete multi-signatures, and give dedicated transforms that take advantage of the underlying structures for improved efficiency. The first one is a slight modification of the popular MuSig2 scheme, achieving the strongest privacy property for free compared to the original scheme. The second is a variant of the lattice-based multi-signature scheme DualMS, making our construction the first post-quantum secure multi-signature for ad-hoc privacy-preserving group signing. The light overhead incurred by the modifications in our DualMS variant still allow us to benefit from the competitiveness of the original scheme.

11.
Lehmann, A., Özbay, C.: Commit-and-Prove System for Vectors and Applications to Threshold Signing. 28th IACR Public-Key Cryptography (PKC). pp. 200–232 (2025).
[ Abstract ] [ Download ]
 
Multi-signatures allow to combine several individual signatures into a compact one and verify it against a short aggregated key. Compared to threshold signatures, multi-signatures enjoy non-interactive key generation but give up on the threshold-setting. Recent works by Das et al. (CCS'23) and Garg et al. (S&P'24) show how multi-signatures can be turned into schemes that enable efficient verification when an ad hoc threshold -- determined only at verification -- is satisfied. This allows to keep the simple key generation of multi-signatures and support flexible threshold settings in the signing process later on. Both works use the same idea of combining BLS multi-signatures with inner-product proofs over committed keys. Das et al. give a somewhat generic proof from both building blocks, which we show to be flawed, whereas Garg et al. give a direct proof for the combined construction in the algebraic group model. In this work, we identify the common blueprint used in both works and abstract the proof-based approach through the building block of a commit-and-prove system for vectors (CP). We formally define a flexible set of security properties for the CP system and show how it can be securely combined with a multi-signature to yield a signature with ad hoc thresholds. Our scheme also lifts the threshold signatures into the multiverse setting recently introduced by Baird et al. (S&P'23), which allows signers to re-use their long-term keys across several groups. The challenge in the generic construction is to express -- and realize -- the combination of homomorphic proofs and commitments (needed to realize flexible thresholds over fixed group keys) and their simulation extractability (needed in the threshold signature security proof). We finally show that a CP instantiation closely following the ideas of Das et al. can be proven secure, but requires a new flexible-base DL-assumption to do so.

12.
Bootle, J., Lyubashevsky, V., Merino-Gallardo, A.: Efficient Verifiable Mixnets from Lattices, Revisited. 28th IACR Public-Key Cryptography (PKC). pp. 237–270 (2025).
[ Abstract ] [ Download ]
 
Mixnets are powerful building blocks for providing anonymity in applications like electronic voting and anonymous messaging. The encryption schemes upon which traditional mixnets are built, as well as the zero-knowledge proofs used to provide verifiability, will, however, soon become insecure once a cryptographically-relevant quantum computer is built. In this work, we construct the most compact verifiable mixnet that achieves privacy and verifiability through encryption and zero-knowledge proofs based on the hardness of lattice problems, which are believed to be quantum-safe. A core component of verifiable mixnets is a proof of shuffle. The starting point for our construction is the proof of shuffle of Aranha et al. (CT-RSA 2021). We first identify an issue with the soundness proof in that work, which is also present in the adaptation of this proof in the mixnets of Aranha et al. (ACM CCS 2023) and Hough et al. (IACR CiC 2025). The issue is that one cannot directly adapt classical proofs of shuffle to the lattice setting due to the splitting structure of the rings used in lattice-based cryptography. This is not just an artifact of the proof, but a problem that manifests itself in practice, and we successfully mount an attack against the implementation of the first of the mixnets. We fix the problem and introduce a general approach for proving shuffles in splitting rings that can be of independent interest. The efficiency improvement of our mixnet over prior work is achieved by switching from re-encryption mixnets (as in the works of Aranha et al. and Hough et al.) to decryption mixnets with very efficient layering based on the hardness of the LWE and LWR problems over polynomial rings. The ciphertexts in our scheme are smaller by approximately a factor of 10X and 2X over the aforementioned instantiations, while the linear-size zero-knowledge proofs are smaller by a factor of 4X and 2X.

2024 [ to top ]

1.
Mouchet, C., Chatel, S., Nürnberger, L., Lueks, W.: Poster: Multiparty Private Set Intersection from Multiparty Homomorphic Encryption. ACM Conference on Computer and Communications Security (CCS). pp. 5003–5005 (2024).
[ Abstract ]
 
We revisit the problem of constructing protocols for multiparty private set intersection (MPSI) in light of the recent advances in multiparty homomorphic encryption (MHE). In MPSI, N larger than 2 parties jointly compute the intersection of their respective private set. Kissner and Song proposed an MHE-based MPSI scheme in 2005, but their approach was limited by the then-available HE schemes. Today, however, MHE schemes have become both more versatile and more efficient. As an early result, we implemented the MPSI approach of Kissner et al. with the recently proposed Helium framework (CCS 2024) for MHE-based MPC. We show that even this simple protocol can outperform the state-of-the-art implementation (in the passive-adversary setting) by Kolesnikov et al. (CCS 2017), both in terms of latency and communication cost.

2.
Mouchet, C., Chatel, S., Pyrgelis, A., Troncoso, C.: Helium: Scalable MPC among Lightweight Participants and under Churn. ACM Conference on Computer and Communications Security (CCS). pp. 3038–3052 (2024).
[ Abstract ] [ Download ]
 
We introduce Helium, a novel framework that supports scalable secure multiparty computation (MPC) for lightweight participants and tolerates churn. Helium relies on multiparty homomorphic encryption (MHE) as its core building block. While MHE schemes have been well studied in theory, prior works fall short of addressing critical considerations paramount for adoption such as supporting resource-constrained and unstably connected participants. In this work, we systematize the requirements of MHE-based MPC protocols from a practical lens, and we propose a novel execution mechanism that addresses those considerations. We implement this execution mechanism in Helium, which makes it the first implemented framework to support MPC under network churn based solely on cryptographic assumptions. We show that a Helium network of 30 parties connected with 100Mbits/s links and experiencing a system-wide churn rate of 40 failures per minute can compute the product between a fixed 512 × 512 secret matrix (e.g., a collectively-trained private model) and a fresh secret vector (e.g., a feature vector) 8.3 times per second. This is ∼1500 times faster than a state-of-the-art MPC framework operating under no churn.

3.
Faller, S., Handirk, T., Hesse, J., Horváth, M., Lehmann, A.: Password-Protected Key Retrieval with(out) HSM Protection. ACM Conference on Computer and Communications Security (CCS). pp. 2445–2459 (2024).
[ Abstract ] [ Download ]
 
Password-protected key retrieval (PPKR) enables users to store and retrieve high-entropy keys from a server securely. The process is bootstrapped from a human-memorizable password only, addressing the challenge of how end-users can manage cryptographic key material. The core security requirement is protection against a corrupt server, which should not be able to learn the key or offline- attack it through the password protection. PPKR is deployed at a large scale with the WhatsApp Backup Protocol (WBP), allowing users to access their encrypted messaging history when switching to a new device. Davies et al. (Crypto’23) formally analyzed the WBP, proving that it satisfies most of the desired security. The WBP uses the OPAQUE protocol for password-based key exchange as a building block and relies on the server using a hardware security module (HSM) for most of its protection. In fact, the security analysis assumes that the HSM is incorruptible – rendering most of the heavy cryptography in the WBP obsolete. In this work, we explore how provably secure and efficient PPKR can be built that either relies strongly on an HSM – but then takes full advantage of that – or requires less trust assumption for the price of more advanced cryptography. To this end, we expand the definitional work by Davies et al. to allow the analysis of PPKR with fine-grained HSM corruption, such as leakage of user records or attestation keys. For each scenario, we aim to give minimal PPKR solutions. For the strongest corruption setting, namely a fully corrupted HSM, we propose a protocol with a simpler design and better efficiency than the WBP. We also fix an attack related to client authentication that was identified by Davies et al.

4.
Daniluk, C.A., Nosyk, Y., Duda, A., Korczyński, M.: Zeros Are Heroes: NSEC3 Parameter Settings in the Wild. ACM Internet Measurement Conference (IMC). 415–422 (2024).
[ Abstract ] [ Download ]
 
Domain Name System Security Extensions (DNSSEC) enhanced the security of conventional DNS by providing data integrity and origin authentication, but enabled zone walking as a side effect. To address this issue, the Next Secure (NSEC3) resource record provides an authenticated denial of existence mechanism based on hashes of domain names. However, an improper selection of the NSEC3 parameters may significantly degrade the performance of resolvers and authoritative name servers alike. RFC 9276 (Guidance for NSEC3 Parameter Settings) imposes additional constraints on hash computation parameters, crucial in light of emerging security threats such as CPU resource exhaustion attacks. Despite this guideline, our analysis of over 302 M registered domain names reveals that 87.8 % of 15.5 % NSEC3-enabled domains fail to adhere to RFC 9276 with a dozen using 500 additional hash iterations. Furthermore, 78.3 % of 114 K open and closed validating resolvers impose the RFC's additional constraints on hash iterations with 18.4 % returning SERVFAIL, possibly rendering non-compliant domains unreachable.

5.
Dayanikli, D., Lehmann, A.: Provable Security Analysis of the Secure Remote Password Protocol. 37th IEEE Computer Security Foundations Symposium (CSF). pp. 393–408 (2024).
[ Abstract ] [ Download ]
 
This paper analyses the Secure Remote Password Protocol (SRP) in the context of provable security. SRP is an asymmetric Password-Authenticated Key Exchange (aPAKE) protocol introduced in 1998. It allows a client to establish a shared cryptographic key with a server based on a password of potentially low entropy. Although the protocol was part of several standardization efforts, and is deployed in numerous commercial applications such as Apple Homekit, 1Password or Telegram, it still lacks a formal proof of security. This is mainly due to some of the protocol's design choices which were implemented to circumvent patent issues. Our paper gives the first security analysis of SRP in the universal composability (UC) framework. We show that SRP is UC-secure against passive eavesdropping attacks under the standard CDH assumption in the random oracle model. We then highlight a major protocol change designed to thwart active attacks and propose a new assumption -- the additive Simultaneous Diffie Hellman (aSDH) assumption -- under which we can guarantee security in the presence of an active attacker. Using this new assumption as well as the Gap CDH assumption, we prove security of the SRP protocol against active attacks. Our proof is in the "Angel-based UC framework", a relaxation of the UC framework which gives all parties access to an oracle with super-polynomial power. In our proof, we assume that all parties have access to a DDH oracle (limited to finite fields). We further discuss the plausibility of this assumption and which level of security can be shown without it.

6.
Dayanikli, D., Lehmann, A.: (Strong) aPAKE Revisited: Capturing Multi-User Security and Salting. IEEE European Symposium on Security and Privacy (Euro&SP). pp. 415–439 (2024).
[ Abstract ] [ Download ]
 
Asymmetric Password-Authenticated Key Exchange (aPAKE) protocols, particularly Strong aPAKE (saPAKE) have enjoyed significant attention, both from academia and industry, with the well-known OPAQUE protocol currently undergoing standardization. In (s)aPAKE, a client and a server collaboratively establish a high-entropy key, relying on a previously exchanged password for authentication. A main feature is its resilience against offline and precomputation (for saPAKE) attacks. OPAQUE, as well as most other aPAKE protocols, have been designed and analyzed in a single-user setting, i.e., modelling that only a single user interacts with the server. By the composition framework of UC, security for the actual multi-user setting is then conjectured. As any real-world (s)aPAKE instantiation will need to cater multiple users, this introduces a dangerous gap in which developers are tasked to extend the single-user protocol securely and in a UC-compliant manner. In this work, we extend the (s)aPAKE definition to directly model the multi-user setting, and explicitly capture the impact that a server compromise has across user accounts. We show that the currently standardized multi-user version of OPAQUE might not provide the expected security, as it is insecure against offline attacks as soon as the file for one user in the system is compromised. This is due to using shared state among different users, which violates the UC composition framework. When extending the aPAKE security in the multi-client setting, we notice that the widely used security definition captures significantly weaker security guarantees than what is offered by many protocols. Essentially, the aPAKE definition assumes that the server stores emphunsalted password-hashes, whereas several protocols explicitly use a salt to protect against precomputation attacks. We therefore propose a definitional framework that captures different salting approaches -- thus showing that the security gap between aPAKE and saPAKE can be smaller than expected.

7.
Ackermann, E., Bober, K.-L., Jungnickel, V., Lehmann, A.: SEKA: Secretless Key Exchange and Authentication in LiFi Networks. IEEE European Symposium on Security and Privacy (Euro&SP). pp. 633–657 (2024).
[ Abstract ] [ Download ]
 
Light Fidelity (LiFi) networks transmit information via light waves and are an interesting alternative to Radio Frequency networks: as light can be confined easily, LiFi provides better performance and makes eavesdropping attacks much more difficult. A core application of LiFi networks is self-contained and local networks among a Group of autonomous devices, e.g., in industrial or medical environments. Cryptographic protocols are used to secure these networks, however the key exchange sometimes relies solely on the confineability of light signals and sends key material in plain over the network. This is clearly not desirable from a security perspective and newer standards recommend key exchange protocols to establish shared keys. A crucial part in any authenticated key exchange protocol is how to bootstrap trust, e.g., by assuming a PKI, pre-installed keys or an out-of-band-channel. Well established solutions exist, but they are not ideal for the type of self-contained networks targeted by LiFi communication. In this work we investigate how the physical properties of a LiFi channel can be used to replace these mechanisms, resulting in a more convenient and also more efficient solution for key exchange. To this end we propose a new type of secret-less key exchange (SEKA) that does not rely on any pre-shared secrets, and instead runs in two phases: a short bootstrap phase where we make stronger assumptions on the physical security, ruling out active attacks. This can be realized by putting all devices in a closed room, taking advantage of the light’s confineability feature. The bootstrap phase is followed by a more classical key-exchange phase, where the actual key material gets exchanged in the presence of active attacks – relying on the shared states from the bootstrap phase. We formally define this new type of key- exchange protocol which offers authenticated key exchange with post-compromise security without relying on pre-shared secrets. We then show that a simpler and more efficient version of the signed Diffie-Hellmann protocol, now relying on MACs instead of signatures for the mutual authentication, can be proven secure in our model. Finally, a proof-of-concept implementation of the SEKA protocol is evaluated in a testbed demonstrating the efficiency gains of our approach.

8.
Lehmann, A., Özbay, C.: Multi-Signatures for Ad-hoc and Privacy-Preserving Group Signing. 27th IACR Public-Key Cryptography (PKC). pp. 196–228 (2024).
[ Abstract ] [ Download ]
 
Multi-signatures allow to combine individual signatures from different signers on the same message into a short aggregated signature. Newer schemes further allow to aggregate the individual public keys, such that the combined signature gets verified against a short aggregated key. This makes them a versatile alternative to threshold or distributed signatures: the aggregated key can serve as group key, and signatures under that key can only be computed with the help of all signers. What makes multi-signatures even more attractive is their simple key management, as users can re-use the same secret key in several and ad-hoc formed groups. In that context, it will be desirable to not sacrifice privacy as soon as keys get re-used and ensure that users are not linkable across groups. In fact, when multi-signatures with key aggregation were proposed, it was claimed that aggregated keys hide the signers' identities or even the fact that it is a combined key at all. In our work, we show that none of the existing multi-signature schemes provide these privacy guarantees when keys get re-used in multiple groups. This is due to the fact that all known schemes deploy deterministic key aggregation. To overcome this limitation, we propose a new variant of multi-signatures with probabilistic yet verifiable key aggregation. We formally define the desirable privacy and unforgeability properties in the presence of key re-use. This also requires to adapt the unforgeability model to the group setting, and ensure that key-reuse does not weaken the expected guarantees. We present a simple BLS-based scheme that securely realizes our strong privacy and security guarantees. We also formalize and investigate the privacy that is possible by deterministic schemes, and prove that existing schemes provide the advertised privacy features as long as one public key remains secret.

2023 [ to top ]

1.
Kroschewski, M., Lehmann, A.: Save The Implicit Flow? Enabling Privacy-Preserving RP Authentication in OpenID Connect. Privacy Enhancing Technologies Symposium (PETS). pp. 96–116 (2023).
[ Abstract ] [ Download ]
 
OpenID Connect (OIDC) is a Single Sign-On (SSO) protocol that allows users to authenticate to various Relying Parties (RPs) via an Identity Provider (IdP). The main drawback of SSO is its lack of privacy, as the IdP learns the RP’s identity at each user’s login. OIDC supports several protocol flows, of which only one, the Implicit Flow, gives hope for any privacy, as it does not require direct communication between the IdP and RP. This design was initially intended for RPs with technical limitations that prevent them from storing credentials and thus authenticating to the IdP. However, RP authentication is crucial to ensure that users only access properly registered RPs. As a result, the Implicit Flow is being discussed to be excluded from the OAuth specification on which OIDC is based. This paper demonstrates a privacy-preserving approach incorporating RP authentication into the Implicit Flow. The IdP can restrict its service to authenticated RPs and tie each authentication token to a specific user and RP without acquiring knowledge of which user is accessing which RP. We formally define the desired security and privacy properties of such an authenticated Implicit Flow, propose a provably secure construction from generic building blocks, and report on an implementation of our scheme.

2.
Galal, T., Lehmann, A.: Privacy-Preserving Outsourced Certificate Validation. Privacy Enhancing Technologies Symposium (PETS). pp. 322–340 (2023).
[ Abstract ] [ Download ]
 
Digital Covid certificates are the first widely deployed end-user cryptographic certificates. For service providers, such as airlines or event ticket vendors, that needed to check that their (global) customers satisfy certain health policies, the verification of such Covid certificates was challenging though — not because of the cryptography involved, but due to the multitude of issuers, different certificate types and the evolving nature of country-specific policies that had to be supported. As Covid certificates contain sensitive health information, their (online) presentation to non-health related entities also poses clear privacy risk. To address both challenges, the EU proposed a specification for outsourcing the verification process to a validator service, that executes the process and informs service providers of the result. TheWHOannounced to adapt this approach for general vaccination credentials beyond Covid-19. While being beneficial to improve security and privacy for service providers, their solution requires strong trust assumption for the (central) validation service that learns all health-related details of the users. In our work, we propose and formally model a privacy-preserving variant of such an outsourced validation service. Therein the validator learns the attributes it is supposed to verify, but not the users identity. Still, the validator’s assertion is blindly bound to the user’s identity to ensure the desired user-binding. We analyze the EU specification in our model and show that it only meets a subset of those goals. Our analysis further shows that the EU protocol is unnecessarily complex and can be significantly simplified while maintaining the same (weak) level of security. Finally, we propose a new construction for privacy-preserving certificate validation that provably satisfies all desired goals.

3.
Dayanikli, D., Lehmann, A.: Password-Based Credentials with Security against Server Compromise. ESORICS. pp. 147–167 (2023).
[ Abstract ] [ Download ]
 
Password-based credentials (PBCs), introduced by Zhang et al. (NDSS'20), provide an elegant solution to secure, yet convenient user authentication. Therein the user establishes a strong cryptographic access credential with the server. To avoid the assumption of secure storage on the user side, the user does not store the credential directly, but only a password-protected version of it. The ingenuity of PBCs is that the password-based credential cannot be offline attacked, offering essentially the same strong security as standard key-based authentication. This security relies on a secret key of the server that is needed to verify whether an authentication token derived from a password-based credential and password is correct. However, the work by Zhang et al. assumes that this server key never gets compromised, and their protocol loses all security in case of a breach. As such a passive leak of the server's stored verification data is one of the main threats in user authentication, our work aims to strengthen PBC to remain secure even when the server's key got compromised. We first show that the desired security against server compromise is impossible to achieve in the original framework. We then introduce a modified version of PBCs that circumvents our impossibility result and formally define a set of security properties, each being optimal for the respective corruption setting. Finally, we propose a surprisingly simple construction that provably achieves our stronger security guarantees, and is generically composed from basic building blocks.

2022 [ to top ]

1.
Hacker, P., Naumann, F., Friedrich, T., Grundmann, S., Lehmann, A.: AI Compliance - Challenges of Bridging Data Science and Law. ACM Journal of Data and Information Quality. (2022).
[ Abstract ] [ URL ]
 
This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.

2.
Das, P., Hesse, J., Lehmann, A.: DPaSE: Distributed Password-Authenticated Symmetric Encryption. ACM AsiaCCS. pp. 682–696 (2022).
[ Abstract ] [ Download ]
 
Cloud storage is becoming increasingly popular among end users that outsource their personal data to services such as Dropbox or Google Drive. For security, uploaded data should ideally be encrypted under a key that is controlled and only known by the user. Current solutions that support user-centric encryption either require the user to manage strong cryptographic keys, or derive keys from weak passwords. While the former has massive usability issues and requires secure storage by the user, the latter approach is more convenient but offers only little security since encrypted data is susceptible to offline attacks. The recent concept of password-authenticated secret-sharing (PASS) enables users to securely derive strong keys from weak passwords by leveraging a distributed server setup, and has been considered a promising step towards secure and usable encryption. However, using PASS for encryption is not as suitable as originally thought: it only considers the (re)construction of a emphsingle, static key -- whereas practical encryption will require the management of emphmany, object-specific keys. Using a dedicated PASS instance for every key makes the solution vulnerable against online attacks, inherently leaks access patterns to the servers and poses the risk of permanent data loss when an incorrect password is used at encryption. We therefore propose a new protocol that directly targets the problem of boostrapping encryption from a single password: distributed password-authenticated symmetric encryption DPaSE. DPaSE offers strong security and usability, such as protecting the user's password against online and offline attacks, and ensuring message privacy and ciphertext integrity as long as at least one server is honest. We formally define the desired security properties in the UC framework and propose a provably secure instantiation. The core of our protocol is a new type of Oblivious Pseudorandom Function (OPRF) that allows to extend a previous partially-blind query with a follow-up request and will be used to blindly carry over passwords across evaluations and avoid online attacks. Our (proof-of-concept) implementation of DPaSE uses exponentiations at the user, exponentiations and pairings at each server, and has a server throughput of account creations and (user authentication followed by) encryptions per second, when run between a user and 2-10 servers.

3.
Casacuberta, S., Hesse, J., Lehmann, A.: SoK: Oblivious Pseudorandom Functions. IEEE EuroS&P. pp. 625–646 (2022).
[ Abstract ] [ Download ]
 
In recent years, oblivious pseudorandom functions (OPRFs) have become a ubiquitous primitive used in cryptographic protocols and privacy-preserving technologies. The growing interest in OPRFs, both theoretical and applied, has produced a vast number of different constructions and functionality variations. In this paper, we provide a systematic overview of how to build and use OPRFs. We first categorize existing OPRFs into essentially four families based on their underlying PRF (Naor-Reingold, Dodis-Yampolskiy, Hashed Diffie-Hellman, and generic constructions). This categorization allows us to give a unified presentation of all oblivious evaluation methods in the literature, and to understand which properties OPRFs can (or cannot) have. We further demonstrate the theoretical and practical power of OPRFs by visualizing them in the landscape of cryptographic primitives, and by providing a comprehensive overview of how OPRFs are leveraged for improving the privacy of internet users. Our work systematizes 15 years of research on OPRFs and provides inspiration for new OPRF constructions and applications thereof.

2021 [ to top ]

1.
Diaz, J., Lehmann, A.: Group Signatures with User-Controlled and Sequential Linkability. Public-Key Cryptography - PKC 2021. pp. 360–388 (2021).
[ Abstract ] [ Download ]
 
Group signatures allow users to create signatures on behalf of a group while remaining anonymous. Such signatures are a powerful tool to realize privacy-preserving data collections, where e.g., sensors, wearables or vehicles can upload authenticated measurements into a data lake. The anonymity protects the user’s privacy yet enables basic data processing of the uploaded unlinkable information. For many applications, full anonymity is often neither desired nor useful though, and selected parts of the data must eventually be correlated after being uploaded. Current solutions of group signatures do not provide such functionality in a satisfactory way: they either rely on a trusted party to perform opening or linking of signatures, which clearly conflicts with the core privacy goal of group signatures; or require the user to decide upon the linkability of signatures before they are generated. In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users – and only they – can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the user’s signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.

2.
Fraser, A., Garms, L., Lehmann, A.: Selectively Linkable Group Signatures - Stronger Security and Preserved Verifiability. CANS. pp. 200–221 (2021).
[ Abstract ] [ Download ]
 
Group signatures allow group members to sign on behalf of the group anonymously. They are therefore well suited to storing data in a way that preserves the users’ privacy, while guaranteeing its authenticity. Garms and Lehmann (PKC’19) introduced a new type of group signatures that balance privacy with utility by allowing to selectively link subsets of the group signatures via an oblivious entity, the converter. The conversion takes a batch of group signatures and blindly transforms signatures originating from the same user into a consistent representation. Their scheme essentially targets a setting where the entity receiving fully unlinkable signatures and the converted ones is the same: only pseudonyms but not full signatures are converted, and the input to the converter is assumed to be well-formed. Thus, the converted outputs are merely linkable pseudonyms but no longer signatures. In this work we extend and strengthen such convertibly linkable group signatures. Conversion can now be triggered by malicious entities too, and the converted outputs can be publicly verified. This preserves the authentication of data during the conversion process. We define the security of this scheme and give a provably secure instantiation. Our scheme makes use of controlled-malleable NIZKs, which allow proofs to be mauled in a controlled manner. This allows signatures to be blinded, while still ensuring they can be verified during conversions.

2020 [ to top ]

1.
Danz, N., Derwisch, O., Lehmann, A., Pünter, W., Stolle, M., Ziemann, J.: Provable Security Analysis of Decentralized Cryptographic Contact Tracing. (Preprint) IACR ePrint. (2020).
[ Abstract ] [ Download ]
 
Automated contact tracing leverages the ubiquity of smartphones to warn users about an increased exposure risk to COVID-19. In the course of only a few weeks, several cryptographic protocols have been proposed that aim to achieve such contract tracing in a decentralized and privacy-preserving way. Roughly, they let users' phones exchange random looking pseudonyms that are derived from locally stored keys. If a user is diagnosed, her phone uploads the keys which allows other users to check for any contact matches. Ultimately this line of work led to Google and Apple including a variant of these protocols into their phones which is currently used by millions of users. Due to the obvious urgency, these schemes were pushed to deployment without a formal analysis of the achieved security and privacy features. In this work we address this gap and provide the first formal treatment of such decentralized cryptographic contact tracing. We formally define three main properties in a game-based manner: pseudonym and trace unlinkability to guarantee the privacy of users during healthy and infectious periods, and integrity ensuring that triggering false positive alarms is infeasible. A particular focus of our work is on the timed aspects of these schemes, as both keys and pseudonyms are rotated regularly, and we specify different variants of the aforementioned properties depending on the time granularity for which they hold. We analyze a selection of practical protocols (DP-3T, TCN, GAEN) and prove their security under well-defined assumptions.

2.
Camenisch, J., Drijvers, M., Lehmann, A., Neven, G., Towa, P.: Short Threshold Dynamic Group Signatures. SCN. pp. 401–423 (2020).
[ Abstract ] [ Download ]
 
Traditional group signatures feature a single issuer who can add users to the group of signers and a single opening authority who can reveal the identity of the group member who computed a signature. Interestingly, despite being designed for privacy-preserving applications, they require strong trust in these central authorities who constitute single points of failure for critical security properties. To reduce the trust placed on authorities, we introduce dynamic group signatures which distribute the role of issuer and opener over several entities, and support t_I-out-of-n_I issuance and t_O-out-of-n_O opening. We first define threshold dynamic group signatures and formalize their security. We then give an efficient construction relying on the pairing-based Pointcheval–Sanders (PS) signature scheme (CT-RSA 2018), which yields very short group signatures of two first-group elements and three exponents. We also give a simpler variant of our scheme in which issuance requires the participation of all n_I issuers, but still supports t_O-out-of-n_O opening. It is based on a new multi-signature variant of the PS scheme which allows for efficient proofs of knowledge and is a result of independent inter- est. We prove our schemes secure in the random-oracle model under a non-interactive q-type of assumption.

3.
Baum, C., Frederiksen, T., Hesse, J., Lehmann, A., Yanai, A.: PESTO: Proactively Secure Distributed Single Sign-On, or How to Trust a Hacked Server. IEEE EuroS&P. pp. 587–606 (2020).
[ Abstract ] [ Download ]
 
Single Sign-On (SSO) is becoming an increasingly popular authentication method for users that leverages a trusted Identity Provider (IdP) to bootstrap secure authentication tokens from a single user password. It alleviates some of the worst security issues of passwords, as users no longer need to memorize individual passwords for all service providers, and it removes the burden of these service to properly protect huge password databases. However, SSO also introduces a single point of failure. If compromised, the IdP can impersonate all users and learn their master passwords. To remedy this risk while preserving the advantages of SSO, Agrawal et al. (CCS'18) recently proposed a distributed realization termed PASTA (password-authenticated threshold authentication) which splits the role of the IdP across n servers. While PASTA is a great step forward and guarantees security as long as not all servers are corrupted, it uses a rather inflexible corruption model: servers cannot be corrupted adaptively and --- even worse --- cannot recover from corruption. The latter is known as proactive security and allows servers to re-share their keys, thereby rendering all previously compromised information useless. In this work, we improve upon the work of PASTA and propose a distributed SSO protocol with proactive and adaptive security (PESTO), guaranteeing security as long as not all servers are compromised at the same time. We prove our scheme secure in the UC framework which is known to provide the best security guarantees for password-based primitives. The core of our protocol are two new primitives we introduce: partially-oblivious distributed PRFs and a class of distributed signature schemes. Both allow for non-interactive refreshs of the secret key material and tolerate adaptive corruptions. We give secure instantiations based on the gap one-more BDH and RSA assumption respectively, leading to a highly efficient 2-round PESTO protocol. We also present an implementation and benchmark of our scheme in Java, realizing OAuth-compatible bearer tokens for SSO, demonstrating the viability of our approach.

4.
Camenisch, J., Drijvers, M., Lehmann, A., Neven, G., Towa, P.: Zone Encryption with Anonymous Authentication for V2V Communication. IEEE EuroS&P. pp. 405–424 (2020).
[ Abstract ] [ Download ]
 
Vehicle-to-vehicle (V2V) communication systems are currently being prepared for real-world deployment, but they face strong opposition over privacy concerns. Position beacon messages are the main culprit, being broadcast in cleartext and pseudonymously signed up to 10 times per second. So far, no practical solutions have been proposed to en- crypt or anonymously authenticate V2V messages. We propose two cryptographic innovations that enhance the privacy of V2V communication. As a core contribution, we introduce zone-encryption schemes, where vehicles generate and authentically distribute encryption keys associated to static geographic zones close to their location. Zone encryption provides security against eavesdropping, and, combined with a suitable anonymous authentication scheme, ensures that messages can only be sent by genuine vehicles, while adding only 224 Bytes of cryptographic overhead to each message. Our second contribution is an authentication mechanism fine-tuned to the needs of V2V which allows vehicles to authentically distribute keys, and is called dynamic group signatures with attributes. Our instantiation features unlimited locally generated pseudonyms, negligible credential download-and-storage costs, identity recovery by a trusted authority, and compact signatures of 216 Bytes at a 131-bit security level.

5.
Bootle, J., Lehmann, A., Lyubashevsky, V., Seiler, G.: Compact Privacy Protocols from Post-Quantum and Timed Classical Assumptions. PQCrypto. pp. 226–246 (2020).
[ Abstract ] [ Download ]
 
While basic lattice-based primitives like encryption and digital signature schemes are already fairly short, more advanced privacy-preserving protocols (e.g. group signatures) that are believed to be post-quantum secure have outputs of at least several hundred kilobytes. In this paper, we propose a framework for building privacy protocols with significantly smaller parameter sizes whose secrecy is based on post-quantum assumptions, but soundness additionally assumes that some classical assumption, e.g., the discrete logarithm problem (DLP), is hard to break within a short amount of time. The main ingredients of our constructions are statistical zero-knowledge proofs of knowledge for certain relations, whose soundness rely on the hardness of solving the discrete logarithm problem for a fresh DLP instance per proof. This notion has recently been described by the term quantum annoyance. Using such proofs, while also enforcing that they be completed in a fixed amount of time, we then show how to construct privacy-preserving primitives such as (dynamic) group signatures and DAA schemes, where soundness is based on the hardness of the "timed" discrete logarithm problem and SIS. The outputs of our schemes are significantly shorter (~30X) than purely lattice-based schemes.

2019 [ to top ]

1.
Moreno, R.T., Bernabé, J.B., Skarmeta, A.F., Stausholm, M., Frederiksen, T.K., Mart’inez, N., Ponte, N., Sakkopoulos, E., Lehmann, A.: OLYMPUS: towards Oblivious identitY Management for Private and User-friendly Services. GIoTS. bll. 1–6. IEEE (2019).
 

2.
Chen, L., Kassem, N.E., Lehmann, A., Lyubashevsky, V.: A Framework for Efficient Lattice-Based DAA. CYSARM@CCS. bll. 23–34. ACM (2019).
[ Abstract ] [ Download ]
 
Currently standardized Direct Anonymous Attestation (DAA) schemes have their security based on the factoring and the discrete logarithm problems, and are therefore insecure against quantum attackers. This paper presents a quantum-safe lattice-based Direct Anonymous Attestation protocol that can be suitable for inclusion in a future quantum-resistant TPM. The security of our proposed scheme is proved in the Universal Composability (UC) model under the assumed hardness of the Ring-SIS, Ring-LWE, and NTRU problems. The signature size of our proposed DAA scheme is around 2MB, which is (at least) two orders of magnitude smaller compared to existing post-quantum DAA schemes.

3.
Bradley, T., Camenisch, J., Jarecki, S., Lehmann, A., Neven, G., Xu, J.: Password-Authenticated Public-Key Encryption. ACNS. bll. 442–462. Springer (2019).
[ Abstract ] [ Download ]
 
We introduce password-authenticated public-key encryption (PAPKE), a new cryptographic primitive. PAPKE enables secure end-to-end encryption between two entities without relying on a trusted third party or other out-of-band mechanisms for authentication. Instead, resistance to man-in-the-middle attacks is ensured in a human-friendly way by authenticating the public key with a shared password, while preventing offline dictionary attacks given the authenticated public key and/or the ciphertexts produced using this key. Our contributions are three-fold. First, we provide property-based and universally composable (UC) definitions for PAPKE, with the resulting primitive combining CCA security of public-key encryption (PKE) with password authentication. Second, we show that PAPKE implies Password-Authenticated Key Exchange (PAKE), but the reverse implication does not hold, indicating that PAPKE is a strictly stronger primitive than PAKE. Indeed, PAPKE implies a two-flow PAKE which remains secure if either party re-uses its state in multiple sessions, e.g. due to communication errors, thus strengthening existing notions of PAKE security. Third, we show two highly practical UC PAPKE schemes: a generic construction built from CCA-secure and anonymous PKE and an ideal cipher, and a direct construction based on the Decisional Diffie-Hellman assumption in the random oracle model. Finally, applying our PAPKE-to-PAKE compiler to the above PAPKE schemes we exhibit the first 2-round UC PAKE's with efficiency comparable to (unauthenticated) Diffie-Hellman Key Exchange.

4.
Frederiksen, T.K., Hesse, J., Lehmann, A., Moreno, R.T.: Identity Management: State of the Art, Challenges and Perspectives. Privacy and Identity Management. Data for Better Living: AI and Privacy. bll. 45–62. Springer (2019).
[ Abstract ] [ Download ]
 
Passwords are still the primary means for achieving user authentication online. However, using a username-password combination at every service provider someone wants to connect to introduces several possibilities for vulnerabilities. A combination of password reuse and a compromise of an iffy provider can quickly lead to financial and identity theft. Further, the username-password paradigm also makes it hard to distribute authorized and up-to-date attributes about users; like residency or age. Being able to share such authorized information is becoming increasingly more relevant as more real-world services become connected online. A number of alternative approaches such as individual user certificates, Single Sign-On (SSO), and Privacy-Enhancing Attribute-Based Credentials (P-ABCs) exist. We will discuss these different strategies and highlight their individual benefits and shortcomings. In short, their strengths are highly complementary: P-ABC based solutions are strongly secure and privacy-friendly but cumbersome to use; whereas SSO provides a convenient and user-friendly solution, but requires a fully trusted identity provider, as it learns all users’ online activities and could impersonate users towards other providers. The vision of the Olympus project is to combine the advantages of these approaches into a secure and user-friendly identity management system using distributed and advanced cryptography. The distributed aspect will avoid the need of a single trusted party that is inherent in SSO, yet maintain its usability advantages for the end users. We will sketch our vision and outline the design of Olympus’ distributed identity management system.

5.
Lehmann, A.: ScrambleDB: Oblivious (Chameleon) Pseudonymization-as-a-Service. PoPETs. 2019, 289–309 (2019).
[ Abstract ] [ Download ]
 
Pseudonymization is a widely deployed technique to de-sensitize data sets by consistently replacing identifying attributes with non-sensitive surrogates. However, all existing solutions are impractical to deploy in settings where data is accumulated from distributed sources: they either require sharing the same secret key with all sources, or rely on a fully trusted service to consistently compute these pseudonyms. Further, the consistency of pseudonyms, which is required to maintain the data's utility, comes with inherent and severe privacy limitations. This paper solves the key management and privacy challenges by introducing oblivious pseudonymization-as-a-service. Therein, the pseudonymization is outsourced to a central, yet fully oblivious entity, i.e., the service neither learns the sensitive information nor the pseudonyms it produces. Further, to obtain better privacy we no longer require pseudonyms to be computed consistently and instead introduce a dedicated join procedure. When data is stored at rest, all data is pseudonymized in a fully unlinkable manner. Only when certain subsets of the data are needed, the linkage is established through a controlled and non-transitive join operation. We formally define the desired security properties in the UC framework and propose a generic protocol that provably satisfies them. The core of our scheme is a 3-party oblivious and convertible PRF, which we believe to be of independent interest.

6.
Garms, L., Lehmann, A.: Group Signatures with Selective Linkability. Public Key Cryptography (1). bll. 190–220. Springer (2019).
[ Abstract ] [ Download ]
 
Group signatures allow members of a group to anonymously produce signatures on behalf of the group. They are an important building block for privacy-enhancing applications, e.g., enabling user data to be collected in authenticated form while preserving the user' s privacy. The linkability between the signatures thereby plays a crucial role for balancing utility and privacy: knowing the correlation of events significantly increases the utility of the data but also severely harms the user's privacy. Therefore group signatures are unlinkable per default, but either support linking or identity escrow through a dedicated central party or offer user-controlled linkability. However, both approaches have significant limitations. The former relies on a fully trusted entity and reveals too much information, and the latter requires exact knowledge of the needed linkability at the moment when the signatures are created. However, often the exact purpose of the data might not be clear at the point of data collection. In fact, data collectors tend to gather large amounts of data at first, but will need linkability only for selected, small subsets of the data. We introduce a new type of group signatures that provide a more flexible and privacy-friendly access to such selective linkability. When created, all signatures are fully unlinkable. Only when strictly needed or desired, should the required pieces be made linkable with the help of a central entity. For privacy, this linkability is established in an oblivious and non-transitive manner. We formally define the requirements for this new type of group signatures and provide an efficient instantiation that provably satisfies these requirements under discrete-logarithm based assumptions.

7.
Klooß, M., Lehmann, A., Rupp, A.: (R)CCA Secure Updatable Encryption with Integrity Protection. EUROCRYPT (1). bll. 68–99. Springer (2019).
[ Abstract ] [ Download ]
 
An updatable encryption scheme allows a data host to update ciphertexts of a client from an old to a new key, given so-called update tokens from the client. Rotation of the encryption key is a common requirement in practice in order to mitigate the impact of key compromises over time. There are two incarnations of updatable encryption: One is ciphertext-dependent, i.e. the data owner has to (partially) download all of his data and derive a dedicated token per ciphertext. Everspaugh et al. (CRYPTO'17) proposed CCA and CTXT secure schemes in this setting. The other, more convenient variant is ciphertext-independent, i.e., it allows a single token to update all ciphertexts. However, so far, the broader functionality of tokens in this setting comes at the price of considerably weaker security: the existing schemes by Boneh et al. (CRYPTO'13) and Lehmann and Tackmann (EUROCRYPT'18) only achieve CPA security and provide no integrity protection. Arguably, when targeting the scenario of outsourcing data to an untrusted host, plaintext integrity should be a minimal security requirement. Otherwise, the data host may alter or inject ciphertexts arbitrarily. Indeed, the schemes from BLMR13 and LT18 suffer from this weakness, and even EPRS17 only provides integrity against adversaries which cannot arbitrarily inject ciphertexts. In this work, we provide the first ciphertext-independent updatable encryption schemes with security beyond CPA, in particular providing strong integrity protection. Our constructions and security proofs of updatable encryption schemes are surprisingly modular. We give a generic transformation that allows key-rotation and confidentiality/integrity of the scheme to be treated almost separately, i.e., security of the updatable scheme is derived from simple properties of its static building blocks. An interesting side effect of our generic approach is that it immediately implies the unlinkability of ciphertext updates that was introduced as an essential additional property of updatable encryption by EPRS17 and LT18.

2018 [ to top ]

1.
Lehmann, A., Tackmann, B.: Updatable Encryption with Post-Compromise Security. EUROCRYPT (3). bll. 685–716. Springer (2018).
[ Abstract ] [ Download ]
 
An updatable encryption scheme allows to periodically rotate the encryption key and move already existing ciphertexts from the old to the new key. These ciphertext updates are done with the help of a so-called update token and can be performed by an untrusted party, as the update never decrypts the data. Updatable encryption is particularly useful in settings where encrypted data is outsourced, e.g., stored on a cloud server. The data owner can produce an update token, and the cloud server can update the ciphertexts. We provide a comprehensive treatment of ciphertext-independent schemes, where a single token is used to update all ciphertexts. We show that the existing ciphertext-independent schemes and models by Boneh et al. (CRYPTO' 13) and Everspaugh et al. (CRYPTO' 17) do not guarantee the post-compromise security one would intuitively expect from key rotation. In fact, the simple scheme recently proposed by Everspaugh et al. allows to recover the current key upon corruption of a single old key. Surprisingly, none of the models so far reflects the timely aspect of key rotation which makes it hard to grasp when an adversary is allowed to corrupt keys. We propose strong security models that clearly capture post-compromise and forward security under adaptive attacks. We then analyze various existing schemes and show that none of them is secure in this strong model, but we formulate the additional constraints that suffice to prove their security in a relaxed version of our model. Finally, we propose a new updatable encryption scheme that achieves our strong notions while being (at least) as efficient as the existing solutions.

2.
Cremers, C., Lehmann, A. reds: Security Standardisation Research - 4th International Conference, SSR 2018, Darmstadt, Germany, November 26-27, 2018, Proceedings. Springer (2018).
 

3.
Camenisch, J., Drijvers, M., Gagliardoni, T., Lehmann, A., Neven, G.: The Wonderful World of Global Random Oracles. EUROCRYPT (1). bll. 280–312. Springer (2018).
[ Abstract ] [ Download ]
 
The random-oracle model by Bellare and Rogaway (CCS'93) is an indispensable tool for the security analysis of practical cryptographic protocols. However, the traditional random-oracle model fails to guarantee security when a protocol is composed with arbitrary protocols that use the same random oracle. Canetti, Jain, and Scafuro (CCS'14) put forth a global but non-programmable random oracle in the Generalized UC framework and showed that some basic cryptographic primitives with composable security can be efficiently realized in their model. Because their random-oracle functionality is non-programmable, there are many practical protocols that have no hope of being proved secure using it. In this paper, we study alternative definitions of a global random oracle and, perhaps surprisingly, show that these allow one to prove GUC-secure existing, very practical realizations of a number of essential cryptographic primitives including public-key encryption, non-committing encryption, commitments, Schnorr signatures, and hash-and-invert signatures. Some of our results hold generically for any suitable scheme proven secure in the traditional ROM, some hold for specific constructions only. Our results include many highly practical protocols, for example, the folklore commitment scheme H(m|r) (where m is a message and r is the random opening information) which is far more efficient than the construction of Canetti et al.

2017 [ to top ]

1.
Cachin, C., Camenisch, J., Freire-Stögbuchner, E., Lehmann, A.: Updatable Tokenization: Formal Definitions and Provably Secure Constructions. Financial Cryptography. bll. 59–75. Springer (2017).
[ Abstract ] [ Download ]
 
Tokenization is the process of consistently replacing sensitive elements, such as credit cards numbers, with non-sensitive surrogate values. As tokenization is mandated for any organization storing credit card data, many practical solutions have been introduced and are in commercial operation today. However, all existing solutions are static yet, i.e., they do not allow for efficient updates of the cryptographic keys while maintaining the consistency of the tokens. This lack of updatability is a burden for most practical deployments, as cryptographic keys must also be re-keyed periodically for ensuring continued security. This paper introduces a model for updatable tokenization with key evolution, in which a key exposure does not disclose relations among tokenized data in the past, and where the updates to the tokenized data set can be made by an untrusted entity and preserve the consistency of the data. We formally define the desired security properties guaranteeing unlinkability of tokens among different time epochs and one-wayness of the tokenization process. Moreover, we construct two highly efficient updatable tokenization schemes and prove them to achieve our security notions.

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

3.
Camenisch, J., Lehmann, A.: Privacy-Preserving User-Auditable Pseudonym Systems. EuroS&P. bll. 269–284. IEEE (2017).
[ Abstract ] [ Download ]
 
Personal information is often gathered and processed in a decentralized fashion. Examples include health records and governmental data bases. To protect the privacy of individuals, no unique user identifier should be used across the different databases. At the same time, the utility of the distributed information needs to be preserved which requires that it be nevertheless possible to link different records if they relate to the same user. Recently, Camenisch and Lehmann (CCS 15) have proposed a pseudonym scheme that addresses this problem by domain-specific pseudonyms. Although being unlinkable, these pseudonyms can be converted by a central authority (the converter). To protect the users' privacy, conversions are done blindly without the converter learning the pseudonyms or the identity of the user. Unfortunately, their scheme sacrifices a crucial privacy feature: transparency. Users are no longer able to inquire with the converter and audit the flow of their personal data. Indeed, such auditability appears to be diametral to the goal of blind pseudonym conversion. In this paper we address these seemingly conflicting requirements and provide a system where user-centric audits logs are created by the oblivious converter while maintaining all privacy properties. We prove our protocol to be UC-secure and give an efficient instantiation using novel building blocks.

4.
Camenisch, J., Drijvers, M., Lehmann, A.: Anonymous Attestation with Subverted TPMs. CRYPTO (3). bll. 427–461. Springer (2017).
[ Abstract ] [ Download ]
 
Various sources have revealed that cryptographic standards and components have been subverted to undermine the security of users, reigniting research on means to achieve security in presence of such subverted components. In this paper we consider direct anonymous attestation (DAA) in this respect. This standardized protocol allows a computer with the help of an embedded TPM chip to remotely attest that it is in a healthy state. Guaranteeing that different attestations by the same computer cannot be linked was an explicit and important design goal of the standard in order to protect the privacy of the user of the computer. Surprisingly, none of the standardized or otherwise proposed DAA protocols achieves privacy when the TPM is subverted, but they all rely on the honesty of the TPM. As the TPM is a piece of hardware, it is hardly possible to tell whether or not a given TPM follows the specified protocol. In this paper we study this setting and provide a new protocol that achieves privacy also in presence of subverted TPMs.

5.
Camenisch, J., Chen, L., Drijvers, M., Lehmann, A., Novick, D., Urian, R.: One TPM to Bind Them All: Fixing TPM 2.0 for Provably Secure Anonymous Attestation. IEEE Symposium on Security and Privacy. bll. 901–920. IEEE Computer Society (2017).
[ Abstract ] [ Download ]
 
The Trusted Platform Module (TPM) is an international standard for a security chip that can be used for the management of cryptographic keys and for remote attestation. The specification of the most recent TPM 2.0 interfaces for direct anonymous attestation unfortunately has a number of severe shortcomings. First of all, they do not allow for security proofs (indeed, the published proofs are incorrect). Second, they provide a Diffie-Hellman oracle w.r.t. the secret key of the TPM, weakening the security and preventing forward anonymity of attestations. Fixes to these problems have been proposed, but they create new issues: they enable a fraudulent TPM to encode information into an attestation signature, which could be used to break anonymity or to leak the secret key. Furthermore, all proposed ways to remove the Diffie-Hellman oracle either strongly limit the functionality of the TPM or would require significant changes to the TPM 2.0 interfaces. In this paper we provide a better specification of the TPM 2.0 interfaces that addresses these problems and requires only minimal changes to the current TPM 2.0 commands. We then show how to use the revised interfaces to build q-SDH- and LRSW-based anonymous attestation schemes, and prove their security. We finally discuss how to obtain other schemes addressing different use cases such as key-binding for U-Prove and e-cash.

2016 [ to top ]

1.
Camenisch, J., Lehmann, A., Neven, G., Samelin, K.: Virtual Smart Cards: How to Sign with a Password and a Server. SCN. bll. 353–371. Springer (2016).
[ Abstract ] [ Download ]
 
An important shortcoming of client-side cryptography on consumer devices is the poor protection of secret keys. Encrypting the keys under a human-memorizable password hardly offers any protection when the device is stolen. Trusted hardware tokens such as smart cards can provide strong protection of keys but are cumbersome to use. We consider the case where secret keys are used for digital signatures and propose a password-authenticated server-aided signature Pass2Sign protocol, where signatures are collaboratively generated by a device and a server, while the user authenticates to the server with a (low-entropy) password. Neither the server nor the device store enough information to create a signature by itself or to perform an offline attack on the password. The signed message remains hidden from the server. We argue that our protocol offers comparable security to trusted hardware, but without its inconveniences. We prove it secure in the universal composability (UC) framework in a very strong adaptive corruption model where, unlike standard UC, the adversary does not obtain past inputs and outputs upon corrupting a party. This is crucial to hide previously entered passwords and messages from the adversary when the device gets corrupted. The protocol itself is surprisingly simple: it is round-optimal, efficient, and relies exclusively on standard primitives such as hash functions and RSA. The security proof involves a novel random-oracle programming technique that may be of independent interest.

2.
Camenisch, J., Drijvers, M., Lehmann, A.: Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited. TRUST. bll. 1–20. Springer (2016).
[ Abstract ] [ Download ]
 
Direct Anonymous Attestation (DAA) is a cryptographic protocol for privacy-protecting authentication. It is standardized in the TPM standard and implemented in millions of chips. A variant of DAA is also used in Intel's SGX. Recently, Camenisch et al.(PKC 2016) demonstrated that existing security models for DAA do not correctly capture all security requirements, and showed a number of flaws in existing schemes based on the LRSW assumption. In this work, we identify flaws in security proofs of a number of qSDH-based DAA schemes and point out that none of the proposed schemes can be proven secure in the recent model by Camenisch et al.(PKC 2016). We therefore present a new, provably secure DAA scheme that is based on the qSDH assumption. The new scheme is one of the most efficient DAA schemes, with support for DAA extensions to signature-based revocation and attributes. We rigorously prove the scheme secure in the model of Camenisch et al., which we modify to support the extensions. As a side-result of independent interest, we prove that the BBS+ signature scheme is secure in the type-3 pairing setting, allowing for our scheme to be used with the most efficient pairing-friendly curves.

3.
Lehmann, A., Whitehouse, D., Fischer-Hübner, S., Fritsch, L., Raab, C.D. reds: Privacy and Identity Management. Facing up to Next Steps - 11th IFIP WG 9.2, 9.5, 9.6/11.7, 11.4, 11.6/SIG 9.2.2 International Summer School, Karlstad, Sweden, August 21-26, 2016, Revised Selected Papers. (2016).
 

4.
Camenisch, J., Drijvers, M., Lehmann, A.: Universally Composable Direct Anonymous Attestation. Public Key Cryptography (2). bll. 234–264. Springer (2016).
[ Abstract ] [ Download ]
 
Direct Anonymous Attestation (DAA) is one of the most complex cryptographic algorithms that has been deployed in practice. In spite of this, and the long body of work on the subject, there is still no fully satisfactory security definition for DAA. This was already acknowledged by Bernard et al. (IJIC'13) who showed that in existing models even fully insecure protocols may be deemed secure. Bernard et al. therefore proposed an extensive set of security games, which however aimed only at a simplified setting, termed pre-DAA. In pre-DAA the host platform that runs the TPM is assumed to be trusted too. Consequently, their notion does not guarantee any security if the TPM is embedded in a potentially corrupt host, which is a significant restriction. In this paper, we give a comprehensive security definition for full DAA in the form of an ideal functionality in the Universal Composability model. Our definition considers the host and TPM to be individual entities that can be in different corruption states. None of the existing DAA schemes immediately satisfies our strong security notion, and we therefore also propose a realization that is based on a DAA scheme supported by the TPM 2.0 standard and rigorously prove it secure in our model.

2015 [ to top ]

1.
Camenisch, J., Lehmann, A., Lysyanskaya, A., Neven, G.: A Single Password for Everything?. ERCIM News. 2015, (2015).
 

2.
Lehmann, A., Wolf, S. reds: Information Theoretic Security - 8th International Conference, ICITS 2015, Lugano, Switzerland, May 2-5, 2015. Proceedings. Springer (2015).
 

3.
Bichsel, P., Camenisch, J., Dubovitskaya, M., Enderlein, R.R., Krenn, S., Krontiris, I., Lehmann, A., Neven, G., Paquin, C., Preiss, F.-S., Rannenberg, K., Sabouri, A.: An Architecture for Privacy-ABCs. Attribute-based Credentials for Trust. bll. 11–78. Springer (2015).
[ URL ]
 

4.
Bichsel, P., Camenisch, J., Dubovitskaya, M., Enderlein, R.R., Krenn, S., Lehmann, A., Neven, G., Preiss, F.-S.: Cryptographic Protocols Underlying Privacy-ABCs. Attribute-based Credentials for Trust. bll. 79–108. Springer (2015).
[ URL ]
 

5.
Camenisch, J., Krenn, S., Lehmann, A., Mikkelsen, G.L., Neven, G., Pedersen, M.O.: Formal Treatment of Privacy-Enhancing Credential Systems. SAC. bll. 3–24. Springer (2015).
[ Abstract ] [ Download ]
 
Privacy-enhancing attribute-based credentials (PABCs) are the core ingredient to privacy-friendly authentication systems, allowing users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion while revealing only a subset of the attributes. To be useful in practice, however, PABCs typically need additional features such as i) revocation, ii) pooling prevention by binding credentials to users' secret keys, iii) pseudonyms as privacy-friendly user public keys, iv) proving equality of attributes without revealing their values, v) or advanced issuance where attributes can be "blindly" carried over into new credentials. Provably secure solutions exist for most of these features in isolation, but it is unclear how they can be securely combined into a full-fledged PABC system, or even which properties such a system would aim to fulfill. We provide a formal treatment of PABC systems supporting the mentioned features by defining their syntax and security properties, resulting in the most comprehensive definitional framework for PABCs so far. Unlike previous efforts, our definitions are not targeted at one specific use-case; rather, we try to capture generic properties that can be useful in a variety of scenarios. We believe that our definitions can also be used as a starting point for diverse application-dependent extensions and variations of PABCs. We present and prove secure a generic and modular construction of a PABC system from simpler building blocks, allowing for a "plug-and-play" composition based on different instantiations of the building blocks. Finally, we give secure instantiations for each of the building blocks, including in particular instantiations based on CL- and Brands-signatures which are the core of the Idemix and U-Prove protocols.

6.
Baldimtsi, F., Camenisch, J., Hanzlik, L., Krenn, S., Lehmann, A., Neven, G.: Recovering Lost Device-Bound Credentials. ACNS. bll. 307–327. Springer (2015).
[ Abstract ]
 
Anonymous credential systems allow users to authenticate in a secure and private fashion. To protect credentials from theft as well as from being shared among multiple users, credentials can be bound to physical devices such as smart cards or tablets. However, device-bound credentials cannot be exported and backed up for the case that the device breaks down or is stolen. Restoring the credentials one by one and re-enabling the legitimate owner to use them may require significant efforts from the user. We present a mechanism that allows users to store some partial backup information of their credentials that will allow them to restore them through a single interaction with a device registration authority, while security and privacy are maintained. We therefore define anonymous credentials with backup and provide a generic construction that can be built on top of many existing credential systems.

7.
Camenisch, J., Lehmann, A.: Privacy for Distributed Databases via (Un)linkable Pseudonyms. ACM Conference on Computer and Communications Security. bll. 1467–1479. ACM (2015).
[ Abstract ] [ Download ]
 
When data maintained in a decentralized fashion needs to be synchronized or exchanged between different databases, related data sets usually get associated with a unique identifier. While this approach facilitates cross-domain data exchange, it also comes with inherent drawbacks in terms of controllability. As data records can easily be linked, no central authority can limit or control the information flow. Worse, when records contain sensitive personal data, as is for instance the case in national social security systems, such linkability poses a massive security and privacy threat. An alternative approach is to use domain-specific pseudonyms, where only a central authority knows the cross-domain relation between the pseudonyms. However, current solutions require the central authority to be a fully trusted party, as otherwise it can provide false conversions and exploit the data it learns from the requests. We propose an (un)linkable pseudonym system that overcomes those limitations, and enables controlled yet privacy-friendly exchange of distributed data. We prove our protocol secure in the UC framework and provide an efficient instantiation based on discrete-logarithm related assumptions.

8.
Camenisch, J., Lehmann, A., Neven, G.: Optimal Distributed Password Verification. ACM Conference on Computer and Communications Security. bll. 182–194. ACM (2015).
[ Abstract ] [ Download ]
 
We present a highly efficient cryptographic protocol to protect user passwords against server compromise by distributing the capability to verify passwords over multiple servers. Password verification is a single-round protocol and requires from each server only one exponentiation in a prime-order group. In spite of its simplicity, our scheme boasts security against dynamic and transient corruptions, meaning that servers can be corrupted at any time and can recover from corruption by going through a non-interactive key refresh procedure. The users' passwords remain secure against offline dictionary attacks as long as not all servers are corrupted within the same time period between refreshes. The only currently known scheme to achieve such strong security guarantees incurs the considerable cost of several hundred exponentiations per server. We prove our scheme secure in the universal composability model, which is well-known to offer important benefits for password-based primitives, under the gap one-more Diffie-Hellman assumption in the random-oracle model. Server initialization and refresh must take place in a trusted execution environment. Initialization additionally requires a secure message to each server, but the refresh procedure is non-interactive. We show that these requirements are easily met in practice by providing an example deployment architecture.

2014 [ to top ]

1.
Camenisch, J., Lehmann, A., Lysyanskaya, A., Neven, G.: Memento: How to Reconstruct Your Secrets from a Single Password in a Hostile Environment. CRYPTO (2). bll. 256–275. Springer (2014).
[ Abstract ] [ Download ]
 
Passwords are inherently vulnerable to dictionary attacks, but are quite secure if guessing attempts can be slowed down, for example by an online server. If this server gets compromised, however, the attacker can again perform an offline attack. The obvious remedy is to distribute the password verification process over multiple servers, so that the password remains secure as long as no more than a threshold of the servers are compromised. By letting these servers additionally host shares of a strong secret that the user can recover upon entering the correct password, the user can perform further cryptographic tasks using this strong secret as a key, e.g., encrypting data in the cloud. Threshold password-authenticated secret sharing (TPASS) protocols provide exactly this functionality, but the two only known schemes by Bagherzandi et al. (CCS 2011) and Camenisch et al. (CCS 2012) leak the password if a user mistakenly executes the protocol with malicious servers. Authenticating to the wrong servers is a common scenario when users are tricked in phishing attacks. We propose the first t-out-of-n TPASS protocol for any n > t that does not suffer from this shortcoming. We prove our protocol secure in the UC framework, which for the particular case of password-based protocols offers important advantages over property-based definitions, e.g., by correctly modeling typos in password attempts.

2.
Camenisch, J., Lehmann, A., Neven, G., Rial, A.: Privacy-Preserving Auditing for Attribute-Based Credentials. ESORICS (2). bll. 109–127. Springer (2014).
[ Abstract ] [ Download ]
 
Privacy-enhancing attribute-based credentials (PABCs) allow users to authenticate to verifiers in a data-minimizing way, in the sense that users are unlinkable between authentications and only disclose those attributes from their credentials that are relevant to the verifier. We propose a practical scheme to apply the same data minimization principle when the verifiers' authentication logs are subjected to external audits. Namely, we propose an extended PABC scheme where the verifier can further remove attributes from presentation tokens before handing them to an auditor, while preserving the verifiability of the audited tokens. We present a generic construction based on a signature, a signature of knowledge and a trapdoor commitment scheme, prove it secure in the universal composability framework, and give efficient instantiations based on the strong RSA and Decision Composite Residuosity (DCR) assumptions in the random-oracle model.

3.
Fischlin, M., Lehmann, A., Pietrzak, K.: Robust Multi-Property Combiners for Hash Functions. J. Cryptology. 27, 397–428 (2014).
[ Abstract ] [ Download ]
 
A robust combiner for hash functions takes two candidate implementations and constructs a hash function which is secure as long as at least one of the candidates is secure. So far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS they are often required to provide several properties simultaneously. We therefore put forward the notion of robust multi-property combiners and elaborate on different definitions for such combiners. We then propose a combiner that provably preserves (target) collision-resistance, pseudorandomness, and being a secure message authentication code. This combiner satisfies the strongest notion we propose, which requires that the combined function satisfies every security property which is satisfied by at least one of the underlying hash function. If the underlying hash functions have output length n, the combiner has output length 2n. This basically matches a known lower bound for black-box combiners for collision-resistance only, thus the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the property of being indifferentiable from a random oracle, slightly increasing the output length to 2n + \omega(log n). Moreover, we show how to augment our constructions in order to make them also robust for the one-wayness property, but in this case require an a priory upper bound on the input length.

2013 [ to top ]

1.
Horsch, M., Hühnlein, D., Lehmann, A., Schmölz, J., Wich, T.: Authentisierung mit der Open eCard App. Datenschutz und Datensicherheit. 37, 507–511 (2013).
 

2.
Camenisch, J., Dubovitskaya, M., Lehmann, A., Neven, G., Paquin, C., Preiss, F.-S.: Concepts and Languages for Privacy-Preserving Attribute-Based Authentication. IDMAN. bll. 34–52. Springer (2013).
[ Abstract ] [ URL ]
 
Existing cryptographic realizations of privacy-friendly authentication mechanisms such as anonymous credentials, minimal disclosure tokens, selfblindable credentials, and group signatures vary largely in the features they offer and in how these features are realized. Some features such as revocation or de-anonymization even require the combination of several cryptographic protocols. These differences and the complexity of the cryptographic protocols hinder the deployment of these mechanisms for practical applications and also make it almost impossible to switch the underlying cryptographic algorithms once the application has been designed. In this paper, we aim to overcome this issue and simplify both the design and deployment of privacy-friendly authentication mechanisms. We define and unify the concepts and features of privacy-preserving attribute-based credentials (Privacy-ABCs) and provide a language framework in XML schema. Our language framework enables application developers to use Privacy-ABCs with all their features without having to consider the specifics of the underlying cryptographic algorithms similar to as they do today for digital signatures, where they do not need to worry about the particulars of the RSA and DSA algorithms either.

2012 [ to top ]

1.
Camenisch, J., Lehmann, A., Neven, G.: Electronic Identities Need Private Credentials. IEEE Security & Privacy. 10, 80–83 (2012).
[ Abstract ] [ URL ]
 
For transactions on the Internet, user authentication typically involves usernames and passwords. When creating an account, users often must provide additional personal information. Usually, this is a list of self-claimed attributes such as name, address, or birth date. Only a few attributes such as email address and credit card information have some mechanism to authenticate them. Solutions such as the Security Assertion Markup Language, OpenID, or X.509 certificates let users authenticate and transfer attributes, certified by an issuer, to a relying party in a more trusted way. However, these technologies still have considerable security and privacy concerns. Private credentials are a superior solution. With them, issuers don't have to be involved during authentication. Also, users disclose only those attributes required by the relying parties and can do so without being easily tracked across their transactions

2.
Degabriele, J.P., Lehmann, A., Paterson, K.G., Smart, N.P., Strefler, M.: On the Joint Security of Encryption and Signature in EMV. CT-RSA. bll. 116–135. Springer (2012).
[ Abstract ] [ Download ]
 
We provide an analysis of current and future algorithms for signature and encryption in the EMV standards in the case where a single key-pair is used for both signature and encryption. We give a theoretical attack for EMV's current RSA-based algorithms, showing how access to a partial decryption oracle can be used to forge a signature on a freely chosen message. We show how the attack might be integrated into EMV's CDA protocol flow, enabling an attacker with a wedge device to complete an offline transaction without knowing the cardholder's PIN. Finally, the elliptic curve signature and encryption algorithms that are likely to be adopted in a forthcoming version of the EMV standards are analyzed in the single key-pair setting, and shown to be secure.

3.
Fischlin, M., Lehmann, A., Schröder, D.: History-Free Sequential Aggregate Signatures. SCN. bll. 113–130. Springer (2012).
[ Abstract ] [ Download ]
 
Aggregation schemes allow to combine several cryptographic values like message authentication codes or signatures into a shorter value such that, despite compression, some notion of unforgeability is preserved. Recently, Eikemeier et al. (SCN 2010) considered the notion of history-free sequential aggregation for message authentication codes, where the sequentially-executed aggregation algorithm does not need to receive the previous messages in the sequence as input. Here we discuss the idea for signatures where the new aggregate does not rely on the previous messages and public keys either, thus inhibiting the costly verifications in each aggregation step as in previous schemes by Lysyanskaya et al. (Eurocrypt 2004) and Neven (Eurocrypt 2008). Analogously to MACs we argue about new security definitions for such schemes and compare them to previous notions for history-dependent schemes. We finally give a construction based on the BLS signature scheme which satisfies our notion.

2011 [ to top ]

1.
Boneh, D., Dagdelen, Özgür, Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random Oracles in a Quantum World. ASIACRYPT. bll. 41–69. Springer (2011).
[ Abstract ] [ Download ]
 
The interest in post-quantum cryptography - classical systems that remain secure in the presence of a quantum adversary - has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum state. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore postquantum secure. We conclude with a rich set of open problems in this area.

2010 [ to top ]

1.
Eikemeier, O., Fischlin, M., Götzmann, J.-F., Lehmann, A., Schröder, D., Schröder, P., Wagner, D.: History-Free Aggregate Message Authentication Codes. SCN. bll. 309–328. Springer (2010).
 

2.
Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., Tessaro, S.: Random Oracles with(out) Programmability. ASIACRYPT. bll. 303–320. Springer (2010).
 

3.
Lehmann, A.: On the security of hash function combiners, (2010).
 

4.
Brzuska, C., Fischlin, M., Lehmann, A., Schröder, D.: Unlinkability of Sanitizable Signatures. Public Key Cryptography. bll. 444–461. Springer (2010).
 

5.
Dagdelen, Özgür, Fischlin, M., Lehmann, A., Schaffner, C.: Random Oracles in a Quantum World. CoRR. abs/1008.0931, (2010).
 

6.
Galindo, D., Libert, B., Fischlin, M., Fuchsbauer, G., Lehmann, A., Manulis, M., Schröder, D.: Public-Key Encryption with Non-Interactive Opening: New Constructions and Stronger Definitions. AFRICACRYPT. bll. 333–350. Springer (2010).
 

7.
Fischlin, M., Lehmann, A.: Delayed-Key Message Authentication for Streams. TCC. bll. 290–307. Springer (2010).
 

8.
Fischlin, M., Lehmann, A., Wagner, D.: Hash Function Combiners in TLS and SSL. CT-RSA. bll. 268–283. Springer (2010).
 

2009 [ to top ]

1.
Lehmann, A., Tessaro, S.: A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical. ASIACRYPT. bll. 364–381. Springer (2009).
 

2.
Brzuska, C., Fischlin, M., Lehmann, A., Schröder, D.: Santizable Signatures: How to Partially Delegate Control for Authenticated Data. BIOSIG. bll. 117–128. GI (2009).
 

3.
Brzuska, C., Fischlin, M., Freudenreich, T., Lehmann, A., Page, M., Schelbert, J., Schröder, D., Volk, F.: Security of Sanitizable Signatures Revisited. Public Key Cryptography. bll. 317–336. Springer (2009).
 

2008 [ to top ]

1.
Fischlin, M., Lehmann, A., Pietrzak, K.: Robust Multi-property Combiners for Hash Functions Revisited. ICALP (2). bll. 655–666. Springer (2008).
 

2.
Fischlin, M., Lehmann, A.: Multi-property Preserving Combiners for Hash Functions. TCC. bll. 375–392. Springer (2008).
 

2007 [ to top ]

1.
Fischlin, M., Lehmann, A.: Security-Amplifying Combiners for Collision-Resistant Hash Functions. CRYPTO. bll. 224–243. Springer (2007).
 

2.
Dönigus, D., Endler, S., Fischlin, M., Hülsing, A., Jäger, P., Lehmann, A., Podrazhansky, S., Schipp, S., Tews, E., Vowe, S., Walthart, M., Weidemann, F.: Security of Invertible Media Authentication Schemes Revisited. Information Hiding. bll. 189–203. Springer (2007).