2024 [ to top ]

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

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

4.
Kroschewski, M., Lehmann, A., Özbay, C.: OPPID: Single Sign-On with Oblivious Pairwise Pseudonyms. Preprint. (2024).
[ 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.

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

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

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

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.

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

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

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

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

2021 [ to top ]

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

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

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

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

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

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

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

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

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

2018 [ to top ]

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

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

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

2017 [ to top ]

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

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

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

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

2016 [ to top ]

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

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

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

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

2015 [ to top ]

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

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

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

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

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

6.
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 ]
 

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

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

2014 [ to top ]

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

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

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

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

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

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.
Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., Tessaro, S.: Random Oracles with(out) Programmability. ASIACRYPT. bll. 303–320. Springer (2010).
 

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

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

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

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

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

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

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

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

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

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

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