Two-Round Adaptively Secure MPC from Isogenies, LPN, or CDH

Navid Alamati; Hart Montgomery; Sikhar Patranabis; Pratik Sarkar

Paper 2023/1170

Two-Round Adaptively Secure MPC from Isogenies, LPN, or CDH

Navid Alamati, Visa Research

Hart Montgomery, Linux Foundation

Sikhar Patranabis, IBM Research India

Pratik Sarkar, Boston University

Abstract

We present a new framework for building round-optimal (two-round) $a d a p t i v e l y$ secure MPC. We show that a relatively weak notion of OT that we call $i n d i s t i n g u i s h a b i l i t y O T w i t h r e c e i v e r o b l i v i o u s s a m p l e a b i l i t y$ (r-iOT) is enough to build two-round, adaptively secure MPC against $m a l i c i o u s$ adversaries in the CRS model. We then show how to construct r-iOT from CDH, LPN, or isogeny-based assumptions that can be viewed as group actions (such as CSIDH and CSI-FiSh). This yields the first constructions of two-round adaptively secure MPC against malicious adversaries from CDH, LPN, or isogeny-based assumptions. We further extend our non-isogeny results to the plain model, achieving (to our knowledge) the first construction of two-round adaptively secure MPC against semi-honest adversaries in the plain model from LPN. Our results allow us to build a two-round adaptively secure MPC against malicious adversaries from essentially all of the well-studied assumptions in cryptography. In addition, our constructions from isogenies or LPN provide the first post-quantum alternatives to LWE-based constructions for round-optimal adaptively secure MPC. Along the way, we show that r-iOT also implies non-committing encryption(NCE), thereby yielding the first constructions of NCE from isogenies or LPN.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in ASIACRYPT 2021
Keywords: Adaptive Security MPC Oblivious Transfer Post-Quantum Security
Contact author(s): alamati @ gmail com
hart montgomery @ gmail com
sikharpatranabis @ gmail com
pratik93 @ bu edu
History: 2023-07-30: approved; 2023-07-29: received; See all versions
Short URL: https://ia.cr/2023/1170
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1170,
      author = {Navid Alamati and Hart Montgomery and Sikhar Patranabis and Pratik Sarkar},
      title = {Two-Round Adaptively Secure {MPC} from Isogenies, {LPN}, or {CDH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1170},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1170}
}