Article

Round-Optimal Oblivious Transfer and MPC from Computational CSIDH

Authors:

Saikrishna Badrinarayanan,

Pratyay Mukherjee,

Sikhar Patranabis,

Srinivasan Raghuraman,

Pratik SarkarAuthors Info & Claims

Public-Key Cryptography – PKC 2023: 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7–10, 2023, Proceedings, Part I

Pages 376 - 405

https://doi.org/10.1007/978-3-031-31368-4_14

Published: 07 May 2023 Publication History

Abstract

We present the first round-optimal and plausibly quantum-safe oblivious transfer (OT) and multi-party computation (MPC) protocols from the computational CSIDH assumption – the weakest and most widely studied assumption in the CSIDH family of isogeny-based assumptions. We obtain the following results:

•

The first round-optimal maliciously secure OT and MPC protocols in the plain model that achieve (black-box) simulation-based security while relying on the computational CSIDH assumption.

•

The first round-optimal maliciously secure OT and MPC protocols that achieves Universal Composability (UC) security in the presence of a trusted setup (common reference string plus random oracle) while relying on the computational CSIDH assumption.

Prior plausibly quantum-safe isogeny-based OT protocols (with/without setup assumptions) are either not round-optimal, or rely on potentially stronger assumptions.

We also build a 3-round maliciously-secure OT extension protocol where each base OT protocol requires only 4 isogeny computations. In comparison, the most efficient isogeny-based OT extension protocol till date due to Lai et al. [Eurocrypt 2021] requires 12 isogeny computations and 4 rounds of communication, while relying on the same assumption as our construction, namely the reciprocal CSIDH assumption.

References

[1]

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

[2]

Albrecht MR, Davidson A, Deo A, and Smart NP Garay JA Round-optimal verifiable oblivious pseudorandom functions from ideal lattices Public-Key Cryptography – PKC 2021 2021 Cham Springer 261-289

[3]

Alamati N, De Feo L, Montgomery H, and Patranabis S Moriai S and Wang H Cryptographic group actions and applications Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 411-439

[4]

Abdalla M, Eisenhofer T, Kiltz E, Kunzweiler S, and Riepel D Dodis Y and Shrimpton T Password-authenticated key exchange from group actions Advances in Cryptology – CRYPTO 2022 2022 Cham Springer 699-728

[5]

Alamati N, Montgomery H, Patranabis S, and Sarkar P Tibouchi M and Wang H Two-round adaptively secure MPC from isogenies, LPN, or CDH Advances in Cryptology – ASIACRYPT 2021 2021 Cham Springer 305-334

[6]

Booher, J., et al.: Failing to hash into supersingular isogeny graphs. Cryptology ePrint Archive, Paper 2022/518 (2022). https://eprint.iacr.org/2022/518

[7]

Brakerski Z and Döttling N Beimel A and Dziembowski S Two-message statistically sender-private OT from LWE Theory of Cryptography 2018 Cham Springer 370-390

[8]

Büscher N et al. Conti M, Zhou J, Casalicchio E, Spognardi A, et al. Secure two-party computation in a quantum world Applied Cryptography and Network Security 2020 Cham Springer 461-480

[9]

Beullens, W., Dobson, S., Katsumata, S., Lai, Y.-F., Pintore, F.: Group signatures and more from isogenies and lattices: generic, simple, and efficient. 13276, 95–126 (2022)

[10]

Bitansky N and Freizeit S Dodis Y and Shrimpton T Statistically sender-private OT from LPN and derandomization Advances in Cryptology – CRYPTO 2022 2022 Cham Springer 699-728

[11]

Badrinarayanan S, Goyal V, Jain A, Kalai YT, Khurana D, and Sahai A Shacham H and Boldyreva A Promise zero knowledge and its applications to round optimal MPC Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 459-487

[12]

Basso A, Kutas P, Merz S-P, Petit C, and Sanso A Tibouchi M and Wang H Cryptanalysis of an oblivious PRF from supersingular isogenies Advances in Cryptology – ASIACRYPT 2021 2021 Cham Springer 160-184

[13]

Beullens W, Kleinjung T, and Vercauteren F Galbraith SD and Moriai S CSI-FiSh: efficient isogeny based signatures through class group computations Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 227-247

[14]

Boneh D, Kogan D, and Woo K Moriai S and Wang H Oblivious Pseudorandom Functions from Isogenies Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 520-550

[15]

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

[16]

Badrinarayanan, S., Masny, D., Mukherjee, P., Patranabis, S., Raghuraman, S., Sarkar, P.: Round-optimal oblivious transfer and MPC from computational CSIDH. IACR Cryptology ePrint Archive, p. 1511 (2022). https://eprint.iacr.org/2022/1511

[17]

Barreto, P., Oliveira, G., Benits, W.: Supersingular isogeny oblivious transfer. Cryptology ePrint Archive, Report 2018/459 (2018). https://eprint.iacr.org/2018/459

[18]

Badrinarayanan S, Patranabis S, and Sarkar P Kiltz E and Vaikuntanathan V Statistical security in two-party computation revisited Theory of Cryptography 2022 Cham Springer 181-210

[19]

Brassard G and Yung M Menezes AJ and Vanstone SA One-way group actions Advances in Cryptology-CRYPT0’ 90 1991 Heidelberg Springer 94-107

[20]

Rai Choudhuri A, Ciampi M, Goyal V, Jain A, and Ostrovsky R Pass R and Pietrzak K Round optimal secure multiparty computation from minimal assumptions Theory of Cryptography 2020 Cham Springer 291-319

[21]

Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1082–1090. ACM Press, June 2019

[22]

Castryck, W., Decru, T.: An efficient key recovery attack on SIDH (preliminary version). IACR Cryptology ePrint Archive, p. 975 (2022). https://eprint.iacr.org/2022/975

[23]

Castryck W, Lange T, Martindale C, Panny L, and Renes J Peyrin T and Galbraith S CSIDH: an efficient post-quantum commutative group action Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 395-427

[24]

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, pp. 494–503. ACM Press, May 2002

[25]

Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291

[26]

Castryck W, Panny L, and Vercauteren F Canteaut A and Ishai Y Rational isogenies from irrational endomorphisms Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 523-548

[27]

Castryck W, Sotáková J, and Vercauteren F Micciancio D and Ristenpart T Breaking the decisional Diffie-Hellman problem for class group actions using genus theory Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 92-120

[28]

Canetti R, Sarkar P, and Wang X Kiayias A, Kohlweiss M, Wallden P, and Zikas V Blazing fast OT for three-round UC OT extension Public-Key Cryptography – PKC 2020 2020 Cham Springer 299-327

[29]

Canetti R, Sarkar P, and Wang X Moriai S and Wang H Efficient and round-optimal oblivious transfer and commitment with adaptive security Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 277-308

[30]

Canetti R, Sarkar P, and Wang X Agrawal S and Lin D Triply adaptive UC NIZK Advances in Cryptology – ASIACRYPT 2022 2022 Cham Springer 466-495

[31]

De Feo L and Galbraith SD Ishai Y and Rijmen V SeaSign: compact isogeny signatures from class group actions Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 759-789

[32]

Döttling N, Garg S, Hajiabadi M, Masny D, and Wichs D Canteaut A and Ishai Y Two-round oblivious transfer from CDH or LPN Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 768-797

[33]

De Feo L, Masson S, Petit C, and Sanso A Galbraith SD and Moriai S Verifiable delay functions from supersingular isogenies and pairings Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 248-277

[34]

David BM, Nascimento ACA, and Müller-Quade J Smith A Universally composable oblivious transfer from lossy encryption and the McEliece assumptions Information Theoretic Security 2012 Heidelberg Springer 80-99

[35]

de Saint Guilhem CD, Orsini E, Petit C, and Smart NP Krenn S, Shulman H, and Vaudenay S Semi-commutative masking: a framework for isogeny-based protocols, with an application to fully secure two-round isogeny-based OT Cryptology and Network Security 2020 Cham Springer 235-258

[36]

Dowsley R, van de Graaf J, Müller-Quade J, and Nascimento ACA Safavi-Naini R Oblivious transfer based on the McEliece assumptions Information Theoretic Security 2008 Heidelberg Springer 107-117

[37]

Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO’82, pp. 205–210. Plenum Press, New York (1982)

[38]

Feige U, Lapidot D, and Shamir A Multiple noninteractive zero knowledge proofs under general assumptions SIAM J. Comput. 1999 29 1 1-28

[39]

Friolo D, Masny D, and Venturi D Hofheinz D and Rosen A A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement Theory of Cryptography 2019 Cham Springer 111-130

[40]

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

[41]

Ishai Y, Kushilevitz E, Ostrovsky R, Prabhakaran M, and Sahai A Paterson KG Efficient non-interactive secure computation Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 406-425

[42]

Jarecki S and Liu X Reingold O Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection Theory of Cryptography 2009 Heidelberg Springer 577-594

[43]

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

[44]

Khurana D and Mughees MH Pass R and Pietrzak K On statistical security in two-party computation Theory of Cryptography 2020 Cham Springer 532-561

[45]

Keller M, Orsini E, and Scholl P Gennaro R and Robshaw M Actively secure OT extension with optimal overhead Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 724-741

[46]

Lai Y-F, Galbraith SD, and Delpech de Saint Guilhem C Canteaut A and Standaert F-X Compact, efficient and UC-secure isogeny-based oblivious transfer Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 213-241

[47]

McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Coding Thv 4244, 114–116 (1978)

[48]

Maino, L., Martindale, C.: An attack on SIDH with arbitrary starting curve. IACR Cryptology ePrint Archive, p. 1026 (2022). https://eprint.iacr.org/2022/1026

[49]

Mula, M., Murru, N., Pintore, F.: On random sampling of supersingular elliptic curves. Cryptology ePrint Archive, Paper 2022/528 (2022). https://eprint.iacr.org/2022/528

[50]

Masny, D., Rindal, P.: Endemic oblivious transfer. In: ACM CCS 2019, pp. 309–326. ACM Press (2019)

[51]

Petit C Takagi T and Peyrin T Faster algorithms for isogeny problems using torsion point images Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 330-353

[52]

Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: 43rd FOCS, pp. 366–375. IEEE Computer Society Press, November 2002

[53]

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

[54]

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

[55]

Quach W Galdi C and Kolesnikov V UC-secure OT from LWE, revisited Security and Cryptography for Networks 2020 Cham Springer 192-211

[56]

Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005/187 (2005). https://eprint.iacr.org/2005/187

[57]

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

[58]

Robert, D.: Breaking SIDH in polynomial time. Cryptology ePrint Archive, Paper 2022/1038 (2022). https://eprint.iacr.org/2022/1038

[59]

Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124–134. IEEE Computer Society Press, November 1994

[60]

Vitse, V.: Simple oblivious transfer protocols compatible with kummer and supersingular isogenies. Cryptology ePrint Archive, Report 2018/709 (2018). https://eprint.iacr.org/2018/709

[61]

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

Delpech de Saint Guilhem CPedersen R(2024)New Proof Systems and an OPRF from CSIDHPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_8(217-251)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_8
Galbraith SLai YMontgomery H(2024)A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group ActionsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_2(36-60)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_2
Basso AChen MFouotsa TKutas PLaval AMarco LSaah G(2024)Exploring SIDH-Based Signature ParametersApplied Cryptography and Network Security10.1007/978-3-031-54770-6_17(432-456)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_17
Show More Cited By

Recommendations

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
Abstract
In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round ...
$_{}$
Two-Round MPC: Information-Theoretic and Black-Box
Theory of Cryptography
Abstract
We continue the study of protocols for secure multiparty computation (MPC) that require only two rounds of interaction. The recent works of Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) essentially settle the ...
Three-Round Secure Multiparty Computation from Black-Box Two-Round Oblivious Transfer
Advances in Cryptology – CRYPTO 2021
Abstract
We give constructions of three-round secure multiparty computation (MPC) protocols for general functions that make black-box use of a two-round oblivious transfer (OT). For the case of semi-honest adversaries, we make use of a two-round, semi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Public-Key Cryptography – PKC 2023: 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7–10, 2023, Proceedings, Part I

May 2023

811 pages

ISBN:978-3-031-31367-7

DOI:10.1007/978-3-031-31368-4

Editors:
Alexandra Boldyreva
Georgia Institute of Technology, Atlanta, GA, USA
,
Vladimir Kolesnikov
Georgia Institute of Technology, Atlanta, GA, USA

© International Association for Cryptologic Research 2023.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 May 2023

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Delpech de Saint Guilhem CPedersen R(2024)New Proof Systems and an OPRF from CSIDHPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_8(217-251)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_8
Galbraith SLai YMontgomery H(2024)A Simpler and More Efficient Reduction of DLog to CDH for Abelian Group ActionsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_2(36-60)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_2
Basso AChen MFouotsa TKutas PLaval AMarco LSaah G(2024)Exploring SIDH-Based Signature ParametersApplied Cryptography and Network Security10.1007/978-3-031-54770-6_17(432-456)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_17
Delpech de Saint Guilhem CEbrahimi Evan Leeuwen B(2023)Zero-Knowledge Systems from MPC-in-the-Head and Oblivious TransferCryptography and Coding10.1007/978-3-031-47818-5_7(120-136)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-47818-5_7

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