Paper 2026/054

Communication and Storage-Friendly Bidirectional Multi-hop CPA Secure Proxy Re-encryption from Supersingular Isogenies

Abstract

$\textit{Proxy re-encryption}$ (PRE) is an essential cryptographic primitive for managing secure access delegation in outsourced data environments, particularly public cloud systems. PRE is a public key encryption (PKE) with two additional algorithms - (i) re-encryption key generation by which a proxy server generates a re-encryption key; (ii) re-encryption algorithm by which the proxy server can transform the ciphertext under the delegator's public key to a ciphertext under the delegatee's public key enabling the delegatee to decrypt the message originally intended for the delegator. With the advent of quantum computing, a pressing need arises to design PRE schemes based on quantum-resistant assumptions. This paper addresses this requirement by presenting the first construction of a bidirectional PRE ($\mathsf{bPRE}$) from supersingular isogenies. Our $\mathsf{bPRE}$ is built upon the commutative supersingular isogeny-based PKE scheme $\mathsf{MSimS}$, a variant of the isogeny-based PKE scheme $\mathsf{SimS}$ and achieves security against $\textit{chosen-plaintext attack}$ (CPA) in the standard model under the hardness of the commutative supersingular isogeny decisional Diffie-Hellman (CSSIDDH) problem. The resultant $\mathsf{bPRE}$ supports efficient re-encryption of ciphertexts by the proxy server for the delegator as well as the delegatee and inherits the multi-hop property, enabling chainable delegation of access rights. Significantly, our isogeny-based $\mathsf{bPRE}$ is asymptotically efficient, offering an efficient reduction in bandwidth consumption compared to current lattice-based proposals in terms of key size and ciphertext size. This makes the scheme a highly compact and practical candidate for post-quantum cloud security. Furthermore, our PKE scheme $\mathsf{MSimS}$ is of independent interest which is proven to be CPA secure under the hardness of the CSSIDDH problem and secure against chosen ciphertext attack (CCA) under the hardness of the CSSIDDH problem and the commutative supersingular isogeny knowledge of exponent (CSSIKOE) problem.