Logic, Theoretical Computer Science
and Cryptography

Universal hashing is a standard tool for extending keyed functions on fixed-length inputs to variable-length messages, notably in message authentication. It can provide efficient compression with information-theoretic bounds on collision probabilities.

This talk presents the key-then-hash approach to constructing universal hash functions from public functions. We will first consider constructions based on public permutations and explain how their concrete properties yield universality guarantees without relying on an ideal-permutation model. We will then generalize these techniques to non-invertible public functions, examining which properties are needed to preserve these guarantees.

Among square quadratic systems over F₂, those with exactly one solution outnumber those with none — by one part in 2ⁿ, at every n, the opposite of the linear case. We give an explicit O(n³) injection from most solution-free systems to uniquely solvable ones, and read it against coNP, DP, NP and the planted-MQ assumption of post-quantum cryptography.

Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt ’22) allows private communication in a challenging setting where encryption is severely controlled by a central authority (henceforth the dictator) who can demand the users to surrender their secret keys. Anamorphic Signatures (AS) (Kutylowski, Persiano, Phan, Yung, Zawada, Crypto ’23) face the even more restrictive world where only authentication is allowed but users still want to send secret messages despite the repressive control of the dictator holding their signing key. Several constructions have been proposed so far, but they all come with some limitations.

In this talk, I will introduce the main ideas behind Anamorphic Encryption and Signatures and present my recent work on Anamorphic Secret Sharing Signatures (ASSS), a new flexible setting where digital signatures are used to covertly embed secret shares which t out of N designated receivers can combine to recover a covert secret. We formalize this new primitive together with new robustness, forward secrecy, and private unforgeability notions and give a construction for Schnorr-like signatures overcoming the limitations of previous constructions. ASSS additionally imply regular single-receiver AS, but two signatures (instead of one) are needed to recover the covert message.