Aalto computer scientists in IEEE S&P 2025
The IEEE Symposium on Security and Privacy is the premier forum for presenting developments in the field of computer security and electronic privacy. The symposium is sponsored by the IEEE Computer Society's Technical Community on Security and Privacy and organized in cooperation with International Association for Cryptologic Research.
The 46th IEEE Symposium on Security and Privacy is held on 12-14 May 2025 in San Francisco, California, USA.
Accepted papers
In alphabetical order. Click the title to see the authors and the abstract.
Authors
Michał Osadnik, Darya Kaviani, Valerio Cini, Russell W. F. Lai, and Giulio Malavolta
Abstract
A verifiable delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today's hardware. As an example, our Papercraft implementation can verify a computation of almost 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment.
Authors
Cecilia Boschini, Darya Kaviani, Russell Lai, Giulio Malavolta, Akira Takahashi, and Mehdi Tibouchi
Abstract
A threshold signature scheme splits the signing key among l parties, such that any t-subset of parties can jointly generate signatures on a given message. Designing concretely efficient post-quantum threshold signatures is a pressing question, as evidenced by NIST's recent call.In this work, we propose, implement, and evaluate a lattice-based threshold signature scheme, Ringtail, which is the first to achieve a combination of desirable properties: 1) The signing protocol consists of only two rounds, where the first round is message-independent and can thus be preprocessed offline. 2) The scheme is concretely efficient and scalable to t <= 1024 parties. For 128-bit security and t = 1024 parties, we achieve 13.4 KB signature size and 10.5 KB of online communication. 3) The security is based on the standard learning with errors (LWE) assumption in the random oracle model. This improves upon the state-of-the-art which either has a three-round signing protocol (Eurocrypt'24) or relies on a new non-standard assumption (Crypto'24). To substantiate the practicality of our scheme, we conduct the first WAN experiment deploying lattice-based threshold signatures, across 8 countries in 5 continents. We observe that an overwhelming majority of the end-to-end latency is consumed by network latency, underscoring the need for round-optimized schemes.
Department of Computer Science
We are an internationally-oriented community and home to world-class research in modern computer science.
School of Science
Science for tomorrow’s technology, innovations and businesses
Read more news
Time crystals could power future quantum computers
A time crystal, a long-life quantum system approaching perpetual motion, has been hooked up to its environment for the first time, unlocking an intriguing way to increase quantum computational and sensing power.
Glitch artwork challenges to see art in a different light
Laura Könönen's sculpture was unveiled on 14 October at the Otaniemi campus.
Nanoparticles in Functional Textiles
Dr. Md. Reazuddin Repon, Postdoctoral Researcher at the Textile Chemistry Group, Department of Bioproducts and Biosystems, Aalto University, has contributed as an editor to a newly published academic volume titled “Nanoparticles Integrated Functional Textiles”.