Paper 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 30 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) already at a very low communication cost.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision.Indocrypt 2021
Keywords
Post-quantum cryptographyIsogeny-based cryptographyCSIDHSecure computation outsourcingLightweight cryptography
Contact author(s)
robi pedersen @ protonmail com
History
2022-01-04: last of 3 revisions
2021-05-28: received
See all versions
Short URL
https://ia.cr/2021/700
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/700,
      author = {Robi Pedersen},
      title = {DeCSIDH: Delegating isogeny computations in the CSIDH setting},
      howpublished = {Cryptology ePrint Archive, Paper 2021/700},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/700}},
      url = {https://eprint.iacr.org/2021/700}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.