International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Round-Optimal Oblivious Transfer and MPC from Computational CSIDH

Authors:
Saikrishna Badrinarayanan , Snap
Daniel Masny , Meta
Pratyay Mukherjee , Supra
Sikhar Patranabis , IBM Research India
Srinivasan Raghuraman , Visa Research
Pratik Sarkar , Boston University
Download:
DOI: 10.1007/978-3-031-31368-4_14
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: We present the first round-optimal and plausibly quantum-safe oblivious transfer (OT) and multi-party computation (MPC) protocols from the computational CSIDH assumption - the weakest and most widely studied assumption in the CSIDH family of isogeny-based assumptions. We obtain the following results: - The first round-optimal maliciously secure OT and MPC protocols in the plain model that achieve (black-box) simulation-based security while relying on the computational CSIDH assumption. - The first round-optimal maliciously secure OT and MPC protocols that achieves Universal Composability (UC) security in the presence of a trusted setup (common reference string plus random oracle) while relying on the computational CSIDH assumption. Prior plausibly quantum-safe isogeny-based OT protocols (with/without setup assumptions) are either not round-optimal, or rely on potentially stronger assumptions. We also build a 3-round maliciously-secure OT extension protocol where each base OT protocol requires only 4 isogeny computations. In comparison, the most efficient isogeny-based OT extension protocol till date due to Lai et al. [Eurocrypt 2021] requires 12 isogeny computations and 4 rounds of communication, while relying on the same assumption as our construction, namely the reciprocal CSIDH assumption.
BibTeX
@inproceedings{pkc-2023-32716,
  title={Round-Optimal Oblivious Transfer and MPC from Computational CSIDH},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-31368-4_14},
  author={Saikrishna Badrinarayanan and Daniel Masny and Pratyay Mukherjee and Sikhar Patranabis and Srinivasan Raghuraman and Pratik Sarkar},
  year=2023
}