Article

Post-Quantum Multi-Party Computation

Authors:

James Bartusek,

Dakshita Khurana,

Giulio MalavoltaAuthors Info & Claims

Advances in Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I

Pages 435 - 464

https://doi.org/10.1007/978-3-030-77870-5_16

Published: 17 October 2021 Publication History

Abstract

We initiate the study of multi-party computation for classical functionalities in the plain model, with security against malicious quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of constant-round post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest:

•

A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of (a circular variant of) the LWE problem. This immediately yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys.

•

A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

To prove the security of our protocol, we develop a new straight-line non-black-box simulation technique against parallel sessions that does not clone the adversary’s state. This technique may also be relevant to the classical setting.

References

[1]

Ananth, P., Placa, R.L.L.: Secure quantum extraction protocols. Cryptology ePrint Archive, Report 2019/1323 (2019). https://eprint.iacr.org/2019/1323

[2]

Asharov G et al. Pointcheval D, Johansson T, et al. Multiparty computation with low communication, computation and interaction via threshold FHE Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 483-501

Digital Library

[3]

Badrinarayanan S, Fernando R, Jain A, Khurana D, and Sahai A Canteaut A and Ishai Y Statistical ZAP arguments Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 642-667

Digital Library

[4]

Barak B Constant-round coin-tossing with a man in the middle or realizing the shared random string model FOCS 2002 2002 345-355

[5]

Ben-Or, M., Crépeau, C., Gottesman, D., Hassidim, A., Smith, A.: Secure multiparty quantum computation with (only) a strict honest majority. In: 47th FOCS, pp. 249–260. IEEE Computer Society Press, Berkeley, CA, USA, 21–24 October 2006.

Digital Library

[6]

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1–10. ACM Press, Chicago, IL, USA, 2–4 May 1988.

Digital Library

[7]

Benhamouda F and Lin H Nielsen JB and Rijmen V k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 500-532

[8]

Bitansky, N., Khurana, D., Paneth, O.: Weak zero-knowledge beyond the black-box barrier. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23–26 June 2019, pp. 1091–1102 (2019).

Digital Library

[9]

Bitansky N and Lin H Beimel A and Dziembowski S One-message zero knowledge and non-malleable commitments Theory of Cryptography 2018 Cham Springer 209-234

Digital Library

[10]

Bitansky, N., Shmueli, O.: Post-quantum zero knowledge in constant rounds. In: STOC (2020)

[11]

Brakerski Z Shacham H and Boldyreva A Quantum FHE (Almost) as secure as classical Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 67-95

Digital Library

[12]

Brakerski Z, Halevi S, and Polychroniadou A Kalai Y and Reyzin L Four round secure computation without setup Theory of Cryptography 2017 Cham Springer 645-677

Digital Library

[13]

Broadbent A and Jeffery S Gennaro R and Robshaw M Quantum homomorphic encryption for circuits of low T-gate complexity Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 609-629

Digital Library

[14]

Chaum D, Crépeau C, and Damgård I Pomerance C Multiparty unconditionally secure protocols (abstract) Advances in Cryptology — CRYPTO 1987 1988 Heidelberg Springer 462-462

[15]

Chor, B., Rabin, M.: Achieving independence in logarithmic number of rounds, pp. 260–268 (1987).

Digital Library

[16]

Ciampi M, Ostrovsky R, Siniscalchi L, and Visconti I Robshaw M and Katz J Concurrent non-malleable commitments (and more) in 3 rounds Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 270-299

Digital Library

[17]

Ciampi M, Ostrovsky R, Siniscalchi L, and Visconti I Katz J and Shacham H Four-round concurrent non-malleable commitments from one-way functions Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 127-157

[18]

Clear M and McGoldrick C Gennaro R and Robshaw M Multi-identity and multi-key leveled FHE from learning with errors Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 630-656

Digital Library

[19]

Crépeau, C., Gottesman, D., Smith, A.: Secure multi-party quantum computation. In: 34th ACM STOC, pp. 643–652. ACM Press, Montréal, Québec, Canada, 19–21 May 2002.

Digital Library

[20]

Damgård I and Lunemann C Matsui M Quantum-secure coin-flipping and applications Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 52-69

Digital Library

[21]

Dodis Y, Halevi S, Rothblum RD, and Wichs D Robshaw M and Katz J Spooky encryption and its applications Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 93-122

Digital Library

[22]

Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography (extended abstract). In: STOC 1991 (1991)

[23]

Dulek Y, Grilo AB, Jeffery S, Majenz C, and Schaffner C Canteaut A and Ishai Y Secure multi-party quantum computation with a dishonest majority Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 729-758

Digital Library

[24]

Dulek Y, Schaffner C, and Speelman F Robshaw M and Katz J Quantum homomorphic encryption for polynomial-sized circuits Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 3-32

Digital Library

[25]

Dupuis F, Nielsen JB, and Salvail L Rabin T Secure two-party quantum evaluation of unitaries against specious adversaries Advances in Cryptology – CRYPTO 2010 2010 Heidelberg Springer 685-706

[26]

Dupuis F, Nielsen JB, and Salvail L Safavi-Naini R and Canetti R Actively secure two-party evaluation of any quantum operation Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 794-811

Digital Library

[27]

Garg S, Mukherjee P, Pandey O, and Polychroniadou A Fischlin M and Coron J-S The exact round complexity of secure computation Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 448-476

[28]

Garg S and Srinivasan A Nielsen JB and Rijmen V Two-round multiparty secure computation from minimal assumptions Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 468-499

[29]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, Bethesda, MD, USA, 31 May - 2 Jun 2009.

Digital Library

[30]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC. pp. 197–206. ACM Press, Victoria, BC, Canada, 17–20 May 2008.

Digital Library

[31]

Gentry C, Sahai A, and Waters B Canetti R and Garay JA Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 75-92

[32]

Goldreich O and Kahan A How to construct constant-round zero-knowledge proof systems for NP J. Cryptology 1996 9 3 167-190

Digital Library

[33]

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or Aa completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, New York City, NY, USA, 25–27 May 1987.

Digital Library

[34]

Goyal, R.: Quantum multi-key homomorphic encryption for polynomial-sized circuits. Cryptology ePrint Archive, Report 2018/443 (2018). https://eprint.iacr.org/2018/443

[35]

Goyal, R., Koppula, V., Waters, B.: Lockable obfuscation. In: Umans, C. (ed.) 58th FOCS, pp. 612–621. IEEE Computer Society Press, Berkeley, CA, USA, 15–17 October 2017.

[36]

Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 695–704. ACM Press, San Jose, CA, USA, 6–8 Jun 2011.

Digital Library

[37]

Goyal, V., Lee, C.K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: FOCS (2012)

[38]

Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: STOC, pp. 1128–1141. ACM, New York, NY, USA (2016).

Digital Library

[39]

Goyal, V., Richelson, S.: Non-malleable commitments using Goldreich-Levin list decoding. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, 9–12 November 2019, pp. 686–699. IEEE Computer Society (2019).

[40]

Goyal V, Richelson S, Rosen A, and Vald M An algebraic approach to non-malleability FOCS 2014 2014 41-50

Digital Library

[41]

Hallgren S, Smith A, and Song F Rogaway P Classical cryptographic protocols in a quantum world Advances in Cryptology – CRYPTO 2011 2011 Heidelberg Springer 411-428

[42]

Kalai YT, Khurana D, and Sahai A Nielsen JB and Rijmen V Statistical witness indistinguishability (and more) in two messages Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 34-65

[43]

Katz J, Ostrovsky R, and Smith A Biham E Round efficiency of multi-party computation with a dishonest majority Advances in Cryptology — EUROCRYPT 2003 2003 Heidelberg Springer 578-595

[44]

Khurana D Kalai Y and Reyzin L Round optimal concurrent non-malleability from polynomial hardness Theory of Cryptography 2017 Cham Springer 139-171

Digital Library

[45]

Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15–17 October 2017, pp. 564–575. IEEE Computer Society (2017).

[46]

Lin, H., Pass, R.: Non-malleability amplification. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 189–198. STOC 2009 (2009)

[47]

Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 705–714. ACM Press, San Jose, CA, USA, 6–8 Jun 2011.

Digital Library

[48]

Lin H, Pass R, and Venkitasubramaniam M Canetti R Concurrent non-malleable commitments from any one-way function Theory of Cryptography 2008 Heidelberg Springer 571-588

[49]

Lindell Y Parallel coin-tossing and constant-round secure two-party computation J. Cryptology 2003 16 3 143-184

[50]

López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Karloff, H.J., Pitassi, T. (eds.) 44th ACM STOC, pp. 1219–1234. ACM Press, New York, NY, USA, 19–22 May 2012.

Digital Library

[51]

Lunemann C and Nielsen JB Nitaj A and Pointcheval D Fully simulatable quantum-secure coin-flipping and applications Progress in Cryptology – AFRICACRYPT 2011 2011 Heidelberg Springer 21-40

[52]

Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th FOCS, pp. 332–338. IEEE Computer Society Press, Paris, France, 7–9 October 2018).

[53]

Mukherjee P and Wichs D Fischlin M and Coron J-S Two round multiparty computation via multi-key FHE Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 735-763

[54]

Pandey O, Pass R, and Vaikuntanathan V Wagner D Adaptive one-way functions and applications Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 57-74

Digital Library

[55]

Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Babai, L. (ed.) 36th ACM STOC, pp. 232–241. ACM Press, Chicago, IL, USA, 13–16 Jun 2004.

Digital Library

[56]

Pass, R., Rosen, A.: Concurrent Non-Malleable Commitments. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of ComputerScience, pp. 563–572. FOCS 2005 (2005)

[57]

Pass R and Rosen A New and improved constructions of nonmalleable cryptographic protocols SIAM J. Comput. 2008 38 2 702-752

Digital Library

[58]

Pass R and Wee H Gilbert H Constant-round non-malleable commitments from sub-exponential one-way functions Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 638-655

Digital Library

[59]

Peikert C and Shiehian S Hirt M and Smith A Multi-key FHE from LWE, revisited Theory of Cryptography 2016 Heidelberg Springer 217-238

Digital Library

[60]

Peikert C and Shiehian S Boldyreva A and Micciancio D Noninteractive zero knowledge for NP from (plain) learning with errors Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 89-114

Digital Library

[61]

Peikert C, Vaikuntanathan V, and Waters B Wagner D A framework for efficient and composable oblivious transfer Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 554-571

Digital Library

[62]

Unruh D Pointcheval D and Johansson T Quantum proofs of knowledge Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 135-152

Digital Library

[63]

Van De Graaf, J.: Towards a Formal Definition of Security for Quantum Protocols. Ph.D. thesis, CAN (1998), aAINQ35648

[64]

Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009).

Digital Library

[65]

Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: 51st FOCS, pp. 531–540. IEEE Computer Society Press, Las Vegas, NV, USA, 23–26 October 2010.

Digital Library

[66]

Wichs, D., Zirdelis, G.: Obfuscating compute-and-compare programs under LWE. In: Umans, C. (ed.) 58th FOCS, pp. 600–611. IEEE Computer Society Press, Berkeley, CA, USA, 15–17 October 2017.

[67]

Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160–164. IEEE Computer Society Press, Chicago, Illinois, 3–5 November 1982.

[68]

Yao, A.C.C.: How to generate and exchange secrets. In: FOCS (1986)

Cited By

Goyal VMalavolta GRaizes J(2024)Unclonable Commitments and ProofsTheory of Cryptography10.1007/978-3-031-78020-2_7(193-224)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_7
Goyal VLiang XMalavolta G(2023)On Concurrent Multi-party Quantum ComputationAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_5(129-161)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38554-4_5
Chia NChung KLiang XYamakawa T(2022)Post-quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-RoundAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_18(533-563)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15982-4_18
Show More Cited By

Recommendations

Round-Optimal Secure Multi-party Computation
Abstract
Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of an active (i.e. malicious)...
Everlasting Multi-party Computation

A protocol has everlasting security if it is secure against adversaries that are computationally unlimited after the protocol execution. This models the fact that we cannot predict which cryptographic schemes will be broken, say, several decades after ...
On Concurrent Multi-party Quantum Computation
Advances in Cryptology – CRYPTO 2023
Abstract
Recently, significant progress has been made toward quantumly secure multi-party computation (MPC) in the stand-alone setting. In sharp contrast, the picture of concurrently secure MPC (or even 2PC), for both classical and quantum functionalities, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I

Oct 2021

848 pages

ISBN:978-3-030-77869-9

DOI:10.1007/978-3-030-77870-5

Editors:
Anne Canteaut
Inria, Paris, France
,
François-Xavier Standaert
UCLouvain, Louvain-la-Neuve, Belgium

© International Association for Cryptologic Research 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 October 2021

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goyal VMalavolta GRaizes J(2024)Unclonable Commitments and ProofsTheory of Cryptography10.1007/978-3-031-78020-2_7(193-224)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_7
Goyal VLiang XMalavolta G(2023)On Concurrent Multi-party Quantum ComputationAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_5(129-161)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38554-4_5
Chia NChung KLiang XYamakawa T(2022)Post-quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-RoundAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_18(533-563)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15982-4_18
Austrin PChung HChung KFu SLin YMahmoody M(2022)On the Impossibility of Key Agreements from Quantum Random OraclesAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_6(165-194)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_6
Chatterjee RChung KLiang XMalavolta G(2022)A Note on the Post-quantum Security of (Ring) SignaturesPublic-Key Cryptography – PKC 202210.1007/978-3-030-97131-1_14(407-436)Online publication date: 8-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-97131-1_14
Bartusek J(2021)Secure Quantum Computation with Classical CommunicationTheory of Cryptography10.1007/978-3-030-90459-3_1(1-30)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90459-3_1
Bartusek JColadangelo AKhurana DMa F(2021)On the Round Complexity of Secure Quantum ComputationAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84242-0_15(406-435)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84242-0_15

View Options

View options

Figures

Tables

Media

View Table of Conten