Paper 2018/940

Reusable Non-Interactive Secure Computation

Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, and Vinod Vaikuntanathan


We consider the problem of Non-Interactive Secure Computation (NISC), a 2-message ``Sender-Receiver'' secure computation protocol that retains its security even when both parties can be malicious. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice. Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver's first message is reused. Motivated by the failure of the OT-based approach, we consider the problem of basing \emph{reusable} NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results: - We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. As a corollary, we get reusable NISC/OLE for general Boolean circuits using any one-way function. - We complement this by a negative result, showing that reusable NISC/OT is impossible to achieve, and a more restricted negative result for the case of the zero-knowledge functionality. This provides a formal justification for the need to replace OT by OLE. - We build a universally composable 2-message OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008). - By combining our NISC/OLE protocol and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols where following a statement-independent preprocessing, both proving and verifying are entirely ``non-cryptographic'' and involve only a constant computational overhead.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
oblivious transferoblivious linear-function evaluationnon-interactive secure computation
Contact author(s)
liutianren @ gmail com
2018-10-05: received
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Yevgeniy Dodis and Yuval Ishai and Daniel Kraschewski and Tianren Liu and Rafail Ostrovsky and Vinod Vaikuntanathan},
      title = {Reusable Non-Interactive Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/940},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.