Traitor-tracing systems allow identifying the users who contributed to building a rogue decoder in a broadcast environment. In a traditional traitor-tracing system, a key authority is responsible for generating the global public parameters and issuing secret keys to users. All security is lost if the key authority itself is corrupt. This raises the question: Can we construct a traitor-tracing scheme, without a trusted authority? In this work, we propose a new model for traitor-tracing systems where, instead of having a key authority, users could generate and register their own public keys. The public parameters are computed by aggregating all user public keys. Crucially, the aggregation process is public, thus eliminating the need of any trusted authority. We present a new traitor-tracing system in this model based on bilinear pairings. Our scheme is proven adaptively secure in the generic group model. This scheme features a transparent setup, ciphertexts consisting of $6\sqrt{L}+4$ group elements, and a public tracing algorithm. Our main technical ingredient is a new registered functional encryption (RFE) scheme for quadratic functions. This is joint work with Russell W. F. Lai, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi and Ivy K. Y. Woo.

The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petri nets. Existing work primarily considers the case in which both the VASS as well as the initial and target configurations are part of the input. In this talk, we investigate the reachability problem in the setting where the VASS and the final configuration are fixed and only the initial configuration is variable. We show that fixed VASS fully express arithmetic with counting on initial segments of the natural numbers. It follows that there is a very weak reduction from any fixed such number-theoretic predicate (e.g. square-freeness or “N1 is the number of primes smaller than N2”) to reachability in fixed VASS where configurations are presented in unary. If configurations are given in binary, we show that there is a fixed VASS with five counters whose reachability problem is PSPACE-hard.

The problem of Byzantine consensus has been key to designing secure distributed systems. Although it is well known that both safety and liveness are at risk as soon as n/3 Byzantine processes fail, very few works attempted to characterize precisely the faults that produce safety violations from the faults that produce termination violations.We present a new lower bound on the solvability of the consensus problem by distinguishing deceitful faults violating safety and benign faults violating termination from the more general Byzantine faults, in what we call the Byzantine-deceitful-benign fault model. We show that one cannot solve consensus if n≤3t+d+2q with t, d, and q are Byzantine, deceitful, and benign processes. We show that this bound is tight by presenting the Basilic class of consensus protocols that solve consensus when n>3t+d+2q. These protocols differ in the number of processes from which they wait to receive messages before progressing.

Then, we build upon the Basilic class in order to present Zero-Loss Blockchain (ZLB), the first blockchain that tolerates an adversary controlling more than half of the system, with up to less than a third of them Byzantine. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably faulty processes. Interestingly, ZLB does not need a known bound on the delay of messages but progressively reduces the portion of faulty processes below 1/3, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff and is almost as fast as the scalable Red Belly Blockchain that cannot tolerate n/3 faults. These works extend our recent results on the rational model with TRAP, providing safety and liveness even in the presence of a majority of non-rational, faulty participants.

The works presented in this talk comprise three publications, at AsiaCCS’22, CSF’23, and DSN’24 (best paper award)

Approximate fully homomorphic encryption (FHE) schemes such as the CKKS scheme (Asiacrypt ’17) are popular in practice due to their efficiency and utility for machine learning applications. Unfortunately, Li and Micciancio (Eurocrypt, ’21) showed that, while achieving standard semantic (or IND-CPA security), the CKKS scheme is broken under a variant security notion known as IND-CPAD. Subsequently, Li, Micciancio, Schultz, and Sorrell (Crypto ’22) proved the security of the CKKS scheme with a noise-flooding countermeasure, which adds Gaussian noise of sufficiently high variance before outputting the decrypted value. However, the variance required for provable security is very high, inducing a large loss in message precision.

In this work, we ask whether there is an intermediate noise-flooding level, which may not be provably secure, but allows to maintain the performance of the scheme, while resisting known attacks. We analyze the security with respect to different adversarial models and various types of attacks. We investigate the effectiveness of lattice reduction attacks, guessing attacks and hybrid attacks with noise-flooding with variance ρ2circ, the variance of the noise already present in the ciphertext as estimated by an average-case analysis, 100 · ρ2circ, and t · ρ2circ, where t is the number of decryption queries. For noise levels of ρ2circ and 100 · ρ2circ, we find that a full guessing attack is feasible for all parameter sets and circuit types. We find that a lattice reduction attack is the most effective attack for noise-flooding level t · ρ2circ, but it only induces at most a several bit reduction in the security level.

Due to the large dimension and modulus in typical FHE parameter sets, previous techniques even for estimating the concrete security of these attacks – such as those in (Dachman-Soled, Ducas, Gong, Rossi, Crypto ’20) – become computationally infeasible, since they involve high dimensional and high precision matrix multiplication and inversion. We therefore develop new techniques that allow us to perform fast security estimation, even for FHE-size parameter sets.

In this talk I will present the work I have done concerning the specification and analysis of normative documents using deontic-based formalisms. I will also discuss challenges in the area and future research directions, including applications in smart contracts.

Short bio: Gerardo Schneider received a PhD degree in Computer Science from the University Joseph Fourier (thesis done at the VERIMAG laboratory), Grenoble (France), in 2002. From 2003 till 2009 he was a researcher at Uppsala University (Sweden), Irisa/INRIA Rennes (France), and the University of Oslo (Norway). He joined the Department of Computer Science and Engineering at the University of Gothenburg (Sweden) in July 2009, where he has been a full professor since July 2014. He acted as Head of the Formal Methods Division since Jan 2017 till Dec 2023, and since Dec 2023 he has been the head of the Data Science and AI division. His research interests include formal verification, combination of verification techniques (e.g., static and runtime verification, controller synthesis and runtime verification), the specification and analysis of normative documents, and privacy. (http://www.cse.chalmers.se/~gersch).