Cryptology ePrint Archive: Report 2021/700

DeCSIDH: Delegating isogeny computations in the CSIDH setting

Robi Pedersen

Abstract: Delegating heavy computations to auxiliary servers, while keeping the inputs secret, presents a practical solution for computationally limited devices to use resource-intense cryptographic protocols, such as those based on isogenies, and thus allows the deployment of post-quantum security on mobile devices and in the internet of things. We propose two algorithms for the secure and verifiable delegation of isogeny computations in the CSIDH setting. We then apply these algorithms to different instances of CSIDH and to the signing algorithms SeaSign and CSI-FiSh. Our algorithms present a communication-cost trade-off. Asymptotically (for high communication), the cost for the delegator is reduced by a factor $9$ for the original CSIDH-512 parameter set and a factor $20$ for SQALE'd CSIDH-4096, while the relative cost of SeaSign vanishes. Even for much lower communication cost, we come close to these asymptotic results. Using the knowledge of the class group, the delegation of CSI-FiSh is basically free (up to element generation in $\mathbb{Z}_{\#\text{Cl}(\mathcal{O})}$) already at a very low communication cost.

Category / Keywords: public-key cryptography / Post-quantum cryptography, Isogeny-based cryptography, CSIDH, Secure computation outsourcing, Lightweight cryptography

Date: received 27 May 2021

Contact author: robi pedersen at protonmail com

Available format(s): PDF | BibTeX Citation

Version: 20210528:091540 (All versions of this report)

Short URL: ia.cr/2021/700


[ Cryptology ePrint archive ]