Article

Efficient Pseudorandom Correlation Generators from Ring-LPN

Authors:

Geoffroy Couteau,

Peter SchollAuthors Info & Claims

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II

Pages 387 - 416

https://doi.org/10.1007/978-3-030-56880-1_14

Published: 17 August 2020 Publication History

Abstract

Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only “silent” local computation. This is achieved via a pseudorandom correlation generator (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency.

In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.

References

[1]

Aguilar-Melchor C, Barrier J, Guelton S, Guinet A, Killijian M-O, and Lepoint T Sako K NFLlib: NTT-based fast lattice library Topics in Cryptology - CT-RSA 2016 2016 Cham Springer 341-356

[2]

Applebaum B, Cash D, Peikert C, and Sahai A Halevi S Fast cryptographic primitives and circular-secure encryption based on hard learning problems Advances in Cryptology - CRYPTO 2009 2009 Heidelberg Springer 595-618

[3]

Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., Santini, P.: Design of LEDAkem and LEDApkc instances with tight parameters and bounded decryption failure rate (2019). https://www.ledacrypt.org/archives/official_comment.pdf

[4]

Beaver D Feigenbaum J Efficient multiparty protocols using circuit randomization Advances in Cryptology — CRYPTO 1991 1992 Heidelberg Springer 420-432

[5]

Ben-Efraim A, Nielsen M, and Omri E Deng RH, Gauthier-Umaña V, Ochoa M, and Yung M Turbospeedz: double your online SPDZ! improving SPDZ using function dependent preprocessing Applied Cryptography and Network Security 2019 Cham Springer 530-549

[6]

Bendlin R, Damgård I, Orlandi C, and Zakarias S Paterson KG Semi-homomorphic encryption and multiparty computation Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 169-188

[7]

Bernstein DJ and Lange T Hoepman J-H and Verbauwhede I Never trust a bunny Radio Frequency Identification. Security and Privacy Issues 2013 Heidelberg Springer 137-148

[8]

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

[9]

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: ACM CCS 2018, pp. 896–912. ACM Press (2018)

[10]

Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: ACM CCS 2019, pp. 291–308. ACM Press (2019)

[11]

Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Boldyreva A and Micciancio D Efficient pseudorandom correlation generators: silent OT extension and more Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 489-518

[12]

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Orrù, M.: Homomorphic secret sharing: optimizations and applications. In: ACM CCS 2017, pp. 2105–2122. ACM Press (2017)

[13]

Boyle E, Gilboa N, and Ishai Y Oswald E and Fischlin M Function secret sharing Advances in Cryptology - EUROCRYPT 2015 2015 Heidelberg Springer 337-367

[14]

Boyle E, Gilboa N, and Ishai Y Robshaw M and Katz J Breaking the circuit size barrier for secure computation under DDH Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 509-539

[15]

Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: ACM CCS 2016, pp. 1292–1303. ACM Press (2016)

[16]

Boyle E, Gilboa N, and Ishai Y Coron J-S and Nielsen JB Group-based secure computation: optimizing rounds, communication, and computation Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 163-193

[17]

Boyle E, Gilboa N, and Ishai Y Hofheinz D and Rosen A Secure computation with preprocessing via function secret sharing Theory of Cryptography 2019 Cham Springer 341-371

[18]

Boyle E, Kohl L, and Scholl P Ishai Y and Rijmen V Homomorphic secret sharing from lattices without FHE Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 3-33

[19]

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97–106. IEEE Computer Society Press, October 2011

[20]

Brakerski Z and Vaikuntanathan V Rogaway P Fully homomorphic encryption from ring-LWE and security for key dependent messages Advances in Cryptology – CRYPTO 2011 2011 Heidelberg Springer 505-524

[21]

Couteau G Ishai Y and Rijmen V A note on the communication complexity of multiparty computation in the correlated randomness model Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 473-503

[22]

Damgård I, Keller M, Larraia E, Pastro V, Scholl P, and Smart NP Crampton J, Jajodia S, and Mayes K Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits Computer Security – ESORICS 2013 2013 Heidelberg Springer 1-18

[23]

Damgård I, Nielsen JB, Nielsen M, and Ranellucci S Katz J and Shacham H The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 167-187

[24]

Damgård, I., Park, S.: How practical is public-key encryption based on LPN and ring-LPN? Cryptology ePrint Archive, Report 2012/699 (2012). http://eprint.iacr.org/2012/699

[25]

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

[26]

Debris-Alazard, T., Tillich, J.P.: Statistical decoding. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1798–1802. IEEE (2017)

[27]

Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: ACM CCS 2017, pp. 523–535. ACM Press (2017)

[28]

Gilboa N and Ishai Y Nguyen PQ and Oswald E Distributed point functions and their applications Advances in Cryptology – EUROCRYPT 2014 2014 Heidelberg Springer 640-658

[29]

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

[30]

Guo Q, Johansson T, and Löndahl C A new algorithm for solving ring-LPN with a reducible polynomial IEEE Trans. Inf. Theory 2015 61 11 6204-6212

[31]

Hazay, C., Ishai, Y., Marcedone, A., Venkitasubramaniam, M.: LevioSA: lightweight secure arithmetic computation. In: ACM CCS 2019, pp. 327–344. ACM Press (2019)

[32]

Heyse S, Kiltz E, Lyubashevsky V, Paar C, and Pietrzak K Canteaut A Lapin: an efficient authentication protocol based on ring-LPN Fast Software Encryption 2012 Heidelberg Springer 346-365

[33]

Ishai Y, Kushilevitz E, Meldgaard S, Orlandi C, and Paskin-Cherniavsky A Sahai A On the power of correlated randomness in secure computation Theory of Cryptography 2013 Heidelberg Springer 600-620

[34]

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Batch codes and their applications. In: Babai, L. (ed.) 36th ACM STOC, pp. 262–271. ACM Press, June 2004

[35]

Ishai Y, Prabhakaran M, and Sahai A Wagner D Founding cryptography on oblivious transfer – efficiently Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 572-591

[36]

Ishai Y, Prabhakaran M, and Sahai A Reingold O Secure arithmetic computation with no honest majority Theory of Cryptography 2009 Heidelberg Springer 294-314

[37]

Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.: GAZELLE: a low latency framework for secure neural network inference. In: USENIX 2018, pp. 1651–1669 (2018)

[38]

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: ACM CCS 2016, pp. 830–842. ACM Press (2016)

[39]

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

[40]

Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC, pp. 20–31. ACM Press, May 1988

[41]

Kolesnikov V, Sadeghi A-R, and Schneider T Garay JA, Miyaji A, and Otsuka A Improved garbled circuit building blocks and applications to auctions and computing minima Cryptology and Network Security 2009 Heidelberg Springer 1-20

[42]

Lipmaa H and Pavlyk K Reiter M and Naccache D Analysis and implementation of an efficient ring-LPN based commitment scheme Cryptology and Network Security 2015 Cham Springer 160-175

[43]

Lyubashevsky V, Peikert C, and Regev O Johansson T and Nguyen PQ A toolkit for ring-LWE cryptography Advances in Cryptology – EUROCRYPT 2013 2013 Heidelberg Springer 35-54

[44]

Melchor CA, Blazy O, Deneuville J, Gaborit P, and Zémor G Efficient encryption from random quasi-cyclic codes IEEE Trans. Inf. Theory 2018 64 5 3927-3943

[45]

Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: 31st ACM STOC, pp. 245–254. ACM Press, May 1999

[46]

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

[47]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, May 2005

[48]

Schoppmann, P., Gascón, A., Reichert, L., Raykova, M.: Distributed vector-OLE: improved constructions and implementation. In: ACM CCS 2019, pp. 1055–1072. ACM Press (2019)

[49]

Smart NP and Vercauteren F Fully homomorphic simd operations Des. Codes Cryptogr. 2014 71 1 57-81

Cited By

Baum CMelissaris NRachuri RScholl P(2024)Cheater Identification on a Budget: MPC with Identifiable Abort from Pairwise MACsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_14(454-488)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_14
Esser ASantini P(2024)Not Just Regular Decoding: Asymptotics and Improvements of Regular Syndrome Decoding AttacksAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_6(183-217)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_6
Dao QJain A(2024)Lossy Cryptography from Code-Based AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_2(34-75)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_2
Show More Cited By

Recommendations

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More
Advances in Cryptology – CRYPTO 2019
Abstract
Secure multiparty computation (MPC) often relies on correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-...
More efficient DDH pseudorandom generators

In this paper, we first show a DDH Lemma, which states that a multi-variable version of the decisional Diffie---Hellman problem is hard under the standard DDH assumption, where the group size is not necessarily known. Our proof, based on a self-...
Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN
Advances in Cryptology – CRYPTO 2023
Abstract
The recent development of pseudorandom correlation generators (PCG) holds tremendous promise for highly efficient MPC protocols. Among other correlations, PCGs allow for the efficient generation of oblivious transfer (OT) and vector oblivious ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II

Aug 2020

864 pages

ISBN:978-3-030-56879-5

DOI:10.1007/978-3-030-56880-1

Editors:
Daniele Micciancio
UC San Diego, La Jolla, CA, USA
,
Thomas Ristenpart
Cornell Tech, New York, NY, USA

© International Association for Cryptologic Research 2020.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2020

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Baum CMelissaris NRachuri RScholl P(2024)Cheater Identification on a Budget: MPC with Identifiable Abort from Pairwise MACsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_14(454-488)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_14
Esser ASantini P(2024)Not Just Regular Decoding: Asymptotics and Improvements of Regular Syndrome Decoding AttacksAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_6(183-217)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_6
Dao QJain A(2024)Lossy Cryptography from Code-Based AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_2(34-75)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_2
Liu HWang XYang KYu Y(2024)The Hardness of LPN over Any Integer Ring and Field for PCG ApplicationsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_6(149-179)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_6
Branco PDöttling NSrinivasan A(2024)Two-Round Maliciously-Secure Oblivious Transfer with Optimal RateAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_10(271-300)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_10
Hazay CYang Y(2024)Toward Malicious Constant-Rate 2PC via Arithmetic GarblingAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_14(401-431)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_14
Baum CDittmer SScholl PWang X(2023)Sok: vector OLE-based zero-knowledge protocolsDesigns, Codes and Cryptography10.1007/s10623-023-01292-891:11(3527-3561)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1007/s10623-023-01292-8
Bombar MCouvreur ADebris-Alazard T(2023)Pseudorandomness of Decoding, Revisited: Adapting OHCP to Code-Based CryptographyAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_9(253-283)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8739-9_9
Branco PDöttling NSrinivasan A(2023)A Framework for Statistically Sender Private OT with Optimal RateAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38557-5_18(548-576)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38557-5_18
Ishai YKelkar MNarayanan VZafar L(2023)One-Message Secure Reductions: On the Cost of Converting CorrelationsAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38557-5_17(515-547)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38557-5_17
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents