Paper 2018/457

From FE Combiners to Secure MPC and Back

Prabhanjan Ananth, Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai


Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure. Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results. 1) A two round semi-honest MPC protocol in the plain model secure against up to (n-1) corruptions with communication complexity proportional only to the depth of the circuit being computed assuming LWE. Prior two round protocols that achieved this communication complexity required a common reference string. 2) A functional encryption combiner based on pseudorandom generators (PRGs) in NC^1. Such PRGs can be instantiated from assumptions such as DDH and LWE. Previous constructions of FE combiners were known only from the learning with errors assumption. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption based only on the assumptions that functional encryption exists and PRGs in NC^1.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
MPCCommunication efficiencyFE combiners.
Contact author(s)
prabhanjan va @ gmail com
bsaikrishna7393 @ gmail com
aayushjainiitd @ gmail com
njmanohar @ gmail com
amitsahai @ gmail com
2018-11-27: revised
2018-05-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Saikrishna Badrinarayanan and Aayush Jain and Nathan Manohar and Amit Sahai},
      title = {From FE Combiners to Secure MPC and Back},
      howpublished = {Cryptology ePrint Archive, Paper 2018/457},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.