Research

Contents

• Cryptography
• Privacy-Enhancing Technologies
• Cryptanalysis
• Usability

Cryptography

We work on several aspects of both foundational and applied cryptography. On the foundational side, we have worked on leakage-resilient and non-malleable cryptography, secure multiparty computation, and the hardness of coding and lattice problems underlying post-quantum cryptography. With respect to applications, we have worked on protocols for building private data aggregation and private data retrieval protocols.

Selected recent works

• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all $\ell_p$ norms, Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro (STOC 2023).
• FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval, Alex Davidson, Gonçalo Pestana, Sofía Celi (PoPETS 2023).
• STAR: Secret Sharing for Private Threshold Aggregation Reporting, Alex Davidson, Peter Snyder, E. B. Quirk, Joseph Genereux, Benjamin Livshits, Hamed Haddadi (ACM CCS 2022).
• Adversarial Correctness and Privacy for Probabilistic Data Structures, Mia Filić, Kenneth G. Paterson, Anupama Unnikrishnan, Fernando Virdia (ACM CCS 2022).
• Public randomness extraction with ephemeral roles and worst-case corruptions, Jesper Buus Nielsen, João Ribeiro, Maciej Obremski (random author ordering) (CRYPTO 2022).
• The mother of all leakages: How to simulate noisy leakages via bounded leakage (almost) for free, Gianluca Brian, Antonio Faonio, Maciej Obremski, João Ribeiro, Mark Simkin, Maciej Skórski, Daniele Venturi (Eurocrypt 2021 & IEEE Trans. Inf. Theory 2022).
• Round-optimal verifiable oblivious pseudorandom functions from ideal lattices, Martin R Albrecht, Alex Davidson, Amit Deo, Nigel P Smart (PKC 2021).
• Adaptively secure constrained pseudorandom functions in the standard model, Alex Davidson, Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa (CRYPTO 2020).

Privacy-Enhancing Technologies

Our work on privacy-enhancing technologies develops and implements anonymity systems and Internet protocols that preserve human user privacy, while they navigate the online world.

Selected recent works

• Enhancing the Unlinkability of Circuit-Based Anonymous Communications with k-Funnels, Vitor Nunes, José Brás, Afonso Carvalho, Diogo Barradas, Kevin Gallagher, Nuno Santos (CoNEXT 2023).
• Rethinking Realistic Adversaries for Anonymous Communication Systems, Kevin Gallagher, Diogo Barradas, Nuno Santos, Free and Open Communications on the Internet 2023 (FOCI 2023).
• Privacy Pass: Bypassing Internet Challenges Anonymously, Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda (PoPETS 2018).

Cryptanalysis

At the core of any guarantee of security offered by a cryptographic primitive, is the hardness of some mathematical problem. Regardless of whether this hardness is computational or information-theoretic, it should be argued and analysed in detail. Cryptanalysis is the study of the hardness of cryptographic mathematical problems.

Selected recent works

• Quantum Lattice Enumeration in Limited Depth, Nina Bindel, Xavier Bonnetain, Marcel Tiepelt, Fernando Virdia (in submission).
• Popping “R-propping”: breaking hardness assumptions for matrix groups over F_{2^8}, Fernando Virdia (Mathematical Cryptology, 3(1)).
• On the Success Probability of Solving Unique SVP via BKZ, Eamonn W. Postlethwaite, Fernando Virdia (PKC 2021)
• Implementing Grover oracles for quantum key search on AES and LowMC, Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia (Eurocrypt 2020).
• (One) failure is not an option: Bootstrapping the search for failures in lattice-based encryption schemes, Jan-Pieter D’Anvers, Mélissa Rossi, Fernando Virdia (Eurocrypt 2020).
• Improved Classical Cryptanalysis of SIKE in Practice, Craig Costello, Patrick Longa, Michael Naehrig, Joost Renes, Fernando Virdia (PKC 2020).
• Estimate All the {LWE, NTRU} Schemes!, Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, Thomas Wunderer (SCN 2018).

Usability

Usability is a core concept in the development and implementation of security systems, when unintended applications or users of systems can reveal security failures. We survey and work with real human users to design, build, and implement security systems, where ease-of-use is a critical part of the system design.

Selected recent works

• Can Deepfakes be created on a whim?, Pulak Metha, Gauri Japtap, Kevin Gallagher, Brian Timmerman, Progga Deb, Siddharth Garg, Rachel Greenstadt, Brendan Dolan-Gavitt, Fourth International Workshop on Cyber Social Threats (CySoc 2023).
• Tango or square dance? how tightly should we integrate network functionality in browsers?, Alex Davidson, Matthias Frei, Marten Gartner, Hamed Haddadi, A Perrig, J Subirà Nieto, Philipp Winter, François Wirz (ACM HotNets 2022)
• Let The Right One In: Attestation as a Usable CAPTCHA Alternative, Tara Whalen, Thibault Meunier, Mrudula Kodali, Alex Davidson, Marwan Fayed, Armando Faz-Hernández, Watson Ladd, Deepak Maram, Nick Sullivan, Benedikt Christoph Wolters, Maxime Guerreiro, and Andrew Galloni (SOUPS 2022).