1.
Klooß, M., Lehmann, A., Rupp, A.: (R)CCA Secure Updatable Encryption with Integrity Protection. EUROCRYPT (1). bll. 68–99. Springer (2019).
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).
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).
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).
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).
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).
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).