Communications in Cryptology IACR CiC

Simple Two-Message OT in the Explicit Isogeny Model

Authors

Emmanuela Orsini, Riccardo Zanotto
Emmanuela Orsini ORCID
Bocconi University, Milan, Italy
emmanuela dot orsini at unibocconi dot it
Riccardo Zanotto ORCID
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
riccardo dot zanotto at cispa dot de
Keywords: Oblivious Transfer Isogenies CSIDH Group Action Model

Abstract

In this work we study algebraic and generic models for group actions, and extend them to the universal composability (UC) framework of Canetti (FOCS 2001). We revisit the constructions of Duman et al. (PKC 2023) integrating the type-safe model by Zhandry (Crypto 2022), adapted to the group action setting, and formally define an algebraic action model (AAM). This model restricts the power of the adversary in a similar fashion to the algebraic group model (AGM). By imposing algebraic behaviour to the adversary and environment of the UC framework, we construct the UC-AAM. Finally, we instantiate UC-AAM with isogeny-based assumptions, in particular the CSIDH action with twists, obtaining the explicit isogeny model, UC-EI; we observe that, under certain assumptions, this model is "closer" to standard UC than the UC-AGM, even though there still exists an important separation. We demonstrate the utility of our definitions by proving UC-EI security for the passive-secure oblivious transfer protocol described by Lai et al. (Eurocrypt 2021), hence providing the first concretely efficient two-message isogeny-based OT protocol in the random oracle model against malicious adversaries.

References

[ABK+21]
Michel Abdalla, Manuel Barbosa, Jonathan Katz, Julian Loss, and Jiayu Xu. Algebraic adversaries in the universal composability framework. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 311–341. December 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-92078-4_11.
Google Scholar ePrint
[ADMP20]
Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis. Cryptographic group actions and applications. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, 411–439. December 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-64834-3_14.
Google Scholar ePrint
[AEK+22]
Michel Abdalla, Thorsten Eisenhofer, Eike Kiltz, Sabrina Kunzweiler, and Doreen Riepel. Password-authenticated key exchange from group actions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, 699–728. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15979-4_24.
Google Scholar ePrint
[AIR01]
William Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: how to sell digital goods. In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, 119–135. May 2001. Springer, Heidelberg. https://doi.org/10.1007/3-540-44987-6_8.
Google Scholar ePrint
[BBD+22]
Jeremy Booher, Ross Bowden, Javad Doliskani, Tako Boris Fouotsa, Steven D. Galbraith, Sabrina Kunzweiler, Simon-Philipp Merz, Christophe Petit, Benjamin Smith, Katherine E. Stange, Yan Bo Ti, Christelle Vincent, José Felipe Voloch, Charlotte Weitkämper, and Lukas Zobernig. Failing to hash into supersingular isogeny graphs. 2022.
Google Scholar ePrint
[BD18]
Zvika Brakerski and Nico Döttling. Two-message statistically sender-private OT from LWE. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, 370–390. November 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-03810-6_14.
Google Scholar ePrint
[BDD+17]
Paulo S. L. M. Barreto, Bernardo David, Rafael Dowsley, Kirill Morozov, and Anderson C. A. Nascimento. A framework for efficient adaptively secure composable oblivious transfer in the ROM. 2017.
Google Scholar ePrint
[BDGM19]
Pedro Branco, Jintai Ding, Manuel Goulão, and Paulo Mateus. A framework for universally composable oblivious transfer from one-round key-exchange. In Martin Albrecht, editor, 17th IMA International Conference on Cryptography and Coding, volume 11929 of LNCS, 78–101. December 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-35199-1_5.
Google Scholar ePrint
[BKV19]
Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: efficient isogeny based signatures through class group computations. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, 227–247. December 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-34578-5_9.
Google Scholar ePrint
[BLN+21]
Sai Sheshank Burra, Enrique Larraia, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Emmanuela Orsini, Peter Scholl, and Nigel P. Smart. High-performance multi-party computation for binary circuits based on oblivious transfer. Journal of Cryptology, 34(3):34, July 2021. https://doi.org/10.1007/s00145-021-09403-1.
Google Scholar ePrint
[BM90]
Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, 547–557. August 1990. Springer, Heidelberg. https://doi.org/10.1007/0-387-34805-0_48.
Google Scholar ePrint
[BMM+23]
Saikrishna Badrinarayanan, Daniel Masny, Pratyay Mukherjee, Sikhar Patranabis, Srinivasan Raghuraman, and Pratik Sarkar. Round-optimal oblivious transfer and MPC from computational CSIDH. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part I, volume 13940 of LNCS, 376–405. May 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-31368-4_14.
Google Scholar ePrint
[BY91]
Gilles Brassard and Moti Yung. One-way group actions. In Alfred J. Menezes and Scott A. Vanstone, editors, CRYPTO'90, volume 537 of LNCS, 94–107. August 1991. Springer, Heidelberg. https://doi.org/10.1007/3-540-38424-3_7.
Google Scholar ePrint
[Can01]
Ran Canetti. Universally composable security: a new paradigm for cryptographic protocols. In 42nd FOCS, 136–145. October 2001. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.2001.959888.
Google Scholar ePrint
[CD23]
Wouter Castryck and Thomas Decru. An efficient key recovery attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 423–447. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30589-4_15.
Google Scholar ePrint
[CDPW07]
Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In Salil P. Vadhan, editor, TCC 2007, volume 4392 of LNCS, 61–85. February 2007. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_4.
Google Scholar ePrint
[CLM+18]
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: an efficient post-quantum commutative group action. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part III, volume 11274 of LNCS, 395–427. December 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-03332-3_15.
Google Scholar ePrint
[CO15]
Tung Chou and Claudio Orlandi. The simplest protocol for oblivious transfer. In Kristin E. Lauter and Francisco Rodríguez-Henríquez, editors, LATINCRYPT 2015, volume 9230 of LNCS, 40–58. August 2015. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-22174-8_3.
Google Scholar ePrint
[Cou06]
Jean-Marc Couveignes. Hard homogeneous spaces. 2006.
Google Scholar ePrint
[CPV20]
Wouter Castryck, Lorenz Panny, and Frederik Vercauteren. Rational isogenies from irrational endomorphisms. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, 523–548. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45724-2_18.
Google Scholar ePrint
[DCW13]
Changyu Dong, Liqun Chen, and Zikai Wen. When private set intersection meets big data: an efficient and scalable protocol. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, 789–800. November 2013. ACM Press. https://doi.org/10.1145/2508859.2516701.
Google Scholar ePrint
[DDN14]
Bernardo David, Rafael Dowsley, and Anderson C. A. Nascimento. Universally composable oblivious transfer based on a variant of LPN. In Dimitris Gritzalis, Aggelos Kiayias, and Ioannis G. Askoxylakis, editors, CANS 14, volume 8813 of LNCS, 143–158. October 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-12280-9_10.
Google Scholar ePrint
[DGH+20]
Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, Daniel Masny, and Daniel Wichs. Two-round oblivious transfer from CDH or LPN. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, 768–797. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45724-2_26.
Google Scholar ePrint
[DGI+19]
Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky. Trapdoor hash functions and their applications. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, 3–32. August 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-26954-8_1.
Google Scholar ePrint
[DHK+23]
Julien Duman, Dominik Hartmann, Eike Kiltz, Sabrina Kunzweiler, Jonas Lehmann, and Doreen Riepel. Generic models for group actions. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part I, volume 13940 of LNCS, 406–435. May 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-31368-4_15.
Google Scholar ePrint
[DOPS20]
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Christophe Petit, and Nigel P. Smart. Semi-commutative masking: A framework for isogeny-based protocols, with an application to fully secure two-round isogeny-based OT. In Stephan Krenn, Haya Shulman, and Serge Vaudenay, editors, CANS 20, volume 12579 of LNCS, 235–258. December 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-65411-5_12.
Google Scholar ePrint
[Dv22]
Léo Ducas and Wessel P. J. van Woerden. On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, 643–673. May / June 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-07082-2_23.
Google Scholar ePrint
[DvMN08]
Rafael Dowsley, Jeroen van de Graaf, Jörn Müller-Quade, and Anderson C. A. Nascimento. Oblivious transfer based on the McEliece assumptions. In Reihaneh Safavi-Naini, editor, ICITS 08, volume 5155 of LNCS, 107–117. August 2008. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-85093-9_11.
Google Scholar ePrint
[EGL82]
Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, CRYPTO'82, volume of, 205–210. 1982. Plenum Press, New York, USA. https://doi.org/?
Google Scholar ePrint
[Fel19]
Joël Felderhoff. Hard Homogenous Spaces and Commutative Supersingular Isogeny based Diffie-Hellman. Internship report, LIX, Ecole polytechnique ; ENS de Lyon, August 2019.
Google Scholar ePrint
[Feo17]
Luca De Feo. Mathematics of isogeny based cryptography. CoRR, 2017.
Google Scholar ePrint
[FKL18]
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, 33–62. August 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-96881-0_2.
Google Scholar ePrint
[GO94]
Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, December 1994. https://doi.org/10.1007/BF00195207.
Google Scholar ePrint
[GPSV21]
Steven Galbraith, Lorenz Panny, Benjamin Smith, and Frederik Vercauteren. Quantum equivalence of the DLP and CDHP for group actions. Mathematical Cryptology, 1(1):40–44, Jun. 2021.
Google Scholar ePrint
[GS10]
Dima Grigoriev and Vladimir Shpilrain. Authentication schemes from actions on graphs, groups, or rings. Annals of Pure and Applied Logic, 162(3):194–200, 2010. https://doi.org/https://doi.org/10.1016/j.apal.2010.09.004.
Google Scholar ePrint
[HK12]
Shai Halevi and Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. Journal of Cryptology, 25(1):158–193, January 2012. https://doi.org/10.1007/s00145-010-9092-8.
Google Scholar ePrint
[JAC+20]
David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Joost Renes, Vladimir Soukharev, David Urbanik, Geovandro Pereira, Koray Karabina, and Aaron Hutchinson. SIKE. Technical Report, National Institute of Standards and Technology, 2020.
Google Scholar ePrint
[JD11]
David Jao and Luca De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Bo-Yin Yang, editor, Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, 19–34. November / December 2011. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-25405-5_2.
Google Scholar ePrint
[JQSY19]
Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General linear group action on tensors: A candidate for post-quantum cryptography. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, 251–281. December 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-36030-6_11.
Google Scholar ePrint
[Kan97]
Ernst Kani. The number of curves of genus two with elliptic differentials. Journal für die reine und angewandte Mathematik (Crelles Journal), 1997:122 – 93, 1997. https://doi.org/?
Google Scholar ePrint
[KOS16]
Marcel Keller, Emmanuela Orsini, and Peter Scholl. MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 830–842. October 2016. ACM Press. https://doi.org/10.1145/2976749.2978357.
Google Scholar ePrint
[LGD21]
Yi-Fu Lai, Steven D. Galbraith, and Cyprien Delpech de Saint Guilhem. Compact, efficient and UC-secure isogeny-based oblivious transfer. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, 213–241. October 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-77870-5_8.
Google Scholar ePrint
[Mau05]
Ueli M. Maurer. Abstract models of computation in cryptography (invited paper). In Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of LNCS, 1–12. December 2005. Springer, Heidelberg. https://doi.org/?
Google Scholar ePrint
[MMP22]
Marzio Mula, Nadir Murru, and Federico Pintore. Random sampling of supersingular elliptic curves. 2022.
Google Scholar ePrint
[MMP+23]
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A direct key recovery attack on SIDH. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 448–471. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30589-4_16.
Google Scholar ePrint
[MS20]
Daniele Micciancio and Jessica Sorrell. Simpler statistically sender private oblivious transfer from ideals of cyclotomic integers. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, 381–407. December 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-64834-3_13.
Google Scholar ePrint
[MZ22]
Hart Montgomery and Mark Zhandry. Full quantum equivalence of group action DLog and CDH, and more. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part I, volume 13791 of LNCS, 3–32. December 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-22963-3_1.
Google Scholar ePrint
[NP01]
Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In S. Rao Kosaraju, editor, 12th SODA, 448–457. January 2001. ACM-SIAM. https://doi.org/?
Google Scholar ePrint
[Pan23]
Lorenz Panny. CSI‑FiSh really isn't polynomial‑time. 2023.
Google Scholar ePrint
[PSZ14]
Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on OT extension. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, 797–812. August 2014. USENIX Association. https://doi.org/?
Google Scholar ePrint
[PVW08]
Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, 554–571. August 2008. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-85174-5_31.
Google Scholar ePrint
[Rab05]
Michael O. Rabin. How to exchange secrets with oblivious transfer. 2005.
Google Scholar ePrint
[Rob23]
Damien Robert. Breaking SIDH in polynomial time. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, 472–503. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30589-4_17.
Google Scholar ePrint
[RS06]
Alexander Rostovtsev and Anton Stolbunov. Public-Key Cryptosystem Based On Isogenies. 2006.
Google Scholar ePrint
[Sho97]
Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, 256–266. May 1997. Springer, Heidelberg. https://doi.org/10.1007/3-540-69053-0_18.
Google Scholar ePrint
[Sil09]
J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer New York, 2009. ISBN 9780387094946.
Google Scholar ePrint
[V{\'{e}}l71]
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes Rendus de l'Académie des Sciences de Paris, 273:238–241, July 1971.
Google Scholar ePrint
[Vit19]
Vanessa Vitse. Simple oblivious transfer protocols compatible with supersingular isogenies. In Johannes Buchmann, Abderrahmane Nitaj, and Tajje-eddine Rachidi, editors, AFRICACRYPT 19, volume 11627 of LNCS, 56–78. July 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-23696-0_4.
Google Scholar ePrint
[Wes22a]
Benjamin Wesolowski. Orientations and the supersingular endomorphism ring problem. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, 345–371. May / June 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-07082-2_13.
Google Scholar ePrint
[Wes22b]
Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In 62nd FOCS, 1100–1111. February 2022. IEEE Computer Society Press. https://doi.org/10.1109/FOCS52979.2021.00109.
Google Scholar ePrint
[Zha22]
Mark Zhandry. To label, or not to label (in generic groups). In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part III, volume 13509 of LNCS, 66–96. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15982-4_3.
Google Scholar ePrint
[ZLWR13]
Bingsheng Zhang, Helger Lipmaa, Cong Wang, and Kui Ren. Practical fully simulatable oblivious transfer with sublinear communication. In Ahmad-Reza Sadeghi, editor, FC 2013, volume 7859 of LNCS, 78–95. April 2013. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-39884-1_8.
Google Scholar ePrint
[ZZK22]
Cong Zhang, Hong-Sheng Zhou, and Jonathan Katz. An analysis of the algebraic group model. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, 310–322. December 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-22972-5_11.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/a39qgy4e-
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Emmanuela Orsini and Riccardo Zanotto, Simple Two-Message OT in the Explicit Isogeny Model. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a39qgy4e-.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.