Cryptology ePrint Archive: Report 2021/1470

Concurrent-Secure Two-Party Computation in Two Rounds from Subexponential LWE

Saikrishna Badrinarayanan and Rex Fernando and Amit Sahai

Abstract: Very recently, two works were able to construct two-round secure multi-party computation (MPC) protocols in the plain model, without setup, relying on the superpolynomial simulation framework of Pass [Pas03]. The first work [ABG+21] achieves this relying on subexponential non-interactive witness indistinguishable arguments, the subexponential SXDH assumption, and the existence of a special type of non-interactive non-malleable commitment. The second work [FJK21] additionally achieves concurrent security, and relies on subexponential quantum hardness of the learning-with-errors (LWE) problem, subexponential classical hardness of SXDH, the existence of a subexponentially-secure (classically-hard) indistinguishablity obfuscation (iO) scheme, and time-lock puzzles.

This paper focuses on the assumptions necessary to construct secure computation protocols in two rounds without setup, focusing on the subcase of two-party functionalities. In this particular case, we show how to build a two-round, concurrent-secure, two-party computation (2PC) protocol based on a single, standard, post-quantum assumption, namely subexponential hardness of the learning-with-errors (LWE) problem.

We note that our protocol is the first two-round concurrent-secure 2PC protocol that does not require the existence of a one-round non-malleable commitment (NMC). Instead, we are able to use the two-round NMCs of [KS17a], which is instantiable from subexponential LWE.

Category / Keywords: cryptographic protocols / two-party computation, learning with errors

Date: received 3 Nov 2021

Contact author: bsaikrishna7393 at gmail com, rex1fernando at gmail com, amitsahai at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211106:155159 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]