Séminaire sécurité du Loria #

Shor’s algorithm (FOCS 1994) is arguably the most powerful application of quantum algorithms to cryptanalysis, as it solves the factoring and discrete logarithm problem in polynomial time. In the past 30 years, many authors have optimized its time complexity (the number of basic operations, also known as quantum gates) and memory footprint (the number of qubits). While quantum computers are still far from running Shor’s algorithm in practice, these fine-grained optimizations improve our understanding of the resources required to do so.

In this talk, I will present a new memory optimization in this algorithm. As in previous works, we focus on the modular exponentiation modulo N, which is its core component. We show that a logarithmic number of work qubits suffices to obtain the least significant bits of the output. We combine this result with May and Schlieper’s truncation technique (ToSC 2022) and the Ekera-Hastad variant of Shor’s algorithm (PQCrypto 2017) to solve the discrete logarithm problem in ℤ_N^* using only d + o(log N) qubits, where d is the bit-size of the logarithm. Consequently we can factor n-bit RSA moduli using n/2 + o(n) qubits, a quarter of the previous most optimized implementations.

This is a joint work with Clémence Chevignard and Pierre-Alain Fouque which was presented at QIP 2025 (https://eprint.iacr.org/2024/222).

Cyber-Physical Systems such as Industrial Control Systems, Drones, and Autonomous Vehicles rely on digital control of a physical process. Adversarial manipulation of such systems can result in physical damage to the system, or the environment. The underlying embedded systems run (often proprietary) firmware on bare metal, interacting with a range of peripherals. Security assessment of such systems by their operators, vendors, and attackers is challenging for various reasons. In this talk, I will go over some of those challenges, and discuss recent ongoing work in the direction of reversing, rehosting, and fuzzing of such systems.

Bio: Nils is a faculty at the CISPA Helmholtz Center for Information Security, heading the SCy-Phy research group. Prior to joining CISPA in 2018, he was an Assistant Professor at the Singapore University of Technology and Design (SUTD). Nils earned his Dr. Sc. in Computer Science from ETH Zurich (Switzerland) in 2012. His research is broadly on information security aspects of practical systems. In particular, he is am currently working on security of cyber-physical systems such as drones, vehicles, and industrial control systems.

Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols.

In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party’s public key.

In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k-40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the-art public-key PCFs.