Abstracts

"On the Limits of Unbounded Updatable Encryption from LWE and PCE"

Martin Albrecht (King’s College London and SandboxAQ)

Updatable Public-Key Encryption (UPKE) enables forward secrecy in asynchronous settings, such as secure group messaging, by allowing public keys to be updated while ensuring ciphertexts encrypted under old keys remain secure even if the new secret key is leaked. While existing lattice-based constructions achieve UPKE via noisy linear shifts, these accumulate noise over time, necessitating super-polynomial moduli or restricting the number of updates. In this talk, I will talk about a construction based on lattice-problems and permutation code equivalence that supports an unbounded number of updates using polynomial-size moduli (EC'25). Inspired by works on the lattice isomorphism problem, our scheme rotates keys rather than shifting them, avoiding norm growth and noise accumulation. I will then also discuss limitations of this approach. In particular, I will discuss its limits, notably that there seems to be little hope for a Module-LWE style variant.

"MinRank based cryptography"

Philippe Gaborit (University of Limoges)

Rank metric based crypto with rank metric codes has been known for more than 30 years and reached the second round of the NIST competition. Because of its stronger complexity it has the potential to reach far smaller parameters sizes than Hamming metric. The main decoding tools for this metric are the Gabidulin codes, however their very rich structure make them difficult to hide and hence it is difficult to reach the promise they hold for obtaining very small ciphertext (like the MacEliece scheme) or signature (like the CFS scheme) sizes.

The MinRank problem corresponds to a matrix-code version of rank metric and is based on matrices over GF(p) rather on codes over extension GF(p^m). When one looses on the sizes of the public key one benefits from a less structured problem which makes matrix-codes version of Gabidulin codes easier to hide.

Until recently the MinRank problem had been used only for ZK based signature, first in 2001 by Courtois and more recently with an MPC-in-the-head based approach and the MIRATH protocol (qualified for the second round of the NIST PQC signature competition), but until recently nothing was known for encryption or full domain hash signature.

In this talk we will present recent new schemes based on the MinRank problem: a MacEliece-like encryption scheme and a full domain hash signature (Miranda), these schemes propose very small ciphertext and signature sizes, which can be as low as 60 Bytes. We will also present a very recent algorithm which introduces an encryption scheme "à la Aleknovich" for the MinRank problem which does not require any masking and is comparable in size to the Frodo lattice-based scheme. All these schemes have in common to propose a different trade-off than classical rank metric codes, with very small ciphertext or signature sizes but bigger public key sizes, and based on a less structured problem. All these new features make them very appealing for code-based cryptography.