Abstract: Advanced Public-Key Encryption schemes broaden the usability of cryptographic primitives, granting for instance primitives to obliviously perform operations on hidden data, and to scale schemes up for applications in large organizations. In contexts in which users are not necessarily synchronized nor always available, developing non-interactive schemes becomes the most attractive solution; moreover, avoiding interactions with a central server in large sets of users also brings the benefit of weakening such an entity's power.

Several challenges arise with these cutting-edge features: when allowing the combination of private data from several sources to be decrypted, the class of authorized computations should be carefully monitored, as when the scheme or security model are too lenient, the confidential information issued from a source can be uncovered.

When scaling encryption schemes for a usage among a large community, the question emerging most naturally is the one of efficiency, both in the case where messages should be issued to subsets of members, or to individual ones, while avoiding interactions with a central server, and potentially reducing its capabilities when it is necessary during a setup phase.

This thesis endeavors to overcome these obstacles, for specific types of computations or communication patterns among many participants. First, two contributions will show constructions improving on current security models, making them suitable for realistic applications, in the case of two specific types of calculations. Then, another two will grant schemes for efficient encryption in large groups of users (without relying on a central server), with convenient effective sizes and computation times, and up-to-date security models with respect to the latest expectations in the state-of-the-art.

Abstract: PKI schemes provide a critical foundation for applied cryptographic protocols. However, there are no rigorous security specifications for realistic PKI schemes, and therefore, no PKI schemes were proven secure. Cryptographic systems that use PKI are analyzed by adopting overly simplified models of the PKI, often, simply assuming secure public keys. This is problematic considering the extensive reliance on PKI, the multiple failures of PKI systems, and the fact that proposed and deployed PKI are complex, have complex requirements and assume complex models.

We present game-based security specifications for PKI schemes, and analyse important, widely deployed PKIs: PKIX and two variants of Certificate Transparency (CT). All PKIs are based on the X.509v3 standard and its CRL revocation mechanism. Our analysis identified few subtle vulnerabilities, and includes reduction-based proofs showing that the PKIs ensure specific requirements under specific models (assumptions).To our knowledge, this is the first reduction-based definition and proof of security for a realistic PKI scheme.

Our specifications and analysis use the Modular Security Specifications (MoSS) framework [Crypto'21]. The talk will explain the relevant aspects of MoSS. We may briefly discuss the extensions that allow provably-secure compositions of protocols.

Joint work with Sara Wrotniak, Hemi Leibowitz and Ewa Syta.

Article link: https://eprint.iacr.org/2019/807

Abstract: Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC'14), sign vectors of elements from a bilinear group. Signatures can be ``adapted'', meaning that anyone can transform a signature on a vector to a (random) signature on any multiple of that vector. (Signatures thus authenticate equivalence classes.) A transformed signature/message pair is then indistinguishable from a random signature on a random message. EQS have been used to efficiently instantiate (delegatable) anonymous credentials, (round-optimal) blind signatures, ring and group signatures and anonymous tokens.

Unforgeability of the original EQS construction is proven directly in the generic group model. While there are constructions from standard assumptions, these either achieve prohibitively weak security notions (PKC'18) or they require a common reference string (AC'19, PKC'22), which reintroduces trust assumptions avoided by EQS.

In this work we ask whether EQS schemes that satisfy the original security model can be proved secure under standard (or even non-interactive) assumptions with standard techniques. Our answer is negative: assuming a reduction that, after running once an adversary breaking unforgeability, breaks a non-interactive computational assumption, we construct efficient meta-reductions that either break the assumption or break class-hiding, another security requirement for EQS.

Joint work with Balthazar Bauer and Fabian Regen.

Article link: https://www.iacr.org/cryptodb//data/paper.php?pubkey=33792

The presentation may also cover another recent work on EQS: https://eprint.iacr.org/2024/183

Abstract: Credential tweaking attacks use breached passwords to generate semantically similar passwords and gain access to victims' services. These attacks sidestep the first generation of compromised credential checking (C3) services. The second generation of compromised credential checking services, called "Might I Get Pwned" (MIGP), is a privacy-preserving protocol that defends against credential tweaking attacks by allowing clients to query whether a password or a semantically similar variation is present in the server's compromised credentials dataset. The desired privacy requirements include not revealing the user's entered password to the server and ensuring that no compromised credentials are disclosed to the client.

In this work, we formalize the cryptographic leakage of the MIGP protocol and perform a security analysis to assess its impact on the credentials held by the server. We focus on how this leakage aids breach extraction attacks, where an honest-but-curious client interacts with the server to extract information about the stored credentials. Furthermore, we discover additional leakage that arises from the implementation of Cloudflare's deployment of MIGP. We evaluate how the discovered leakage affects the guessing capability of an attacker in relation to breach extraction attacks. Finally, we propose MIGP 2.0, a new iteration of the MIGP protocol designed to minimize data leakage and prevent the introduced attacks.

Joint work with Dario Pasquini (EPFL), Danilo Francati (Aarhus University), Giuseppe Ateniese (George Mason University), to appear at S&P 2024.

Article link: https://eprint.iacr.org/2023/1848

Abstract: Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations.

In this work, we propose a novel framework that realizes VE protocols using zero-knowledge proof systems based on the MPC-in-the-head paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zero-knowledge proofs into secure VE protocols for any secure public-key encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme.

Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with post-quantum security, along with an implementation and benchmarks.

This is joint work with Akira Takahashi.