Cryptology ePrint Archive: Report 2020/411

Secure Two-Party Computation in a Quantum World

Niklas Büscher and Daniel Demmler and Nikolaos P. Karvelas and Stefan Katzenbeisser and Juliane Krämer and Deevashwer Rathee and Thomas Schneider and Patrick Struck

Abstract: Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were shown to be secure in the classical setting, but are not known to be secure against quantum adversaries. In this work, we start to pave the way for secure two-party computation in a quantum world where the adversary has access to a quantum computer. We show that post-quantum secure two-party computation has comparable efficiency to their classical counterparts. For this, we develop a lattice-based OT protocol which we use to implement a post-quantum secure variant of Yao's famous garbled circuits (GC) protocol (FOCS'82). Along with the OT protocol, we show that the oblivious transfer extension protocol of Ishai et al. (CRYPTO'03), which allows running many OTs using mainly symmetric cryptography, is post-quantum secure. To support these results, we prove that Yao's GC protocol achieves post-quantum security if the underlying building blocks do.

Category / Keywords: cryptographic protocols / Post-quantum security, Yao’s GC protocol, Oblivious transfer, Secure two-party computation, Homomorphic encryption

Original Publication (with major differences): 18th International Conference on Applied Cryptography and Network Security (ACNS 2020)

Date: received 11 Apr 2020, last revised 25 Aug 2020

Contact author: demmler at informatik uni-hamburg de, deevashwer student cse15@iitbhu ac in, patrick struck@tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20200825:102634 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]