Paper 2026/1457

IBE and PIR from Isogenies

Abstract

We significantly expand the reach of isogeny-based cryptography by constructing, for the first time, two fundamental primitives that have long remained out of reach from isogenies: identity-based encryption (IBE) and semi-honest single-server private information retrieval (PIR) with communication polylogarithmic in the database size. Our IBE additionally achieves anonymity, which means that the ciphertexts hide both the message and the recipient identity. Our results are enabled by new techniques for constructing cryptographic primitives from structured isogeny computations, centered around the first construction of blind batch encryption from isogenies. To establish its security, we introduce a new hardness assumption, CDH with Mismatched Torsion (CDHwMT), which informally captures the hardness of a CDH-like problem in the presence of structured auxiliary isogeny information. We provide evidence for its plausibility by showing that, in the Algebraic Isogeny Model, CDHwMT reduces to well-studied isogeny assumptions. The same techniques yield further cryptographic applications: the first isogeny-based hierarchical IBE, laconic oblivious transfer, and public-key encryption simultaneously achieving high-rate leakage resilience and key-dependent-message/circular security. All of our constructions can be conjectured to be post-quantum secure. Beyond these individual primitives, our results demonstrate that isogenies can support substantially richer cryptographic functionality than previously known, and provide new tools toward building advanced post-quantum cryptography.

Note: This version of the paper includes a new result, namely the first construction of single-server PIR from isogenies. We also present a more polished exposition of the original result on IBE from isogenies (and associated implications).