Parallel Implementations of Post-Quantum Leighton-Micali Signature on Multiple Nodes

Parallel Implementations of Post-Quantum Leighton-Micali Signature on Multiple Nodes | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Parallel Implementations of Post-Quantum Leighton-Micali Signature on Multiple Nodes Yan Kang, Xiaoshe Dong, Ziheng Wang, Heng Chen, Qiang Wang This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-2656155/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 7 You are reading this latest preprint version Abstract To defend against quantum computer attacks, the National Institute of Standards and Technology (NIST) has been exploring post-quantum cryptography (PQC). Now, NIST has standardised only two PQC algorithms, one of which is the Leighton-Micali signature (LMS). However, the performance of LMS limits its practical application. In this paper, we propose a parallel LMS implementation on multiple nodes. Considering different application scenarios, we provide two parallel schemes: algorithmic parallelism and data parallelism. The main part of our work is the two-tier parallel structure for the LMS tree. Targeting the x86/64 multiple nodes, our work introduces vectorization to present the three-tier parallel structure. We also design communication optimization, including the selection of communication primitives and the creation of communicators for multi-node running. Experimental evidence shows that our code effectively reduces the latency, and is 19.04× faster than the fastest implementation on the same platform when running key pair generation for LMS SHA256 M32 H20(20). post-quantum cryptography stateful hash-based signatures LMS HSS parallel computing Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Major revision 05 Aug, 2023 Reviews received at journal 10 Jul, 2023 Reviewers agreed at journal 30 Jun, 2023 Reviewers invited by journal 30 Jun, 2023 Editor assigned by journal 06 Mar, 2023 Submission checks completed at journal 06 Mar, 2023 First submitted to journal 04 Mar, 2023 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-2656155","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":181375437,"identity":"c2addf4a-a59f-41b6-a5cd-840d4f618054","order_by":0,"name":"Yan Kang","email":"","orcid":"","institution":"Xi'an Jiaotong University","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Yan","middleName":"","lastName":"Kang","suffix":""},{"id":181375438,"identity":"a8438c44-05a7-4cc4-b42e-051e4793175b","order_by":1,"name":"Xiaoshe Dong","email":"","orcid":"","institution":"Xi'an Jiaotong University","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Xiaoshe","middleName":"","lastName":"Dong","suffix":""},{"id":181375442,"identity":"f2f5a0d3-b1f4-418c-8f16-810a4856cde3","order_by":2,"name":"Ziheng Wang","email":"","orcid":"","institution":"Xi'an Jiaotong University","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Ziheng","middleName":"","lastName":"Wang","suffix":""},{"id":181375445,"identity":"1d6202cc-b839-4362-a29f-836411dae18f","order_by":3,"name":"Heng Chen","email":"","orcid":"","institution":"Xi'an Jiaotong University","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Heng","middleName":"","lastName":"Chen","suffix":""},{"id":181375448,"identity":"201dfd3f-e486-4a66-b56a-3c2ba4c94870","order_by":4,"name":"Qiang Wang","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABHElEQVRIiWNgGAWjYNACAyBmZj744EMFAzNYgIcoLexsyYYzzjAw8xCnBQT4ecykedugqvFpMTh+9vCLNwV2efLOPMbGvPMOs9tLJDA+eNvGIG+OS8uZvDTLOQbJxYaH2Qofzt2WxswjkcBsOLeNwXBnA3YtZgdyzIx5DJgTNzYzbzZ4u80GpIUN5MIEgwM4tJx/A9JSD9TCYCbBO0cCpIX9N14tN3KMH/MYHE6cz8xiJsnbALGFGZ8W+xtvzBjnGBxP3MAMCuRjQL+cedgsOeechOEGHFok+3OMP7z5U504v/8wMCprDieztycf/PCmzEYely1AwCYBigWYgmQGBsYGIC2BUz0QMH8AaZFvgPDs8CkdBaNgFIyCkQkAChlYHgLRTNIAAAAASUVORK5CYII=","orcid":"","institution":"Xi'an Jiaotong University","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Qiang","middleName":"","lastName":"Wang","suffix":""}],"badges":[],"createdAt":"2023-03-05 02:29:13","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-2656155/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-2656155/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":34019260,"identity":"ab1d0bd2-9ee2-42b4-a00d-7eda6a45c13e","added_by":"auto","created_at":"2023-03-09 14:32:32","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":571003,"visible":true,"origin":"","legend":"","description":"","filename":"lmscpu.pdf","url":"https://assets-eu.researchsquare.com/files/rs-2656155/v1/3cfa97f4cc0243c2f2d07301.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Parallel Implementations of Post-Quantum Leighton-Micali Signature on Multiple Nodes","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"post-quantum cryptography, stateful hash-based signatures, LMS, HSS, parallel computing","lastPublishedDoi":"10.21203/rs.3.rs-2656155/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-2656155/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eTo defend against quantum computer attacks, the National Institute of Standards and Technology (NIST) has been exploring post-quantum cryptography (PQC). Now, NIST has standardised only two PQC algorithms, one of which is the Leighton-Micali signature (LMS). However, the performance of LMS limits its practical application. In this paper, we propose a parallel LMS implementation on multiple nodes. Considering different application scenarios, we provide two parallel schemes: algorithmic parallelism and data parallelism. The main part of our work is the two-tier parallel structure for the LMS tree. Targeting the x86/64 multiple nodes, our work introduces vectorization to present the three-tier parallel structure. We also design communication optimization, including the selection of communication primitives and the creation of communicators for multi-node running. Experimental evidence shows that our code effectively reduces the latency, and is 19.04× faster than the fastest implementation on the same platform when running key pair generation for LMS SHA256 M32 H20(20).\u003c/p\u003e","manuscriptTitle":"Parallel Implementations of Post-Quantum Leighton-Micali Signature on Multiple Nodes","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2023-03-09 14:32:27","doi":"10.21203/rs.3.rs-2656155/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Major revision","date":"2023-08-05T04:38:00+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2023-07-10T12:35:46+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"f1fef1e5-cd75-4643-bb4a-1328090e7cf1","date":"2023-07-01T01:56:56+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2023-06-30T23:42:12+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2023-03-07T04:19:39+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2023-03-07T04:19:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"The Journal of Supercomputing","date":"2023-03-05T02:24:16+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"the-journal-of-supercomputing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [The Journal of Supercomputing](https://www.springer.com/journal/11227)","snPcode":"11227","submissionUrl":"https://submission.nature.com/new-submission/11227/3","title":"The Journal of Supercomputing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"f9058149-3638-4fd7-849b-f0844c071cb4","owner":[],"postedDate":"March 9th, 2023","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2023-09-07T02:14:19+00:00","versionOfRecord":[],"versionCreatedAt":"2023-03-09 14:32:27","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-2656155","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-2656155","identity":"rs-2656155","version":["v1"]},"buildId":"FbvkV6FR0MCFSLy54lSbu","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}