CINXE.COM
Heuristic Algorithm for Solving Restricted SVP and its Applications
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link href="/css/dist/css/bootstrap.min.css" rel="stylesheet"> <title>Heuristic Algorithm for Solving Restricted SVP and its Applications</title> <link rel="stylesheet" href="/css/eprint.css?v=10"> <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" /> <link rel="apple-touch-icon" href="/img/apple-touch-icon-180x180.png" /> <style> a.toggle-open:after { content:' -'; font-weight: 800; } a.toggle-closed:after { content: " ›"; font-weight: 800; } .paper-abstract { white-space: pre-wrap; } #metadata dt { margin-top: 1rem; } #metadata dt + dd { /* gap between dt and first dd */ margin-top: .75rem; } #metadata dd { margin-left: 2rem; } #metadata dd.keywords { padding-bottom: .5rem; } span.authorName { margin-top: .5rem; font-style: italic; } </style> <script> MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEnvironments: false }, loader: { load: [ "ui/safe", "ui/lazy", ], }, options: { safeOptions: { allow: { URLs: "none", classes: "safe", cssIDs: "safe", styles: "safe", }, }, } }; </script> <script id="MathJax-script" async src="/js/mathjax/tex-chtml.js"></script> <meta name="citation_title" content="Heuristic Algorithm for Solving Restricted SVP and its Applications"> <meta name="citation_author" content="Geng Wang"> <meta name="citation_author" content="Wenwen Xia"> <meta name="citation_author" content="Dawu Gu"> <meta name="citation_journal_title" content="Cryptology ePrint Archive"> <meta name="citation_publication_date" content="2025"> <meta name="citation_pdf_url" content="https://eprint.iacr.org/2025/586.pdf"> <meta property="og:image" content="https://eprint.iacr.org/img/iacrlogo.png"/> <meta property="og:image:alt" content="IACR logo"/> <meta property="og:url" content="https://eprint.iacr.org/2025/586"> <meta property="og:site_name" content="IACR Cryptology ePrint Archive" /> <meta property="og:type" content="article" /> <meta property="og:title" content="Heuristic Algorithm for Solving Restricted SVP and its Applications" /> <meta property="og:description" content="In lattice-based cryptography, many attacks are performed by finding a short enough vector on a specific lattice. However, it is possible that length is not the only restriction on the vector to be found. A typical example is SVP with infinity norm: since most SVP solving algorithms only aim to find short vector under Euclidean norm, the infinity norm is in fact another restriction on the vector. In the literature, such problems are usually solved by performing exhaustive search on a list of short vectors generated from lattice sieving. However, the sieving list might either be too large or too small to pass the additional restriction, which makes the solving algorithm inefficient in some cases. Our contribution in this work is as follows: (1) We formally define a new lattice hard problem called restricted SVP, and show that it can be used to generalize many lattice hard problems, including SVP with non-Euclidean norm and Kannan's embedding on approximate CVP. (2) We extend the dimension for free technique and the enumerate-then-slice technique into approximate SVP where the goal is to output a list of short vectors with a certain size. (3) We give the heuristic algorithm for solving restricted SVP, and design a hardness estimator for this algorithm, which can be used to estimate the concrete hardness of signature forgery in Dilithium and other lattice-based signatures. Using this estimator, we present a concrete security analysis for Dilithium against signature forgery under the gate-count model for the first time. Our estimation matches well with the security estimation from core-SVP model in the document of Dilithium, and we also combine our estimator with the rescaling technique to generate a tighter estimation." /> <meta property="article:section" content="PUBLICKEY" /> <meta property="article:modified_time" content="2025-04-01T01:01:40+00:00" /> <meta property="article:published_time" content="2025-04-01T01:01:40+00:00" /> <meta property="article:tag" content="Lattice-based Cryptography" /> <meta property="article:tag" content="Shortest Vector Problem" /> <meta property="article:tag" content="Dilithium" /> <meta property="article:tag" content="Post-quantum cryptography" /> </head> <body> <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <div class="fixed-top" id="topNavbar"> <nav class="navbar navbar-custom navbar-expand-lg"> <div class="container px-0 justify-content-between justify-content-lg-evenly"> <div class="order-0 align-items-center d-flex"> <button class="navbar-toggler btnNoOutline" type="button" data-bs-toggle="collapse" data-bs-target="#navbarContent" aria-controls="navbarContent" aria-expanded="false"> <span class="icon-bar top-bar"></span> <span class="icon-bar middle-bar"></span> <span class="icon-bar bottom-bar"></span> </button> <a class="d-none me-5 d-lg-inline" href="https://iacr.org/"><img class="iacrlogo" src="/img/iacrlogo_small.png" alt="IACR Logo" style="max-width:6rem;"></a> </div> <a class="ePrintname order-1" href="/"> <span class="longNavName">Cryptology ePrint Archive</span> </a> <div class="collapse navbar-collapse order-3" id="navbarContent"> <ul class="navbar-nav me-auto ms-2 mb-2 mb-lg-0 justify-content-end w-100"> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Papers </a> <ul class="dropdown-menu me-3" aria-labelledby="navbarDropdown"> <span class="text-dark mx-3" style="white-space:nowrap;">Updates from the last:</span> <li><a class="dropdown-item ps-custom" href="/days/7">7 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/31">31 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/183">6 months</a></li> <li><a class="dropdown-item ps-custom" href="/days/365">365 days</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/byyear">Listing by year</a></li> <li><a class="dropdown-item" href="/complete">All papers</a></li> <li><a class="dropdown-item" href="/complete/compact">Compact view</a></li> <li><a class="dropdown-item" href="https://www.iacr.org/news/subscribe">Subscribe</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/citation.html">How to cite</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/rss">Harvesting metadata</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="submissionsDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Submissions </a> <ul class="dropdown-menu me-3" aria-labelledby="submissionsDropdown"> <li><a class="dropdown-item" href="/submit">Submit a paper</a></li> <li><a class="dropdown-item" href="/revise">Revise or withdraw a paper</a></li> <li><a class="dropdown-item" href="/operations.html">Acceptance and publishing conditions</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="aboutDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> About </a> <ul class="dropdown-menu me-3" aria-labelledby="aboutDropdown"> <li><a class="dropdown-item" href="/about.html">Goals and history</a></li> <li><a class="dropdown-item" href="/news.html">News</a></li> <li><a class="dropdown-item" href="/stats">Statistics</a></li> <li><a class="dropdown-item" href="/contact.html">Contact</a></li> </ul> </li> </ul> </div> <div class="dropdown ps-md-2 text-right order-2 order-lg-last"> <button class="btn btnNoOutline" type="button" id="dropdownMenuButton1" data-bs-toggle="dropdown" aria-expanded="false"> <img src="/img/search.svg" class="searchIcon" alt="Search Button"/> </button> <div id="searchDd" class="dropdown-menu dropdown-menu-end p-0" aria-labelledby="dropdownMenuButton1"> <form action="/search" method="GET"> <div class="input-group"> <input id="searchbox" name="q" type="search" class="form-control" autocomplete="off"> <button class="btn btn-secondary border input-group-append ml-2"> Search </button> </div> </form> <div class="ms-2 p-1 d-none"><a href="/search">Advanced search</a></div> </div> </div> </div> </nav> </div> <main id="eprintContent" class="container px-3 py-4 p-md-4"> <div class="row mt-4"> <div class="col-md-7 col-lg-8 pe-md-5"> <h4>Paper 2025/586</h4> <h3 class="mb-3">Heuristic Algorithm for Solving Restricted SVP and its Applications</h3> <div class="author"><span class="authorName">Geng Wang</span><span class="affiliation">, Shanghai Jiao Tong University</span></div> <div class="author"><span class="authorName">Wenwen Xia</span><span class="affiliation">, Shanghai Jiao Tong University</span></div> <div class="author"><span class="authorName">Dawu Gu</span><span class="affiliation">, Shanghai Jiao Tong University</span></div> <h5 class="mt-3">Abstract</h5> <p style="white-space: pre-wrap;">In lattice-based cryptography, many attacks are performed by finding a short enough vector on a specific lattice. However, it is possible that length is not the only restriction on the vector to be found. A typical example is SVP with infinity norm: since most SVP solving algorithms only aim to find short vector under Euclidean norm, the infinity norm is in fact another restriction on the vector. In the literature, such problems are usually solved by performing exhaustive search on a list of short vectors generated from lattice sieving. However, the sieving list might either be too large or too small to pass the additional restriction, which makes the solving algorithm inefficient in some cases. Our contribution in this work is as follows: (1) We formally define a new lattice hard problem called restricted SVP, and show that it can be used to generalize many lattice hard problems, including SVP with non-Euclidean norm and Kannan's embedding on approximate CVP. (2) We extend the dimension for free technique and the enumerate-then-slice technique into approximate SVP where the goal is to output a list of short vectors with a certain size. (3) We give the heuristic algorithm for solving restricted SVP, and design a hardness estimator for this algorithm, which can be used to estimate the concrete hardness of signature forgery in Dilithium and other lattice-based signatures. Using this estimator, we present a concrete security analysis for Dilithium against signature forgery under the gate-count model for the first time. Our estimation matches well with the security estimation from core-SVP model in the document of Dilithium, and we also combine our estimator with the rescaling technique to generate a tighter estimation.</p> </div> <div id="metadata" class="col-md-5 col-lg-4 ps-md-5 mt-4 mt-md-0"> <h5>Metadata</h5> <dl> <dt> Available format(s) </dt> <dd> <a class="btn btn-sm btn-outline-dark" href="/2025/586.pdf"> <img class="icon" src="/img/file-pdf.svg">PDF</a> </dd> <dt>Category</dt> <dd><a href="/search?category=PUBLICKEY"><small class="badge category category-PUBLICKEY">Public-key cryptography</small></a></dd> <dt>Publication info</dt> <dd>Published elsewhere. Minor revision. PQCrypto 2025</dd> <dt>Keywords</dt> <dd class="keywords"><a href="/search?q=Lattice-based%20Cryptography" class="me-2 badge bg-secondary keyword">Lattice-based Cryptography</a><a href="/search?q=Shortest%20Vector%20Problem" class="me-2 badge bg-secondary keyword">Shortest Vector Problem</a><a href="/search?q=Dilithium" class="me-2 badge bg-secondary keyword">Dilithium</a><a href="/search?q=Post-quantum%20cryptography" class="me-2 badge bg-secondary keyword">Post-quantum cryptography</a></dd> <dt>Contact author(s)</dt> <dd><span class="font-monospace"> wanggxx<span class="obfuscate"> @ </span>sjtu edu cn </span> </dd> <dt>History</dt> <dd>2025-04-02: approved</dd> <dd>2025-04-01: received</dd> <dd><a rel="nofollow" href="/archive/versions/2025/586">See all versions</a></dd> <dt>Short URL</dt> <dd><a href="https://ia.cr/2025/586">https://ia.cr/2025/586</a></dd> <dt>License</dt> <dd><a rel="license" target="_blank" href="https://creativecommons.org/licenses/by-nc/4.0/"> <img class="licenseImg" src="/img/license/CC_BY_NC.svg" alt="Creative Commons Attribution-NonCommercial" title="Creative Commons Attribution-NonCommercial"><br> <small>CC BY-NC</small> </a> </dd> </dl> </div> </div> <p class="mt-4"><strong>BibTeX</strong> <button id="bibcopy" class="ms-2 btn btn-sm btn-outline-dark" aria-label="Copy to clipboard" onclick="copyBibtex()"> <img src="/img/copy-outline.svg" class="icon">Copy to clipboard</button></p> <pre id="bibtex"> @misc{cryptoeprint:2025/586, author = {Geng Wang and Wenwen Xia and Dawu Gu}, title = {Heuristic Algorithm for Solving Restricted {SVP} and its Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/586}, year = {2025}, url = {https://eprint.iacr.org/2025/586} } </pre> <script> var bibcopy; function triggerTooltip() { console.log('setting tooltip'); } window.onload = triggerTooltip; function copyBibtex() { let range = document.createRange(); range.selectNode(document.getElementById('bibtex')); window.getSelection().removeAllRanges(); window.getSelection().addRange(range); document.execCommand('copy'); window.getSelection().removeAllRanges(); let bibcopy = document.getElementById('bibcopy'); let copyTooltip = new bootstrap.Tooltip(bibcopy, {trigger: 'manual', title: 'Copied!'}); copyTooltip.show(); setTimeout(function() { copyTooltip.dispose(); }, 2000); } </script> </main> <div class="container-fluid mt-auto" id="eprintFooter"> <a href="https://iacr.org/"> <img id="iacrlogo" src="/img/iacrlogo_small.png" class="img-fluid d-block mx-auto" alt="IACR Logo"> </a> <div class="colorDiv"></div> <div class="alert alert-success w-75 mx-auto"> Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content. </div> </div> <script src="/css/bootstrap/js/bootstrap.bundle.min.js"></script> <script> var topNavbar = document.getElementById('topNavbar'); if (topNavbar) { document.addEventListener('scroll', function(e) { if (window.scrollY > 100) { topNavbar.classList.add('scrolled'); } else { topNavbar.classList.remove('scrolled'); } }) } </script> </body> </html>