{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T21:05:06Z","timestamp":1776978306878,"version":"3.51.4"},"reference-count":25,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,4]]},"abstract":"Abstract<\/jats:title>\n \n We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order\n \n \n \n \n \n \n p<\/m:mi>\n <\/m:mrow>\n \n 3<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n {p}^{3}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and exponent\n \n \n \n \n \n \n p<\/m:mi>\n <\/m:mrow>\n \n 2<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n {p}^{2}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for certain exponentially large parameters. This implies an attack on SPDH-Sign,\n \n Pronounced \u201cSPUD-Sign\u201d.<\/jats:p>\n <\/jats:fn>\n a signature scheme based on the SDLP, for such parameters. In particular, SDLP instances over such groups are parameterised by an\n \n \n \n \n n<\/m:mi>\n <<\/m:mo>\n \n (<\/m:mo>\n \n p<\/m:mi>\n \u2212<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \n \n p<\/m:mi>\n <\/m:mrow>\n \n 6<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n n\\lt \\left(p-1){p}^{6}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n : we develop a method to solve instances when\n \n \n \n \n n<\/m:mi>\n \u2264<\/m:mo>\n poly<\/m:mi>\n \n (<\/m:mo>\n \n log<\/m:mi>\n p<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n \n \u22c5<\/m:mo>\n p<\/m:mi>\n <\/m:math>\n n\\le {\\rm{poly}}\\left(\\log p)\\hspace{0.25em}\\cdot p<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Letting\n \n \n \n \n \u03bb<\/m:mi>\n <\/m:math>\n \\lambda<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be the security parameter of SPDH-Sign, which is taken\n \n \n \n \n p<\/m:mi>\n =<\/m:mo>\n exp<\/m:mi>\n \u03bb<\/m:mi>\n <\/m:math>\n p=\\exp \\lambda<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large\n \n \n \n \n p<\/m:mi>\n <\/m:math>\n p<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . However, for\n \n \n \n \n n<\/m:mi>\n \u2248<\/m:mo>\n \n \n p<\/m:mi>\n <\/m:mrow>\n \n 2<\/m:mn>\n <\/m:mrow>\n <\/m:msup>\n <\/m:math>\n n\\approx {p}^{2}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and larger, our method no longer completely solves the SDLP instances. We also study the linear hidden shift problem for a group action corresponding to SDLP and take a step towards proving the quantum polynomial time equivalence of SDLP and the semidirect computational Diffie\u2013Hellman problem.\n <\/jats:p>","DOI":"10.1515\/jmc-2024-0025","type":"journal-article","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T11:52:14Z","timestamp":1741089134000},"source":"Crossref","is-referenced-by-count":2,"title":["A small serving of mash: (Quantum) algorithms for SPDH-Sign with small parameters"],"prefix":"10.1515","volume":"19","author":[{"given":"Andrew","family":"Mendelsohn","sequence":"first","affiliation":[{"name":"Department of Electrical and Electronic Engineering, Imperial College London , SW7 2AZ , United Kingdom"}]},{"given":"Edmund","family":"Dable-Heath","sequence":"additional","affiliation":[{"name":"The Alan Turing Institute , London , NW1 2DB , United Kingdom"}]},{"given":"Cong","family":"Ling","sequence":"additional","affiliation":[{"name":"Department of Electrical and Electronic Engineering, Imperial College London , SW7 2AZ , United Kingdom"}]}],"member":"374","published-online":{"date-parts":[[2025,3,4]]},"reference":[{"key":"2025122009205614449_j_jmc-2024-0025_ref_001","doi-asserted-by":"crossref","unstructured":"Diffie W, Hellman M. New directions in cryptography. IEEE Trans Inform Theory. 1976;22(6):644\u201354.","DOI":"10.1109\/TIT.1976.1055638"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_002","doi-asserted-by":"crossref","unstructured":"Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science; 1994. p. 124\u201334.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_003","unstructured":"Battarbee C, Kahrobaei D, Perret L, Shahandashti SF. A subexponential quantum algorithm for the semidirect discrete logarithm problem; 2022. Presented at NIST\u2019s Fourth PQC Standardization Conference. Cryptology ePrint Archive, Paper 2022\/1165. https:\/\/eprint.iacr.org\/2022\/1165."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_004","doi-asserted-by":"crossref","unstructured":"Battarbee C, Kahrobaei D, Perret L, Shahandashti SF. SPDH-sign: towards efficient, post-quantum group-based signatures. In: Johansson T, Smith-Tone D, editors. Post-quantum cryptography. Switzerland: Springer Nature; 2023. p. 113\u201338.","DOI":"10.1007\/978-3-031-40003-2_5"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_005","doi-asserted-by":"crossref","unstructured":"Alamati N, De Feo L, Montgomery H, Patranabis S. Cryptographic group actions and applications. In: Moriai S, Wang H, editors. ASIACRYPT 2020. Cham: Springer International Publishing; 2020. p. 411\u201339.","DOI":"10.1007\/978-3-030-64834-3_14"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_006","doi-asserted-by":"crossref","unstructured":"Alamati N, Malavolta G, Rahimi A. Candidate trapdoor claw-free functions from group actions with applications to quantum protocols. In: Kiltz E, Vaikuntanathan V, editors. TCC 2022. vol. 13747 of LNCS. Switzerland: Springer Nature; 2022. p. 266\u201393.","DOI":"10.1007\/978-3-031-22318-1_10"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_007","doi-asserted-by":"crossref","unstructured":"Alamati N, Patranabis S. Cryptographic primitives with hinting property. In: Agrawal S, Lin D, editors. ASIACRYPT 2022. vol. 13791 of LNCS. Switzerland: Springer Nature; 2022. p. 33\u201362.","DOI":"10.1007\/978-3-031-22963-3_2"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_008","doi-asserted-by":"crossref","unstructured":"Rahman N, Shpilrain V. MAKE: A matrix action key exchange. J Math Cryptol. 2022;16(1):64\u201372.","DOI":"10.1515\/jmc-2020-0053"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_009","doi-asserted-by":"crossref","unstructured":"Habeeb M, Kahrobaei D, Koupparis C, Shpilrain V. Public key exchange using semidirect product of (semi)groups. In: Jacobson M, Locasto M, Mohassel P, Safavi-Naini R, editorsApplied u. Berlin Heidelberg: Springer; 2013. p. 475\u201386.","DOI":"10.1007\/978-3-642-38980-1_30"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_010","doi-asserted-by":"crossref","unstructured":"Kahrobaei D, Shpilrain V. Using semidirect product of (semi)groups in public key cryptography. In: Beckmann A, Bienvenu L, Jonoska N, editors. Pursuit of the Universal. Cham: Springer International Publishing; 2016. p. 132\u201341.","DOI":"10.1007\/978-3-319-40189-8_14"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_011","doi-asserted-by":"crossref","unstructured":"Battarbee C, Kahrobaei D, Shahandashti SF. Semidirect product key exchange: the state of play; 2023. Cryptology ePrint Archive, Paper 2023\/594. https:\/\/eprint.iacr.org\/2023\/594.","DOI":"10.1142\/S0219498825500665"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_012","unstructured":"Roman\u2019kov V. Linear decomposition attack on public key exchange protocols using semidirect products of (semi)groups. CoRR. 2015; http:\/\/arxiv.org\/abs\/1501.01152."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_013","unstructured":"Battarbee C, Kahrobaei D, Shahandashti SF. Cryptanalysis of semidirect product key exchange using matrices over non-commutative rings. Math Cryptol. 2022 March;1(2):2\u20139. https:\/\/journals.flvc.org\/mathcryptology\/article\/view\/130528."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_014","doi-asserted-by":"crossref","unstructured":"Brown DRL, Koblitz N, LeGrow JT. Cryptanalysis of MAKE. J Math Cryptol. 2022;16(1):98\u2013102.","DOI":"10.1515\/jmc-2021-0016"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_015","unstructured":"Couveignes JM. Hard Homogeneous Spaces; 2006. Cryptology ePrint Archive, Paper 2006\/291. https:\/\/eprint.iacr.org\/2006\/291."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_016","doi-asserted-by":"crossref","unstructured":"Gnilke OW, Zumbr\u00e4gel J. Cryptographic group and semigroup actions. J Algebra Appl. 2024;23(07):2530001.","DOI":"10.1142\/S0219498825300016"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_017","doi-asserted-by":"crossref","unstructured":"Castryck W, Vander Meeren N. Two remarks on the vectorization problem. In: Isobe T, Sarkar S, editors. INDOCRYPT 2022. vol. 13774 of LNCS. Cham: Springer International Publishing; 2022. p. 658\u201378.","DOI":"10.1007\/978-3-031-22912-1_29"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_018","doi-asserted-by":"crossref","unstructured":"D\u2019Alconzo G, Di Scala AJ. Representations of group actions and their applications in cryptography. Finite Fields Appl. 2024;99:102476.","DOI":"10.1016\/j.ffa.2024.102476"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_019","doi-asserted-by":"crossref","unstructured":"Imran M, Ivanyos G. Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem. Designs Codes Cryptography. 2024 May;92:2825\u201343.","DOI":"10.1007\/s10623-024-01416-8"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_020","unstructured":"Conrad K. Groups of order p3; https:\/\/kconrad.math.uconn.edu\/blurbs\/grouptheory\/groupsp3.pdf."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_021","unstructured":"Monico C. Remarks on MOBS and cryptosystems using semidirect products; 2021. Cryptology ePrint Archive, Paper 2021\/1114. https:\/\/eprint.iacr.org\/2021\/1114."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_022","doi-asserted-by":"crossref","unstructured":"Rahman N, Shpilrain V. MOBS: matrices over bit strings public key exchange. La Matematica. 2024 June;3:1198\u2013206.","DOI":"10.1007\/s44007-024-00114-0"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_023","doi-asserted-by":"crossref","unstructured":"Battarbee C, Kahrobaei D, Tailor D, Shahandashti SF. On the efficiency of a general attack against the MOBS cryptosystem. J Math Cryptol. 2022;16(1):289\u201397.","DOI":"10.1515\/jmc-2021-0050"},{"key":"2025122009205614449_j_jmc-2024-0025_ref_024","unstructured":"Galbraith S, Panny L, Smith B, Vercauteren F. Quantum equivalence of the DLP and CDHP for group actions. Math Cryptol. 2021 June;1(1):40\u20134. https:\/\/journals.flvc.org\/mathcryptology\/article\/view\/122741."},{"key":"2025122009205614449_j_jmc-2024-0025_ref_025","doi-asserted-by":"crossref","unstructured":"Montgomery H, Zhandry M. Full quantum equivalence of group action DLog and CDH, and more. In: Agrawal S, Lin D, editors. ASIACRYPT 2022. vol. 13791 of LNCS. Switzerland: Springer Nature; 2022. p. 3\u201332.","DOI":"10.1007\/978-3-031-22963-3_1"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0025\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0025\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:40:26Z","timestamp":1766223626000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0025\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,1]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,14]]},"published-print":{"date-parts":[[2025,4,14]]}},"alternative-id":["10.1515\/jmc-2024-0025"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2024-0025","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,1]]},"article-number":"20240025"}}