More Web Proxy on the site http://driver.im/

Article

Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits

Authors:

Aner Ben-Efraim,

Emmanuela Orsini,

Nigel P. Smart,

Eduardo Soria-VazquezAuthors 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 III

Pages 33 - 63

https://doi.org/10.1007/978-3-030-77883-5_2

Published: 17 October 2021 Publication History

Abstract

We (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity O(n) per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue we present a second protocol that assumes at least n/c of the parties are honest (for an arbitrary fixed value c). This second protocol allows for a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our evaluation phase with an implementation.

References

[1]

Applebaum B Sahai A Garbling XOR gates “For Free” in the standard model Theory of Cryptography 2013 Heidelberg Springer 162-181

Digital Library

[2]

Applebaum, B., Harnik, D., Ishai, Y.: Semantic security under related-key attacks and applications. In: Chazelle, B. (ed.) ICS 2011, pp. 45–60. Tsinghua University Press, January 2011

[3]

Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503–513. ACM Press, May 1990

[4]

Bellare M and Kohno T Biham E A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications Advances in Cryptology — EUROCRYPT 2003 2003 Heidelberg Springer 491-506

[5]

Ben-Efraim, A., Lindell, Y., Omri, E.: Optimizing semi-honest secure multiparty computation for the internet. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 578–590. ACM Press, October 2016

[6]

Ben-Efraim A, Lindell Y, and Omri E Takagi T and Peyrin T Efficient scalable constant-round MPC via garbled circuits Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 471-498

[7]

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, May 1988

[8]

Bertoni G, Daemen J, Peeters M, Van Assche G, Van Keer R, and Viguier B Preneel B and Vercauteren F KangarooTwelve: fast hashing based on Keccak-p Applied Cryptography and Network Security 2018 Cham Springer 400-418

Digital Library

[9]

Black J, Rogaway P, and Shrimpton T Nyberg K and Heys H Encryption-scheme security in the presence of key-dependent messages Selected Areas in Cryptography 2003 Heidelberg Springer 62-75

[10]

Blum A, Furst M, Kearns M, and Lipton RJ Stinson DR Cryptographic primitives based on hard learning problems Advances in Cryptology — CRYPTO’ 93 1994 Heidelberg Springer 278-291

[11]

Camenisch J and Lysyanskaya A Pfitzmann B An efficient system for non-transferable anonymous credentials with optional anonymity revocation Advances in Cryptology — EUROCRYPT 2001 2001 Heidelberg Springer 93-118

[12]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001

[13]

Cramer R, Damgård I, Escudero D, Scholl P, and Xing C Shacham H and Boldyreva A SPD

Z_{2^{k}}

: efficient MPC mod

2^{k}

for dishonest majority Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 769-798

Digital Library

[14]

Damgård I and Nielsen JB Menezes A Scalable and unconditionally secure multiparty computation Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 572-590

[15]

Damgård I, Pastro V, Smart N, and Zakarias S Safavi-Naini R and Canetti R Multiparty computation from somewhat homomorphic encryption Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 643-662

Digital Library

[16]

Esser A, Kübler R, and May A Katz J and Shacham H LPN decoded Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 486-514

[17]

Frederiksen TK, Keller M, Orsini E, and Scholl P Iwata T and Cheon JH A unified approach to MPC with preprocessing using OT Advances in Cryptology – ASIACRYPT 2015 2015 Heidelberg Springer 711-735

Digital Library

[18]

Goldreich O, Krawczyk H, and Luby M Goldwasser S On the existence of pseudorandom generators Advances in Cryptology — CRYPTO’ 88 1990 New York Springer 146-162

[19]

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

[20]

Hazay C, Orsini E, Scholl P, and Soria-Vazquez E Peyrin T and Galbraith S Concretely efficient large-scale MPC with active security (or, TinyKeys for TinyOT) Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 86-117

Digital Library

[21]

Hazay C, Orsini E, Scholl P, and Soria-Vazquez E Shacham H and Boldyreva A TinyKeys: a new approach to efficient multi-party computation Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 3-33

Digital Library

[22]

Hazay C, Scholl P, and Soria-Vazquez E Takagi T and Peyrin T Low cost constant round MPC combining BMR and oblivious transfer Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 598-628

[23]

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st FOCS, pp. 294–304. IEEE Computer Society Press, November 2000

[24]

Ishai Y and Kushilevitz E Widmayer P, Eidenbenz S, Triguero F, Morales R, Conejo R, and Hennessy M Perfect constant-round secure computation via perfect randomizing polynomials Automata, Languages and Programming 2002 Heidelberg Springer 244-256

[25]

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 830–842. ACM Press, October 2016

[26]

Keller M, Pastro V, and Rotaru D Nielsen JB and Rijmen V Overdrive: making SPDZ great again Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 158-189

[27]

Kolesnikov V and Schneider T Aceto L, Damgård I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, and Walukiewicz I Improved garbled circuit: free XOR gates and applications Automata, Languages and Programming 2008 Heidelberg Springer 486-498

Digital Library

[28]

Larraia E, Orsini E, and Smart NP Garay JA and Gennaro R Dishonest majority multi-party computation for binary circuits Advances in Cryptology – CRYPTO 2014 2014 Heidelberg Springer 495-512

[29]

Lindell Y, Pinkas B, Smart NP, and Yanai A Gennaro R and Robshaw M Efficient constant round multi-party computation combining BMR and SPDZ Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 319-338

Digital Library

[30]

Lindell Y, Smart NP, and Soria-Vazquez E Hirt M and Smith A More efficient constant-round multi-party computation from BMR and SHE Theory of Cryptography 2016 Heidelberg Springer 554-581

Digital Library

[31]

Matsui M Helleseth T Linear cryptanalysis method for DES cipher Advances in Cryptology — EUROCRYPT ’93 1994 Heidelberg Springer 386-397

[32]

Maurer U Knudsen LR Indistinguishability of random systems Advances in Cryptology — EUROCRYPT 2002 2002 Heidelberg Springer 110-132

[33]

Nielsen JB, Nordholt PS, Orlandi C, and Burra SS Safavi-Naini R and Canetti R A new approach to practical active-secure two-party computation Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 681-700

Digital Library

[34]

NIST National Institute for Standards and Technology: SHA-3 derived functions: cSHAKE, KMAC, TupleHash and ParallelHash (2016). http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf

[35]

NIST National Institute for Standards and Technology: Recommendation for key derivation through extraction- then-expansion rev.1 (2018). https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-56c.pdf

[36]

Orsini E, Smart NP, and Vercauteren F Jarecki S Overdrive2k: efficient secure MPC over

Z_{2^{k}}

from somewhat homomorphic encryption Topics in Cryptology – CT-RSA 2020 2020 Cham Springer 254-283

Digital Library

[37]

Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC, pp. 73–85. ACM Press, May 1989

[38]

Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 21–37. ACM Press, October/November 2017

[39]

Wang, X., Ranellucci, S., Katz, J.: Global-scale secure multiparty computation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 39–56. ACM Press, October/November 2017

[40]

Yang, K., Wang, X., Zhang, J.: More efficient MPC from improved triple generation and authenticated garbling. Cryptology ePrint Archive, Report 2019/1104 (2019). https://eprint.iacr.org/2019/1104

[41]

Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986

Cited By

Goyal VLi JMisra AOstrovsky RSong YWeng C(2024)Dishonest Majority Constant-Round MPC with Linear Communication from DDHAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_6(167-199)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_6
Beck GGoel AHegde AJain AJin ZKaptchuk GMeng WJensen CCremers CKirda E(2023)Scalable Multiparty GarblingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623132(2158-2172)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623132
Ning JTan Z(2023)Geometry-Based Garbled Circuits Relying Solely on One Evaluation Algorithm Under Standard AssumptionInformation Security and Cryptology10.1007/978-981-97-0942-7_10(183-202)Online publication date: 9-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-97-0942-7_10

Recommendations

Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain Model
Theory of Cryptography
Abstract
We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao’s protocol for ...
Efficient secure computation with garbled circuits
ICISS'11: Proceedings of the 7th international conference on Information Systems Security

Secure two-party computation enables applications in which participants compute the output of a function that depends on their private inputs, without revealing those inputs or relying on any trusted third party. In this paper, we show the potential of ...
Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently
CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) ...

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 III

Oct 2021

589 pages

ISBN:978-3-030-77882-8

DOI:10.1007/978-3-030-77883-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

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goyal VLi JMisra AOstrovsky RSong YWeng C(2024)Dishonest Majority Constant-Round MPC with Linear Communication from DDHAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_6(167-199)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_6
Beck GGoel AHegde AJain AJin ZKaptchuk GMeng WJensen CCremers CKirda E(2023)Scalable Multiparty GarblingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623132(2158-2172)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623132
Ning JTan Z(2023)Geometry-Based Garbled Circuits Relying Solely on One Evaluation Algorithm Under Standard AssumptionInformation Security and Cryptology10.1007/978-981-97-0942-7_10(183-202)Online publication date: 9-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-97-0942-7_10

View Options

View options

Figures

Tables

Media

View Table of Conten