A BKW-Style Solver for the Restricted Syndrome Decoding Problem

A BKW-Style Solver for the Restricted Syndrome Decoding Problem | 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 A BKW-Style Solver for the Restricted Syndrome Decoding Problem Thomas Johansson, Qian Guo, Vu Nguyen This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7253519/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 8 You are reading this latest preprint version Abstract The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has recently been turned into a post-quantum signature scheme named CROSS by Baldi et al.. It is a scheme highlighted for being computationally friendly and providing a compact signature and public key size. This paper investigates an Oracle-based definition of the RSDP that has already proved useful in constructing other cryptographic primitives. We propose a new solving algorithm for this novel and interesting problem. Our approach is to first introduce a new weight definition for vectors over $\ffield{p}$ and then develop a solving algorithm similar to the BKW algorithm that includes finding many such low-weight vectors in a dual space. We make use of several advanced techniques, such as Covering codes and Subspace Hypothesis Testing . We show that when there are many samples, our algorithm can be more advantageous than prior work based on information-set decoding adaptations for RSDP or algebraic approaches. Restricted Syndrome Decoding Problem BKW algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 24 Mar, 2026 Reviews received at journal 26 Feb, 2026 Reviewers agreed at journal 01 Oct, 2025 Reviewers agreed at journal 30 Sep, 2025 Reviewers invited by journal 14 Aug, 2025 Editor assigned by journal 31 Jul, 2025 Submission checks completed at journal 31 Jul, 2025 First submitted to journal 30 Jul, 2025 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-7253519","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":502958322,"identity":"1d051947-a88f-47aa-b6ce-d6a6c416f85f","order_by":0,"name":"Thomas Johansson","email":"","orcid":"","institution":"Lund University","correspondingAuthor":false,"prefix":"","firstName":"Thomas","middleName":"","lastName":"Johansson","suffix":""},{"id":502958324,"identity":"edb2b870-37c5-4cd2-9cd9-dc99703061b7","order_by":1,"name":"Qian Guo","email":"","orcid":"","institution":"Lund University","correspondingAuthor":false,"prefix":"","firstName":"Qian","middleName":"","lastName":"Guo","suffix":""},{"id":502958325,"identity":"7b9a0d64-08a8-4c49-9c6f-4157676f11b2","order_by":2,"name":"Vu Nguyen","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA5ElEQVRIiWNgGAWjYFAD9gaGAwwMFgwGxGvhOcBw4ACDhAQJWiQSGBiI0mJwI4Ht4de2w3Lmko8PHv7AIFFnzsD+8AEBLezGsm2HjS1npyWAHWbZwGOM1ybJGQls0pJthxM33M4xgPjlAA+bBDFa6jfcPP8BqoX9+Q98WvglEtgkP7YdTjC4wQMNsQMMZvh0MPDzPGyTZjiXbrjhTJrBgTMGEpIbDvMY43UYG3vyMckfZdbyBscPP/5QUWHDb3C8/eEHvNYwMDYw8zA0QzmgoGLGrx6i6QdDHRHKRsEoGAWjYMQCAGF9STCcbMYlAAAAAElFTkSuQmCC","orcid":"","institution":"Lund University","correspondingAuthor":true,"prefix":"","firstName":"Vu","middleName":"","lastName":"Nguyen","suffix":""}],"badges":[],"createdAt":"2025-07-30 13:38:35","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7253519/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7253519/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":89629408,"identity":"6c21b076-e013-427c-badd-3932d4f9125d","added_by":"auto","created_at":"2025-08-22 06:32:04","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":839439,"visible":true,"origin":"","legend":"","description":"","filename":"RestrictedDecodingSubmit.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7253519/v1_covered_62137213-e884-484e-b143-518efbba6e79.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A BKW-Style Solver for the Restricted Syndrome Decoding Problem","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"cryptography-and-communications","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"ccds","sideBox":"Learn more about [Cryptography and Communications](http://link.springer.com/journal/12095)","snPcode":"12095","submissionUrl":"https://submission.nature.com/new-submission/12095/3","title":"Cryptography and Communications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Restricted Syndrome Decoding Problem, BKW algorithm","lastPublishedDoi":"10.21203/rs.3.rs-7253519/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7253519/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003e\u0026nbsp;The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has recently been turned into a post-quantum signature scheme named CROSS by Baldi et al.. It is a scheme highlighted for being computationally friendly and providing a compact signature and public key size. This paper investigates an Oracle-based definition of the RSDP that has already proved useful in constructing other cryptographic primitives. We propose a new solving algorithm for this novel and interesting problem. Our approach is to first introduce a new weight definition for vectors over $\\ffield{p}$ and then develop a solving algorithm similar to the BKW algorithm that includes finding many such low-weight vectors in a dual space. We make use of several advanced techniques, such as \u003cem\u003eCovering codes\u003c/em\u003e and \u003cem\u003eSubspace Hypothesis Testing\u003c/em\u003e. We show that when there are many samples, our algorithm can be more advantageous than prior work based on information-set decoding adaptations for RSDP or algebraic approaches.\u003c/p\u003e","manuscriptTitle":"A BKW-Style Solver for the Restricted Syndrome Decoding Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-08-22 06:23:57","doi":"10.21203/rs.3.rs-7253519/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2026-03-24T20:56:14+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-26T15:02:11+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"132698349637370469299547533416813299390","date":"2025-10-01T16:32:44+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"159992879599777994153715261127395052109","date":"2025-09-30T21:17:53+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-08-14T14:29:49+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-08-01T02:38:54+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-07-31T23:08:30+00:00","index":"","fulltext":""},{"type":"submitted","content":"Cryptography and Communications","date":"2025-07-30T13:34:51+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"cryptography-and-communications","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"ccds","sideBox":"Learn more about [Cryptography and Communications](http://link.springer.com/journal/12095)","snPcode":"12095","submissionUrl":"https://submission.nature.com/new-submission/12095/3","title":"Cryptography and Communications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"bd741ba4-b0cc-4772-a2f4-1a5d3cfbd06a","owner":[],"postedDate":"August 22nd, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-04-21T16:09:02+00:00","versionOfRecord":[],"versionCreatedAt":"2025-08-22 06:23:57","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7253519","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7253519","identity":"rs-7253519","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}