Communications in Cryptology IACR CiC

Simple Two-Message OT in the Explicit Isogeny Model


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


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.


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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Ran Canetti. Universally composable security: a new paradigm for cryptographic protocols. In 42nd FOCS, 136–145. October 2001. IEEE Computer Society Press.
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.
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.
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.
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.
Jean-Marc Couveignes. Hard homogeneous spaces. 2006.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Joël Felderhoff. Hard Homogenous Spaces and Commutative Supersingular Isogeny based Diffie-Hellman. Internship report, LIX, Ecole polytechnique ; ENS de Lyon, August 2019.
Luca De Feo. Mathematics of isogeny based cryptography. CoRR, 2017.
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.
Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, December 1994.
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.
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.
Shai Halevi and Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. Journal of Cryptology, 25(1):158–193, January 2012.
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.
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.
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.
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.
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.
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.
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.
Marzio Mula, Nadir Murru, and Federico Pintore. Random sampling of supersingular elliptic curves. 2022.
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.
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.
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.
Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In S. Rao Kosaraju, editor, 12th SODA, 448–457. January 2001. ACM-SIAM.
Lorenz Panny. CSIFiSh really isn't polynomial‑time. 2023.
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.
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.
Michael O. Rabin. How to exchange secrets with oblivious transfer. 2005.
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.
Alexander Rostovtsev and Anton Stolbunov. Public-Key Cryptosystem Based On Isogenies. 2006.
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.
J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer New York, 2009. ISBN 9780387094946.
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes Rendus de l'Académie des Sciences de Paris, 273:238–241, July 1971.
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.
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.
Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In 62nd FOCS, 1100–1111. February 2022. IEEE Computer Society Press.
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.
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.
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.

PDFPDF Open access

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-.


Copyright is held by the author(s)

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